Sweep algorithm return intersecting segments

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Sweep algorithm return intersecting segments

brainslush
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


Reply | Threaded
Open this post in threaded view
|

Re: Sweep algorithm return intersecting segments

Efi Fogel
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 <[hidden email]> 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



Reply | Threaded
Open this post in threaded view
|

Re: Sweep algorithm return intersecting segments

brainslush
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 <[hidden email]> 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 <[hidden email]> 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
>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Sweep algorithm return intersecting segments

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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
>
>