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.