Bentley-Ottmann Algorithm For Two Groups of Lines Segments

Question

The Bentley-Ottmann algorithm is used for the computation of intersection of line segments.

However, instead of finding the intersecting points of all the lines among themselves, I want to find the intersecting points between two groups of lines. This is to say that for every line in line group A, I want to know the intersection points between those lines and the lines in group B.

Is there anyway I can extend the Bentley-Ottmann algorithm for this? I already have the existing Bentley-Ottmann algorithm implemented ( in the library of CGAL), and I am not keen to modify it. I am, however, am keen to find ways to reuse it and extend it.

Edit: Any other algorithms ( not necessarily based on Bentley- Ottmann) are welcome. It would be better if those algorithms are already implemented in the existing library.

Answer 1

You could find all intersections between all lines in A+B, then remove intersections between lines in the same set. You're not increasing the complexity by much and this allows you to use CGAL's library function unmodified with only a simple wrapper function.

Answer 2

Where Bentley-Ottman keeps a tree of line segments ordered by their current vertical position, couldn't you keep two trees, one each for groups A and B? Then where the original algorithm checks the neighbors above and below the current point, you'd check the A-neighbor above against the B-neighbor below, and vice versa.

This is based on a quick skim of the Wikipedia article; I haven't written much geometrical code in the past decade.

Answer 3

Adding this answer for completeness, even though it may not be the most efficient method for 2 dimensions.

In 3D graphics its common to 2 KD-trees, which can be used to detect all overlapping nodes (can be used for boolean operations on geometry).

Working example (C code). https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b$1089

If there are many small segments (such as the path of a hand drawn line), this will be reasonably efficient. However if there are many long edges (think pickup-sticks)... this will perform badly, and you would want to split leaf nodes in the BVH tree to get better performance. However if thats the case, its probably better to use a different method as suggested in other answers.

Answer 4

Yes Bentley-Ottmann algorithm can be extended to do this, along with other methods.

In literature, the task you described along the lines of reporting intersections between red and blue lines.

Here is a paper extending B-O sweep to an optimal algorithm. http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

I would disagree with @marcog's claim about complexity. The paper linked claims optimal time of O(n log(n+k)), if you filter the intersections, you will have to perform a B-O sweep on all lines, and it would be ((n+k) log n).

There are other similar algorithms which may not require complex data-structures http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

For fewer edges and fewer intersections between edges, the solution in @marcog's answer might work well. (Here is an example from CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).

If you need to process complex polygons (GIS data etc.) or need a general algorithm, this class of algorithms might be worth while.