How to find simple polygons in a complex polygon created by two lines

Question

Given the image attached, I am looking for a way/strategy/pseudocode to iteratively find each polygon created either by two blue-dotted line segments, a blue-dotted line segment and an intersection, or two intersections.

I have an ordered list of line segments for each line, an ordered list of blue-dotted line segments, and an ordered list of intersections. Segments are stored as a list of two (x,y) tuples, intersections are stored as one (x,y) tuple. By ordered in this case I mean the shape has been processed from left to right, so everything is stored as if you were to follow the paths in an S shape from the bottom left to the top right.

At the moment I am processing each section of the polygon based on what is contained within two blue line segments, although I don't think this is a good way of going about it. I feel as though any attempt at an algorithm so far has overfit to this specific example. I'm fairly new to computational geometry so any help is appreciated.

edit 1: I am looking for a way to identify simple polygons (shapes with no holes and no self-intersections). For example beginning in the bottom left, there is a triangle created by the blue_line_seg[0], blue_line_seg[1] and part of the first line segment (since in this case we are following the green and red paths from left to right). This polygon could be stored (for the moment) as any arrangement of the points associated with those two blue line segments and the endpoint of the first green line segment ((3,6), (5.3,5.7), (5,3)). following that there is a 4-sided polygon created using blue_line_seg[1], blue_line_seg[2], part of the first line segment on the red path, and the entire first segment of the green path. However, between blue_line_seg[2] and blue_line_seg[3] we encounter an intersection point at (13.5,5.5), which would close off the third polygon. That polygon would also contain the last endpoint of the first red line segment. This is where it gets confusing: i'm trying to find a way to process each simple polygon without using too many heuristics / overfitting to this specific example.

Answer 1

Please take a look at the DCEL data structure, which is normally used for representation and processing of polygonal subdivisions of the plane. This data structure usually stores three kinds of geometric objects - vertices, edges and faces. Relationships between these objects are also stored in the DCEL - for example, for each vertex you can find all the edges, incident to this vertex. Simple polygons you are looking for will be represented by finite DCEL faces.

You'll need to convert your ordered lists of segments and intersections to the DCEL. In order to do that you need to split all your red and green segments into edges by endpoints of blue segments and intersection points. All edges endpoints will become vertices - and you'll need to store relationships between edges and vertices. Each edge is represented by a pair of directed half-edges, and for each half-edge you'll be able to find the next half-edge with the same face on its left side. So, each face will be bounded by a loop of directed half-edges.

This structure has been implemented many times already, and one of best implementations is the CGAL 2D Arrangements - it covers degenerate cases as well, which is important in Computational Geometry.

Answer 2

It is an easy matter to generate a single (crossed) polygon from the red polyline and the blue segments. Now for a relatively simple solution, you can

• detect all edge/edge intersection points; this can be done by brute-force or more efficiently (Bentley-Ottman algorithm);

• label the intersections with the index of the initial point of the edge plus the relative distance to the intersection (a fraction in $[0,1)$); every intersection has in fact two labels;

• sort the intersections by increasing label, but keep a link between the two labels relating to the same intersection;

• you now have a list of "polygonal arcs" with known endpoints - and a way to enumerate the intermediate vertices; and the endpoints have links that form closed loops.

The labeling with a fraction is required when there are several intersections along the same edge; alternatively, you can sort the intersections along the edge and number accordingly.

This description assumes the points in general position (i.e. no vertex on an edge, no overlapping edges).

In the picture, the initial arcs are 5.2, 0, 1, 2, 2.4; 2.4, 2.6; 2.6, 3, 4, 4.8; 4.8, 5, 2.4. Then after forming the loops, 5.2/2.4, 0, 1, 2, 2.4/5.2; 2.6/4.8, 5, 2.4/5.2, 4.8/2.6; 2.6/4.8, 3, 4, 2.6/4.8.