Maximum area of self-intersecting polygon

3
votes

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:

  • The intersection points are known in advance, no need to calculate them (as the example shows)
  • The last point is guaranteed to connect back to the figure, i.e. no dangling lines
  • The polygon is always traceable, i.e. it can be drawn, without lifting the pen
  • Time complexity ideally not worse than O(n log(n)) where n is the number of points

Thanks for your help!

2
algorithmgeometry2dpolygon
Is the last point guaranteed to connect back to the figure, ie no dangling lines? – Carlos
Also it's always traceable right? You can draw the figure without lifting your pen? – Carlos
Seems to me that the real question is which points are inside of a larger polygon. Once you've removed them Shoelace algo should work. For that I came across this: en.wikipedia.org/wiki/Point_in_polygon. I'm not sure how to proceed from there though, thinking about it. – Carlos
I suppose you would built the set of segments, and for each point test a ray to count the number of intersections, which tells you if the point is inside or outside. Then build the set of points with the inside points removed. – Carlos
Hi @Carlos, thanks for your comments. I have edited the problem to answer your questions. I was thinking about this approach too but I believe then the time complexity is O(n²) - I was hoping for something with a better performance – satoshi

2 Answers

1
votes

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).

0
votes
  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.