Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
1  
At first I thought that I'd have to go through the list of possibly millions of vertexes looking for the highest x value. Then return through the list again to do the actual labeling. A more efficient way would be to just go through the list of vertexes once labeling along the way, making an assumption as to which side was the initial "inside". Traversing the list we can also keep track of the highest x value. When we find it, if we find that our assumption was incorrect and that all the "inside" labels are actually "outside" labels, then we just flip the label for all of the labels. –  Kevin Nuckolls Jun 27 '10 at 15:20
add comment

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.

share|improve this answer
    
I like Anton's answer better! –  Joseph O'Rourke Jun 27 '10 at 2:25
    
I'm interested in how this algorithm would work. Can you provide links to definitions of "orient" and "to be consistent with" in this context? –  Kevin Nuckolls Jun 27 '10 at 22:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.