Get simple polygons

Question

I have a polygon C as below:

C = 10     0
     2     0
     2     2
     0     2
     2     0
     0     0
     0    10
    10    10

where the first column represents x's coordinate and the second column is corresponding to y's coordinate of the polygon C. As you can see in the picture above, this is not a simple polygon (this polygon contains a hole which is specified by white color), so I want to get all the simple sub-polygons from C which does not contain a hole. In this case output should be as following:

    C1 =  0     2
          2     0
          0     0

    C2 =  2     0
          2     2
          0     2
          0    10
         10    10
         10     0

Where C1 and C2 are corresponding to the small red triangle and big red polygon respectively.

The problem is how I can generate this sub-polygons?

Any idea will be appreciated.

Answer 1

First can we assume that all intersection points are present? It is easy to come up with polygons that intersect themselves in interesting ways. However using something like http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm you should be able to find and add in all intersections.

Next I will make the simplifying assumption that we do not ever retraverse a line segment. (You can deal with that pathological case in various ways.)

With that detail taken care of, next we need to locate all of the minimal polygons that can be defined by those points, whether or not they are eventually counted as inside or outside. (For convenience we will add a "point" at infinity and count the outside as a polygon.) To do that we first take each point, and list the points it connects directly to in counter-clockwise order. (Traveling parallel to the x-axis is 0 degrees, to the y axis is 90 degrees, the negative x-axis is 180 degrees, and then we wrap around as you go farther down.) So for your example we'd get something like this:

( 0,  0): ( 2, 0), ( 0, 2)
( 2,  0): (10, 0), ( 2, 2), ( 0, 2), ( 0, 0)
(10,  0): (10,10), ( 2, 0)
( 0,  2): ( 0, 0), ( 2, 0), ( 2, 2), ( 0,10)
( 2,  2): ( 2, 0), ( 0, 2)
( 0, 10): ( 0, 2), (10,10)
(10, 10): (10, 0), ( 0,10)

Now every simple polygon will hit each point between two of those points, and vice versa we can take one of those gaps (including the wrap around) and easily generate the associated polygon, at each corner making the smallest possible counterclockwise turn (ie from the point we came to to the one one after, possibly wrapping). For each line segment the polygon will be on the right hand side. We know we have all of them when we have every single point and gap. So in the above case we'd start with a point like ( 0, 0) and the following point ( 2, 0), then we look at ( 2, 0) and find that ( 0, 0) is followed by (10, 0), go to (10, 0) and find that ( 2, 0) is followed by (10,10) and proceed in this manner to trace out:

( 0, 0), ( 2, 0), (10, 0), (10,10), ( 0,10), ( 0, 2), ( 0, 0)

(Note, due to orientation this traced the outside area.)

Now we start with ( 0, 0) and the alternate starting point ( 0, 2) and do the same operation to get:

( 0, 0), ( 0, 2), ( 2, 0), ( 0, 0)

(This is the small inner triangle.)

For ( 2, 0) we've not yet traveled to ( 2, 2). So let's do that.

( 2, 0), ( 2, 2), ( 0, 2), ( 0,10), (10,10), (10,0), ( 2, 0)

(This is the large irregular polygon.)

For ( 2, 0) we have not yet traveled to ( 0, 2) so let's do that:

( 2, 0), ( 0, 2), ( 2, 2), ( 2, 0)

(This is the small white triangle.)

And then an enumeration of all of the possible directed line segments we might want to travel will find that we've covered them all. So these are our polygons. Now we're left to figure out what is inside and what is outside. There is a simple trick for that. Find a point with the lowest possible value of y (if there is a tie, any will do). For instance suppose we picked ( 2, 0). The connecting points, arranged counter-clockwise, were (10, 0), ( 2, 2), ( 0, 2), ( 0, 0). Those are respectively outside, inside, outside, inside...and furthermore once a one edge of a given polygon is marked as being outside or inside, all of its directed edges are the same. Thus we easily get:

outside:
  - (10, 0), ( 2, 2), ( 0, 2), ( 0, 0)
  - ( 2, 0), ( 0, 2), ( 2, 2), ( 2, 0)

inside:
  - ( 2, 0), ( 2, 2), ( 0, 2), ( 0,10), (10,10), (10, 0), ( 2, 0)
  - ( 0, 0), ( 0, 2), ( 2, 0), ( 0, 0)

And your answer will be just the inside polygons.

(Small optimization, we don't need to draw the outside polygons at all. We can take the first line segment whose orientation we discover, trace out an inside one, then go to one of its corners, identify the orientation of the line segments touching that corner, and start drawing other inside polygons. If we keep track properly, we'll eventually get them all.)