calculating bounded polygon from intersecting linestrings

0
votes

I am using boost geometry and I am trying to calculate a "bounded" polygon (see image below) from intersecting polylines (linestrings 2d in Boost geometry). Currently, my approach is i) to get all the intersection points between these lines and then ii) "split" each line at the intersection points. However, this algorithm is a little bit exhaustive. Does anyone know if boost geometry has something more efficient for this?

enter image description here

Moreover, how could I get the segment (or vector of points) for each linestring that lie withing two intersection points? For example, for the green linestring, if I have the two red intersection points, how can I get the linestring between these two points (vector of points containing the two red intersection points and the two interior blue points)? Is there any "split"-like functionality in boost geometry?

Any suggestion is much appreciated. Thanks a lot in advance.

1
boostcomputational-geometryboost-geometry
Are you intersecting a polyline against a square grid ? – Yves Daoust
Hi, many thanks the comment. The intersections can be between polylines and lines. For a given set of polylines or lines I would like to calculate the bounding polygon as depicted in the image above. For the given example we have 3 lines and a polyline. – GioR
Can it be between two polylines ? How many lines/polylines at the same time ? – Yves Daoust
Yes, it must handle cases of two polylines, as well. For example, it can be a closed region between two polylines, each representing a hemi-circle. However, the number of polylines can be any providing that they can enclose/form a bounding polygon. – GioR
I don't think you are after a "bounding" polygon. Rather a "bounded" polygon. – Yves Daoust

1 Answers

2
votes

From the given description, it seems that the (poly)lines intersect in pairs to form a single loop, so that the inner polygon is well defined. If this is not true, the solution is not unique.

As the number of lines is small, exhaustive search for the pairwise intersections will not be a big sin. For 5 (poly)lines, there are 10 pairs to be tried, while you expect 5 intersections. Forming the loop from the intersections is not a big deal.

What matters most is if Boost Geometry uses an efficient algorithm to intersect polylines. Unsure if this is documented. For moderate numbers of vertices (say below 100), this is not so important.

If the number of points is truly large, you can resort to an efficient line segment intersection algorithm, which lowers the complexity from O(n²+k) down to O((n+k) log n). See https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm. You can process all polylines in a single go.

If your polylines have specific properties, they can be exploited to ease the task.