How do I calculate the area of a 2d polygon?

by

Here is the standard method, AFAIK. Basically sum the cross products around each vertex. Much simpler than triangulation.

Python code, given a polygon represented as a list of (x,y) vertex coordinates, implicitly wrapping around from the last vertex to the first:

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                         for ((x0, y0), (x1, y1)) in segments(p)))

def segments(p):
    return zip(p, p[1:] + [p[0]])

David Lehavi comments: It is worth mentioning why this algorithm works: It is an application of Green’s theorem for the functions −y and x; exactly in the way a planimeter works. More specifically:

Formula above =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area

More Related Contents:

  1. Is there an efficient algorithm to generate a 2D concave hull?
  2. How to determine if a point is in a 2D triangle? [closed]
  3. Circle line-segment collision detection algorithm?
  4. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  5. An algorithm for inflating/deflating (offsetting, buffering) polygons
  6. Algorithm to detect intersection of two rectangles?
  7. How to calculate an angle from three points? [closed]
  8. Simple calculations for working with lat/lon and km distance?
  9. Sort points in clockwise order?
  10. How do I efficiently determine if a polygon is convex, non-convex or complex?
  11. Finding whether a point lies inside a rectangle or not
  12. How do you calculate the average of a set of circular data? [closed]
  13. What is an Efficient algorithm to find Area of Overlapping Rectangles
  14. Largest circle inside a non-convex polygon
  15. How to check if line segment intersects a rectangle?
  16. How to compare two shapes?
  17. Combined area of overlapping circles
  18. Calculate largest inscribed rectangle in a rotated rectangle
  19. Circle-circle intersection points
  20. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  21. Sort Four Points in Clockwise Order
  22. Collision detection of huge number of circles
  23. How can I create an internal spiral for a polygon?
  24. Calculating the position of points in a circle
  25. Find if a point is inside a convex hull for a set of points without computing the hull itself
  26. Best way to find a point on a circle closest to a given point
  27. Algorithm for reflecting a point across a line
  28. determine if a point sits inside an arbitrary shape?
  29. How can I perform Collision Detection on rotated rectangles? [closed]
  30. Location of highest density on a sphere

Leave a Comment