We have a dataset that consists of connectors and segments. Each segment has exactly two connectors, but each connector can belong to zero or more segments (i.e., Connector “A” in the left image below has no segments, while Connector “M” has three, MR, ML, and MN. )
It is clear that wherever any lines meet or intersect, there will be a connector, so we don’t need to worry about even / odd rules, overlapping or partially closed polygons, etc., since they are not applied.
In short, we are trying to identify all created polygons (colored shapes in the correct image). I believe that this can be done in two stages.
Part 1: removing excess items
The standalone connectors (here the “A” connector) can simply be removed because they cannot be part of the shape contour.
Floating endpoints that refer to the same segment (connectors "B" and "E") can also be deleted, since they also cannot be part of the shape outline. This will also delete their referenced segments (BC and ED).
Doing the above recursively then identifies “C” as the endpoint (since “B” and BC have already been deleted), so it and the remaining CD segment can also be deleted. In the next recursive pass, the “D” connector and the DF segment will also be removed, etc.
However, I did not find a good way to identify the HI segment. However, I think this can be achieved during polygon detection, since such segments will only be the result of compound paths and will be tracked in both directions during one shape detection. (More on this below.)
Step 2: Polygon Detection
Each segment can be traced in two directions. For example, a segment connecting 'O' and 'P' can be either OP or PO. Choosing the clock direction of the trace, the OP will belong to the polygon OPQN, while the PO will belong to the polygon POI.
The following logic assumes a clockwise track direction.
Starting from any segment, while traversing, if you return to the starting point, you have identified a potential polygon. Keeping the current delta of the angle of your course during tracing (this is how much your course rotates, and should not be confused with the simple addition of angles between segments), when this is done, if this angle is positive, you will find a valid polygon. If it is negative, you have found a “containing” polygon, that is, one that contains one or more “valid” polygons. The outer perimeter of the entire figure (or figures) contains polygons.
Consider the case of a square diagonally divided into two triangles. By tracking each segment twice - one in each direction - you get three potentially acceptable polygons: a square and two triangles. The triangles will have a positive delta angle telling you that they are valid, but the triangle triangle will be negative, telling you what the polygon contains.
Note. The containing polygon can also be equal to the actual polygon. It will just be "wound" in the opposite direction.
Consider a simple triangle. The track clockwise will give the correct polygon. A second attempt to draw a trace in a clockwise direction will actually result in a counterclockwise trace, which will give you a negative delta of the angle, telling you what the outline of the shape really is.
Note: You must also check other polygons encountered along this path, and check each point for any previously encountered points during shape detection. If you find that you have visited the same point again, save the polygon created since the first collision with this point, check its angle. If it is positive, it is a valid polygon (and you are actually tracking the contained polygon.) If it is negative, you have found the contained polygon (in this case, you are currently tracking a valid polygon.) Finally, delete all segments in your cumulative stack and return to the first the case when the last point was detected, and continue the detection.
For example, if you start with “J” and move clockwise, you will go through “I”, “H”, then “G”, then “F”, then you will return to “H”. You just found a negative angle HGF polygon, so you know that it contains a polygon. Remove these three segments from your stack and continue. Now you will press "I" again. In this case, you have already visited the same segment during this passage, but in a different direction, so just completely remove this segment from your stack and continue next to “O”, then “N”, etc. back to "j".
When a segment is tracked in both directions, it can be considered "used" and no further processing of this segment is required. Continue processing all unused segments. After all segments have been traced in both directions, you can be sure that all polygons - real and containing - have been found.
Finally, check each containing polygon to see if it falls into any valid polygon. If so, exclude it from this valid polygon, creating a compound path. In the example given here, the containing HGF polygon is contained in a valid blue polygon, so it should be excluded. Note that there is also a valid HFG polygon, which is marked in red here.
Anyway, this is what I came up with, but I wonder if there is a better / simpler way. Thoughts?