CGAL users discussion list

[Efi Fogel <>]

Indeed, Arrangement_with_history_2 is a generic data structure that you can use to solve the problem.

Define an object of a type that is an instance of Arrangement_with_history_2<Traits, Dcel>. Then, insert all the curves into the arrangement. Finally, iterate over the vertices of the arrangement. You can query the degree of a visited vertex to filter out vertices associated with non-intersection points. Also, you can obtain the incident edges to get the inducing curves.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On 8 November 2017 at 19:01, Nicolas CHARVIN <> wrote:

Hello,

[Disclaimenr: I am a brand new CGAL user, and C++ isn't my main programming language]

I am currently performing simulation on nanowires networks.
So, within a large number N of random segments, I need to detect for each segment which segments it is intersecting.
Naive implementation works well, but of course in O(N2).

I wish I could use sweepline algorithms to perform this way faster, as described in the example "sweep_line.cpp". It works really fast (up to 100,000 segments) but unfortunately, "compute_intersection_points" only return the intersections points, not the two segments involved.

Searching in the list, I found that some people need the same thing in 2012: https://sympa.inria.fr/sympa/arc/cgal-discuss/2012-11/msg00149.html

It has been told in the thread that "Arrangement_with_history_2" might do the trick. But I have no idea what it means.

Does anyone have any hints to help ?

Regards,
Nicolas

--

	Nicolas CHARVIN Laboratoire LEPMI - équipe LMOPS / Bât Helios, 60 av du Lac Leman - 73370 Le Bourget du Lac +33 4 79 75 87 91

www.univ-smb.fr

	Un geste simple pour l'environnement, n'imprimez ce message que si vous en avez l'utilité.