How do I detect bounded regions of closed-loop polygons?

Question

I am given an ordered set of points in 2D space as an output of a previous process. Coordinate points will be given in the form ((x0,y0),(x1,y1),...,(xn,yn)), where the very last coordinate pair will be a repetition of the first pair (i.e x0 = xn and y0 = yn). In this way, I know that when I re-encounter the same coordinate, I have made a closed loop. I would like to be able to detect the enclosed area by the polygon. If a single closed loop is given, the output should be the enclosed area of that closed loop. Now say I have a separate set of points, similar to to the first set. If a set of many closed looped polygons is given, then if each polygon is separated in space from each other, the output should be each enclosed area. However, if some of the polygons enclose each other, it should be the area bounded between both of them. For example, if I have one closed loop polygon inside another, the output area should between both of them (or in other words, the area enclosed by the larger one minus the area enclosed by the smaller one). If I have more than one closed loop polygon inside of a single larger one, it should be the area enclosed by the larger one minus all the areas enclosed by the smaller ones).

For a case where I have a region A enclosed by a region B, where B is enclosed by a region C, there are three distinct regions.

1. Region C minus region B (bounded on the outside by polygon 1)
2. Region B minus region A (bounded on the outside by polygon 2)
3. Region A (bounded on the outside by polygon 3)

Of the three regions, I only want region 1) and region 3). The reason I do not take region 2) is because for all the bounded areas on my 2D plane, the outermost polygons always represent the boundaries of a relevant region, and the input that produced my sets of coordinates representing my closed loop polygons would never have given me the points for polygon 2 if in the end region 1) and region 2) were meant to be combined. It instead would have given me only polygon 1 and polygon 3, similar to the case I described above.

In summary, - I am given enough information to know all the coordinate points for a set of closed loop polygons on a 2D plane and they are distinguishable from each other. - I need to develop an algorithm that will take in the entire set of closed loops polygons and return enough information to describe a bounded area. In thinking about the problem, I think the output that I would want is to know whether for a each and every line segment of the a closed loop polygon, on which side of that line segment is inside and outside of the polygon. - It should be able to resolve the case where I have polygons inside of polygons. - Closed loop polygons will never share any points. Each set of coordinate points will be unique to a polygon.

My initial thoughts were calculate the centroid of the polygon and then compare all line segments to the centroid, but I don't think this would work for all cases.

Answer 1

Judging by the description of your input, splitting your input stream into separate polygons is a trivial task.

After that, in order to "return enough information to describe a bounded area" you can build the following data structure out of your polygons:

1. Separate all polygons into two classes: main polygons and hole polygons.
2. Main polygon is... well, the exterior border of a bounded area. It separates the interior of the bounded area from the "outside world".
3. Hole polygon is a polygon that describes a hole in some main polygon.
4. Each hole polygon is associated with exactly one main polygon
5. Each main polygon is associated with zero or more hole polygons
6. Optionally, you can order the vertices in main polygons counterclockwise and vertices in hole polygons clockwise. But this is not strictly necessary to satisfy the formal requirement of "describing a bounded area"

The resulting structure is two-tiered: you end you with a list of main polygons, and each main polygon might contain a list of its holes.

In your example, you have 4 main polygons. One of them contains two hole polygons.

So, all you need to do is to recognize hole polygons and properly associate them with their main polygons.

An industrial-strength approach for solving this task would be an application of sweep-line algorithm to the input polygons. It would easily perform the classification into main and hole polygons as well as build the proper association between them.

An ad-hoc algorithm might look as follows

1. Sort all polygons in order of increasing area
2. For each polygon p in the sorted order
   3. Take any vertex v of p
   4. Perform an "inside" test of v against all polygons of greater area than p (for example, by using a simple even-odd intersection test: How can I determine whether a 2D Point is within a Polygon?)
   5. If the number of polygons that contain v is odd, p is a hole polygon. Otherwise, p is a main polygon
   6. If p is a hole polygon, then the smallest-area polygon that contains v is its associated main polygon.

That's it.

Answer 2

I think the output that I would want is to know whether for a each and every line segment of the a closed loop polygon, on which side of that line segment is inside and outside of the polygon.

1. Compute the normal for the line segment (perpendicular line).
2. Compute the mid-point of the line segment (any point will do).
3. Intersect every other line segment with a ray projected from the mid-point in the direction of the normal.

Intuitively, each intersection means either entering or exiting another polygon. Since finally the ray will be outside all polygons, we can deduce that if the ray intersects an even number of other line segments, then the side of the line segment indicated by the normal is on the outside of the polygon. If odd, it's on the inside.

There are a couple of tricky cases: one is where the ray exactly intersects the end-point of two connected line segments. Be careful to only count this as one intersection. The other case is where the ray is parallel to and exactly overlaps another line segment. This should count as two intersections.

There are more efficient algorithms (e.g. involving triangulation), but this one is simplest.