4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Convex polygon? $\endgroup$
    – JBL
    Commented Jun 27, 2010 at 1:58
  • $\begingroup$ The centroid may not be inside the polygon. Unless, as JBL questioned, your polygon is convex. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 27, 2010 at 2:15

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kevin Nuckolls
    Commented Jun 27, 2010 at 15:20
  • $\begingroup$ "Pick the vertex with the highest $x$ value" is basically how every algorithm in computational geometry starts (at least the most basic algorithms, I never got many pages deep into the subject). $\endgroup$
    – Ville Salo
    Commented May 8, 2020 at 6:11
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I like Anton's answer better! $\endgroup$
    – Joseph O'Rourke
    Commented Jun 27, 2010 at 2:25
  • $\begingroup$ 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? $\endgroup$
    – Kevin Nuckolls
    Commented Jun 27, 2010 at 22:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .