Bentley-Ottman Algorithm for Two Groups of Line Segments

Question

The Bentley-Ottman algorithm is used to calculate the intersection of segments.

However, instead of finding intersecting points of all lines between them, I want to find intersecting points between two groups of lines. This means that for each row in the row group, AI want to know the intersection points between these lines and the rows in the group B.

Anyway, can I extend the Bentley-Ottmann algorithm for this? I already have a implemented Bentley-Ottmann algorithm ( in the CGAL library ), and I do not want to modify it. However, I really want to find ways to reuse and expand it.

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

Answer 1

You can find all the intersections between all the lines in A+B, and then remove the intersections between the lines in one set. You do not greatly increase the complexity, and this allows you to use the CGAL library function unchanged with just a simple wrapper function.

Answer 2

Bentley-Ottman , , , A B? , , A- B- .

; .

Answer 3

, .

3D- 2 KD-, ( ).

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

(, , ), . , (, -)... , BVH, . , , , , .

Answer 4

, - , .

, , .

, B-O . http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

@marcog . O (n log (n + k)), , BO , ((n + k) log n).

, http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

@marcog . ( CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).

( ..) , .