Efficient algorithm for finding a point P with the highest winding number

Question

Given an ordered list of two-dimensional points $P$ that represent the vertices of an $N$-sided (very) self-intersecting polygon, find a point $p_{best}$ with the highest winding number of all points within that polygon represented by $P$.

Sunday's algorithm sounds great for efficient calculation given one point, but selection of what points to query seems difficult. Originally, I thought one arbitrarily selected point infinitesimally to the right/left of each segment would be sufficient, or that a point at the, but both do not account for e.g. the center of star polygons.

One approach that would work would be to break down each segment at each crossing point, and then selecting a point to the right / left of each sub-segment. Is that necessary, though? In the worst case, a star polygon with N segments could have $O(N^2)$ sub-segments once broken down.

The context for this is finding what area I've "run the most circles around" given my Google Maps point-by-point tracking data, so N is on the order of 10,000 to 100,000. I am curious because I have a guess it'd be something on my commute, but I'm not sure.

Answer 1

Yes, you can "break down each segment at each crossing point", and then you'll get a Planar Subdivision or Planar straight-line graph. All the edges of this graph will be oriented according to the natural orientation of the original self-intersecting polygon. It's easy to see that all the points, belonging to the same face of this graph, will have the same winding number - so actually you need to find a face with maximal winding number.

Now observe that winding numbers of two faces, having a common edge, differ by one. If you move from a face with winding number $N$ to its neighboring face, crossing their common edge, oriented from left to right - this neighboring face will have winding number $N+1$. And vice versa, if you cross the edge, oriented from right to left, the face winding number will be decremented.

The winding number of the external face is zero. So, you can start from the external face and calculate winding numbers of all faces, jumping from face to face across their common edges. Now, take the face with maximal winding number and choose any point inside it - this will be your $p_{best}$.