Polygon region (recursively using Python)

Question

I am trying to solve an exercise from Learning a Python Book. But, I think, I do not understand the concept of recursion. I wrote a function Recursively. Therefore, I know some aspects. But I don’t have enough experience. And I stopped learning programming for about a year.

Anyway, let me ask you the full question:

A polygon can be represented by a list of (x, y) pairs, where each pair is a tuple: [(x1, y1), (x2, y2), (x3, y3), ... (xn, yn)]. Write a recursive function to calculate the area of ​​the polygon. This can be achieved by trimming the triangle using the fact that the triangle with angles (x1, y1), (x2, y2), (x3, y3) has an area of ​​(x1y1 + x2y2 + x3y2 - y1x2 -y2x3 - y3x1) / 2.

Despite the fact that the question has already given the formula, I used a different formula. Because I did some research on the polygon area. And if you look at here , then a different formula.

And to describe my program step by step would be better to explain what I want. Ok, I had to declare global regions, due to recursion:

area = 0 x = [0] * 3 y = [0] * 3 

And then I created a function recursively. As a result, this function always returns to zero. So my real problem is this:

 def areaofpolygon(polygon, i): global area, x, y # My variables try: # I prefered using try statement from using if-else statements. So it is the easier I guess. x[i], y[i] = polygon[i] # X and Y coordinates from tuple area += (x[i]*y[i+1] - x[i+1]*y[i]) #My formula except IndexError: return area/2 areaofpolygon(polygon, i+1) # Here, this is my weird recursion 

And my main function:

  def main(): mypolygon = [(1,2), (2,5), (1,4)] # I declared polygon as tuples # I called my function and started to count from zero, and the result will be prompted. print(areaofpolygon(mypolygon,0)) return 0 if __name__ == '__main__': main() 

And here is my complete code without comment:

 ''' Created on Feb 24, 2012 @author: msarialp ''' area = 0 x = [0] * 3 y = [0] * 3 def areaofpolygon(polygon, i): global area, x, y try: x[i], y[i] = polygon[i] area += (x[i]*y[i+1] - x[i+1]*y[i]) except IndexError: return area/2 areaofpolygon(polygon, i+1) def main(): mypolygon = [(1,2), (2,5), (1,4)] print(areaofpolygon(mypolygon,0)) return 0 if __name__ == '__main__': main() 

EDIT One

After reading your answers, I realized what was wrong with my code. So I decided to share the latest version of my program to get some other tips. Again, I had to declare global variables. How can I apply the function (lop_triangle) from senderle

 area = 0 x = [0] * 3 y = [0] * 3 

My function, which divides the tuple and gets the x and y coordinates.

 def sides_of_polygon(polygon, i): global x, y try: x[i], y[i] = polygon[i] return sides_of_polygon(polygon, i+1) except IndexError: return x, y 

My function calculates the polygon area (as before)

 def area_of_polygon(x, y, i): global area try: area += x[i]*y[i+1] - x[i+1]*y[i] return area_of_polygon(x, y, i+1) except IndexError: return area/2.0 

My main function ...

 def main(): mypolygon = [(1,2), (2,5), (1,4)] dx, dy = sides_of_polygon(mypolygon, 0) print(area_of_polygon(dx,dy,0)) return 0 if __name__ == '__main__': main() 

Please help me improve my code without giving a complete solution.

EDIT 2

After discussing with senderle, I realized where the problem is, and the senderle solution is better than mine, so I suggest you use it. Anyway, He helped me make the right code. And I had to change the formula again.

 area += x[i]*y[(i+1) % 3] - x[(i+1) % 3]*y[i] 

He also added for longer polygons 3 should be len (vertices). Thanks to everyone for their time.

Answer 1

The essence of recursion is this:

• Define a simple base register and decide for this.
• Capture a process that, when repeated, reduces a more complex case to this base case.
• Apply the process in # 2 to the problem until you reach the base case.

In your case, the first step is very simple. The smallest polygon is a triangle. The area of ​​the triangle (x1y2 + x2y3 + x3y1 – y1x2 –y2x3 – y3x1) / 2 . (It looks like they made a mistake in the problem, though ...)

The second step is also simple, because the task operator gives it to you: if an n-vertex polygon is given, delete the triangle, determine its area and add it to the region of the resulting (n-1) - vertex polygon.

We will break it into pieces. First, the function to solve # 1:

 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 

Easy. Now the function for solution # 2 is all we need is a function that overlaps the triangle and returns both it and the resulting smaller polygon:

 def lop_triangle(points): triangle = [points[0], points[-1], points[-2]] polygon = points[:-1] return triangle, polygon 

If this is not obvious, it simply creates a triangle using the first and last two points of the polygon. Then it removes the last point of the polygon, which is now equivalent to shredding the triangle. (Draw an n-polygon and name its vertices from 0 to n to see how it works.) So now we have a triangle and a simpler polygon.

Now, let it all be together. This third step is to some extent the most difficult, but since we have solved the first two problems, the third is easier to understand.

 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) 

All the magic happens on this last line. Each time area_of_polygon receives a triangle, it simply returns the area of ​​the triangle. But when it receives a larger polygon, it overlaps the triangle, occupies the area of ​​this triangle and adds it to the area of ​​the smaller polygon. So they say that a polygon has 5 vertices. The first time area_of_polygon is called (c1), it discards the triangle, takes its area and then calls area_of_polygon (c2) again, but this time with a 4-vertex polygon. Then the area_of_polygon lops of the triangle and calls area_of_polygon (c3) again, but this time with a three-vertex polygon. And then he does not need to call area_of_polygon again. It simply returns the area of ​​the triangle to the previous call (c2). This sums the result with the triangle in (c2) and returns that value in (c1). And then you have your answer.

In addition, for what it costs, the tungsten formula can be written with great clarity in three lines:

 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 

Answer 2

The execution of your formula is erroneous. It looks forward to the values ​​in your x, y lists that have not yet been set with (x[i]*y[i+1] - x[i+1]*y[i])

If you put the print statement inside the try-except block, you will see that you simply multiply by zero and get a zero region:

 try: x[i], y[i] = polygon[i] area += (x[i]*y[i+1] - x[i+1]*y[i]) print x[i], y[i+1], x[i+1], y[i] except IndexError, e: return area/2 #1 0 0 2 #2 0 0 5 

Also, you are not returning the results of your recursive call to areaofpolygon, so you will never get this area/2 . You want: return areaofpolygon(polygon, i+1) . And make sure you really divide by 2.0 to get floating point precision, since your points are ints.

Try using the formula you found or suggested in another question.

Update

Here is a fixed version of your code:

 #!/usr/bin/env python from random import randint from shapely.geometry import Polygon area = 0 def areaofpolygon(polygon, i): global area if i == 0: area = 0 try: x1, y1 = polygon[i] x2, y2 = polygon[i+1] area += (x1*y2) - (x2*y1) except IndexError, e: x1, y1 = polygon[0] x2, y2 = polygon[-1] area += (x2*y1) - (x1*y2) return abs(area/2.0) return areaofpolygon(polygon, i+1) def main(): mypolygon = [(randint(0, 100), randint(0, 100)) for _ in xrange(10)] print mypolygon area = areaofpolygon(mypolygon, 0) assert area == Polygon(mypolygon).area print "Test passed." return 0 if __name__ == '__main__': main() ### Output ### $ ./test.py [(29, 76), (85, 49), (27, 80), (94, 98), (19, 1), (75, 6), (55, 38), (74, 62), (0, 25), (93, 94)] Test passed. $ ./test.py [(13, 37), (98, 74), (42, 58), (32, 64), (95, 97), (34, 62), (34, 59), (21, 76), (55, 32), (76, 31)] Test passed. $ ./test.py [(38, 67), (66, 59), (16, 71), (53, 100), (64, 52), (69, 31), (45, 23), (52, 37), (27, 21), (42, 74)] Test passed. 

Note that you do not need global lists x, y. And you also missed the last part of the equation in which you use the last point and the first point.

Answer 3

Use this formula.

https://upload.wikimedia.org/wikipedia/en/math/c/b/b/cbb6a25439b51061adb913c2a6706484.png

You complete your task in one cycle.