CGAL users discussion list

[Efi Fogel <>]

It uses the sweep, so its complexity is O((n+k)log(n))

The single insert uses the zone, so its complexity is O(n^2).

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

On 12 July 2018 at 17:14, Benjamin Streitz <> wrote:

Thx. I think https://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2curve_history_8cpp-example.html is an even better example which I found originating from your example, assuming one doesn't want to define an observer.

One more question about performance. Does this approach have the same performance of O((n+k)log(n)) as the sweep algorithm itself or is that only true for a single insert() operation?

> Efi Fogel <> hat am 12. Juli 2018 um 12:29 geschrieben:

>
>
> Consider constructing a 2d-arrangement induced by the curves (using the
> aggregate insert() free function, which is based on the surface-sweep
> framework).
> In particular, construct an object the type of which is an instance of
> Arrangement_with_history_2, or extend the arrangement to your needs and use
> an observer to update the extended data (see, e.g., the face_extension.cpp
> example of the Arrangement_on_surface_2 package).
> All the information you mention can be extracted from the arrangement
> object.
>
> ____ _ ____ _
> /_____/_) o /__________ __ //
> (____ ( ( ( (_/ (_/-(-'_(/
> _/
>
>
>
> On 12 July 2018 at 13:14, brainslush <> wrote:
>
> > I have a list of segments and want to determine where and with what
> > other segments they are intersecting unsing the sweep algorithm.
> > The part for obtaining the intersection positions is straight forward
> > from the tutorial / example.
> > https://doc.cgal.org/latest/Surface_sweep_2/index.html
> >
> > What steps would I have to take to obtain the the segments/curves
> > involed in the intersection?
> >
> > Kind Regards,
> > Benjamin
> >
> >
> >
> >
> > --
> > Sent from: http://cgal-discuss.949826.n4.nabble.com/
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://sympa.inria.fr/sympa/info/cgal-discuss
> >
> >
> >
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss
>
>