StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The essence of recursion is as follows:</p> <ol> <li>Identify a simple base case and solve for that.</li> <li>Conceive of a process that, when repeated, reduces a more complex case to that base case.</li> <li>Apply the process in #2 to the problem until you reach the base case. </li> </ol> <p>In your case, the first step is easy. The smallest polygon is a triangle. The area of a triangle is <code>(x1y2 + x2y3 + x3y1 – y1x2 –y2x3 – y3x1) / 2</code>. (It looks like they misstated it in the problem though...)</p> <p>The second step is also easy, because the problem statement gives it to you: given an n-vertex polygon, lop off a triangle, determine its area, and add it to the area of the resulting (n-1)-vertex polygon. </p> <p>We'll break it down into parts. First, a function to solve #1:</p> <pre><code>def area_of_triangle(points): (x1, y1), (x2, y2), (x3, y3) = points return abs(x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1) / 2 </code></pre> <p>Easy. Now a function to solve #2. All we need is a function that lops off a triangle and returns both it and the resulting smaller polygon:</p> <pre><code>def lop_triangle(points): triangle = [points[0], points[-1], points[-2]] polygon = points[:-1] return triangle, polygon </code></pre> <p>If it's not obvious, this simply creates a triangle using the first and the last two points of the polygon. Then it removes the last point of the polygon, which is now equivalent to chopping off the triangle. (Draw a n-polygon and label its vertices from 0 to n to see how it works.) So now we have a triangle and a simpler polygon. </p> <p>Now, let's put it all together. This third step is in some ways the hardest, but because we solved the first two problems already, the third is easier to understand. </p> <pre><code>def area_of_polygon(points): if len(points) == 3: return area_of_triangle(points) else: triangle, polygon = lop_triangle(points) return area_of_triangle(triangle) + area_of_polygon(polygon) </code></pre> <p>All the magic happens in that last line. Every time <code>area_of_polygon</code> gets a triangle, it just returns the area of a triangle. But when it gets a larger polygon, it lops off a triangle, takes the area of that triangle, and adds it to... the area of a smaller polygon. So say the polygon has 5 vertices. The first time <code>area_of_polygon</code> is called (c1), it lops off a triangle, takes its area, and then calls <code>area_of_polygon</code> (c2) <em>again</em>, but this time with a 4-vertex polygon. Then <code>area_of_polygon</code> lops of a triangle, and calls <code>area_of_polygon</code> (c3) <em>again</em>, but this time with a 3-vertex polygon. And then it doesn't have to call <code>area_of_polygon</code> again. It just returns the area of a triangle to the previous call (c2). That sums the result with the triangle in (c2) and returns that value to (c1). And then you have your answer. </p> <p>Also, for what it's worth, the <a href="http://mathworld.wolfram.com/PolygonArea.html" rel="nofollow">wolfram formula</a> can be written with great clarity in three lines:</p> <pre><code>def area_of_polygon(vertices): pairs = zip(vertices, vertices[1:] + vertices[0:1]) return sum(x1 * y2 - y1 * x2 for (x1, y1), (x2, y2) in pairs) / 2 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload