CGAL users discussion list

[Winnie <>]

Hello list!

I am trying to construct a map of all intersections within a set of
segments. The naive approach would take O(m²) time - but I'm aiming for
the O(m log m) of the Bentley-Ottmann algorithm.

It seems like the algorithm is implemented in the Sweep_line_2 module of
CGAL [1]. Unfortunately, there is not a lot of documentation about the
Sweep_line_visitor-Concept, which I tried to implement to get the
intersecting segments. Also it seems like I can not access the original
segments from the Sweep_line_visitor callbacks - only the generated
subcurves.

Is there somehow a possibility to get all intersecting segments for each
segment using CGAL? Possibly the easiest solution would be, to pass a
reference of the original segment to the Sweep_line_subcurve and then
access this within the visitor callback - which would require a
modification of the CGAL code as far as I understand it.

Best regards,
Winnie Hellmann

[1]
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Sweep_line_2/Chapter_main.html