# How can I efficiently determine which side of a line segment is internal to the polygon?

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?

-
Convex polygon? – JBL Jun 27 '10 at 1:58
The centroid may not be inside the polygon. Unless, as JBL questioned, your polygon is convex. – Joseph O'Rourke Jun 27 '10 at 2:15

Select any edge $e_1$, and orient it arbitrarily. Now orient the next edge $e_2$ (the one that uniquely shares the head endpoint of $e_1$) to be consistent with $e_1$. Continuing in this manner, you orient the boundary in $O(n)$ time (assuming you can find the next edge in constant time).
Now choose a point $x$ outside the bounding box of the polygon, so it is known to be exterior. Compute the sum of the signed areas of all the triangles determined by $x$ and $e_i$. If you've oriented the polygon counterclockwise, this sum should be zero. If it is not, reverse the orientation. Now your interior is to the left of every edge.