CODEWITHSUNDEEP
algorithmgeometry2dpolygon
satoshi
satoshi

Reputation: 4113

Maximum area of self-intersecting polygon

I'm looking for an algorithm for calculating the maximum area in a self-intersecting polygon. As it's self-intersecting it is not trivial to calculate the area with methods such as the shoelace formula.

Example:

Self-intersecting polygon

The polygon in the example prioritises vertices with the "smallest" letter alphabetically, sometimes going back to the same vertex in a non-alphabetical way as it is self-intersecting. Although that shouldn't make a difference in the expected area.

In this case the algorithm should output 40: the area of the square (36) plus the area of the 4 outer triangles (4).

Constraints:

Thanks for your help!

Upvotes: 3

Views: 309

Answers (2)

satoshi
satoshi

Reputation: 4113

I think I've got it.

  1. Find the vertex with the lowest x. In case of a tie, pick the one with the lowest y. This process is O(n)
  2. Of the 2+ segments connected to the vertex found in point 1, pick the one that forms the smallest angle with the x-axis, so as to start traversing the polygon in a clockwise direction. This process is O(s) where s is the number of segments that are connected to the starting vertex.
  3. Keep choosing the next connected segments ignoring the order of the segments in the original polygon. In case of an intersection, pick the segment that forms the smallest angle with the current segment with the direction negated, measured clockwise. This is in order to choose the segment that lays on the outside of the polygon. This process is O(n i/2) where i is the average number of segments connected to each vertex.
  4. Once back to the starting point, calculate the area using the shoelace formula. This could actually be calculated in parallel whilst traversing the polygon in points 2 and 3.

This algorithm's worst case time complexity is O(n i/2) where n is the number of vertices and i is the average number of segments connected to each vertex. The best case complexity is O(n) for a polygon that never intersects. In my case the polygons rarely intersect so this process is close to O(n).

Upvotes: 1

Carlos
Carlos

Reputation: 6021

  1. Build the set of segments from the points given
  2. For each point, test a ray to see if it intersects an even or odd number of those segments.
  3. The even intersect counts are internal points, remove them.
  4. Shoelace algo tells you the area of the remaining shape.

Let me think of a way where this isn't n^2, because you are comparing n points with n segments.

Upvotes: 0

Related Questions