1
$\begingroup$

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.

enter image description here

$\endgroup$
2
  • $\begingroup$ I don't understand. What is meant by a polygon created by two blue-dotted lines? Two lines don't seem to be enough to define a polygon. Please tell us more about the definition of the polygon and how it relates to the lines/intersections. Are you drawing a distinction between a line and a line segment? If so, what is a line? $\endgroup$ – D.W. May 31 at 20:48
  • $\begingroup$ @D.W. I added more context, thanks for your help $\endgroup$ – Nixon May 31 at 21:20
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.