As part of a larger analysis I have a need to break a polygon into it's individual line segments and mark which side is "inside" of the polygon. If your curious this is going to be fed into a big parallel map reduce algorithm to translate the representation of the polygon into a more efficient data structure for fast recall.
The naive solution I've come up with is to first cast a ray towards the calculated centroid of the polygon from each vertex of every line segment and count the number of line intersections between the vertex and the centroid. That way I can determine if the side of each line that is facing the centroid is "internal" or not. Based upon whether or not each ray has an odd or even number of intersections.
The best way to think about this is that I will be creating a triangle at a single line segment with the two rays that are cast towards the centroid. I can determine based upon the internal angles which side of the line segment is "facing" the centroid. There is a distinct difference between facing the centroid, and actually being on the internal side of the polygon.
Unfortunately, this is quite inefficient to calculate. Assume I have a very detailed polygon with tens of millions of vertexes. It would be very slow if for each vertex I created a vector between the centroid and the vertex, then ran a line intersection algorithm against every other line segment in the polygon. It's just not going to finish in a timely manner.
I think I can walk the line segments one by one and determine based upon the internal angles at each vertex which side of each line segment is "internal" to the polygon. Are there any known theorems out there that I am unaware of that will help me answer this problem?
Best Answer
Pick the vertex with the highest x value. You can label the edges touching it. Now just walk along your polygon and label the edges consistently.