CGAL users discussion list

[Ben Supnik <>]

I am not sure.  My original point was only that overlay is not good for 
the very rare case where one of the arrangements is trivial and the 
other is huge.

For multiple general arrangements, it might be faster to merge several 
at once, but as far as I know CGAL doesn't provide that "off the shelf"; 
the boolean operations code can do it - it "overlays" 5 (by default) 
arrangements at once - if given 10 it "overlays" 5 and 5 and then 
overlays the results.

But to get that for the general overlay case you'd have to write your 
own sweep visitor, which is quite complex (unless CGAL added this and I 
missed it) so perhaps overlay and then overlay the results (for log 2 
overlays) is best.

cheers
Ben

On 7/3/12 8:47 AM, Graviton wrote:
> Thanks Ben, are you saying that by overlaying one arrangement with
> another, and get the resulting arrangement to overlay with another
> arrangement, and repeat this until the very last arrangement, this is
> the best algorithm for my use case?
>
>
> On Tue, Jul 3, 2012 at 8:44 PM, Ben Supnik [via cgal-discuss] <[hidden
> email] </user/SendEmail.jtp?type=node&node=4655349&i=0>> wrote:
>
>     Hi Y'all,
>
>     Assuming "efficient" means lowest time complexity, overlay is best for
>     the general case.
>
>     The only exception I found: if one arrangement has a much larger number
>     of half-edges than the other _and_ you can accept that the first
>     arrangement be altered, it's quicker to insert the second arrangement's
>     edges into the first and rebuild the face information.
>
>     But the difference in size has to be _really extreme_, and if the size
>     difference really is extreme the edges have to be inserted individually
>     (because the bulk edge inserted is going to do something quite similar
>     to a full overlay).
>
>     I hit this case when intersecting a single polygon (with perhaps 20 or
>     30 sides) into an arrangement with on the order of a million edges.
>
>     For two large arrangements "overlay" is really quite good!!
>
>     cheers
>     Ben
>
>     On 7/3/12 3:51 AM, Efi Fogel wrote:
>
>      > On Tue, Jul 3, 2012 at 10:34 AM, Graviton <[hidden email]
>     <http://user/SendEmail.jtp?type=node&node=4655348&i=0>
>      > < email]
>     <http://user/SendEmail.jtp?type=node&node=4655348&i=1>>> wrote:
>      >
>      >     I have a number of
>      >
>     
> http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Arrangement_2/Chapter_main.html
>      >     arrangements  with vertices v, edges e and faces f. I tag
>     each face
>      >     in each
>      >     of the arrangement properly (e,g, {A} face means that the
>     face is
>      >     inside the
>      >     arrangement A)
>      >
>      >     Now, I want to overlay all these arrangements together, and
>     for the
>      >     resulting arrangement, I want each face will have a tag of
>     the original
>      >     arrangements. How to do this? My idea is that I want to use
>      >
>     
> http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Arrangement_2_ref/Function_overlay.html#Cross_link_anchor_811
>      >     overlay  function for the first two arrangements to find a
>     resulting
>
>      >     arrangement, and use the overlay on the resulting arrangement
>     and third
>      >     arrangements, and so on.
>      >
>      >     But do we have a more efficient way of working?
>      >
>      >
>      > No.
>      >
>      >
>      >
>      >
>      >     --
>      >     View this message in context:
>      >
>     
> http://cgal-discuss.949826.n4.nabble.com/Get-the-overlapped-face-info-for-multiple-arrangements-tp4655345.html
>      >     Sent from the cgal-discuss mailing list archive at Nabble.com.
>
>      >
>      >     --
>      >     You are currently subscribed to cgal-discuss.
>      >     To unsubscribe or access the archives, go to
>      > https://lists-sop.inria.fr/wws/info/cgal-discuss
>      >
>      >
>      >
>      >
>      > --
>      >     ____  _        ____             _
>      >    /_____/_) o    /__________  __  //
>      >   (____ (   (    (    (_/ (_/-(-'_(/
>      >                           _/
>      >
>      >
>      >
>     --
>     Scenery Home Page: http://scenery.x-plane.com/
>     Scenery blog: http://www.x-plane.com/blog/
>     Plugin SDK: http://www.xsquawkbox.net/xpsdk/
>     X-Plane Wiki: http://wiki.x-plane.com/
>     Scenery mailing list: [hidden email]
>     <http://user/SendEmail.jtp?type=node&node=4655348&i=2>
>     Developer mailing list: [hidden email]
>     <http://user/SendEmail.jtp?type=node&node=4655348&i=3>
>
>
>
>     --
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
>
>     ------------------------------------------------------------------------
>     If you reply to this email, your message will be added to the
>     discussion below:
>     
> http://cgal-discuss.949826.n4.nabble.com/Get-the-overlapped-face-info-for-multiple-arrangements-tp4655345p4655348.html
>
>     To unsubscribe from Get the overlapped face info for multiple
>     arrangements, click here.
>     NAML
>     
> <http://cgal-discuss.949826.n4.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>
>
>
>
> ------------------------------------------------------------------------
> View this message in context: Re: Get the overlapped face info for
> multiple arrangements
> <http://cgal-discuss.949826.n4.nabble.com/Get-the-overlapped-face-info-for-multiple-arrangements-tp4655345p4655349.html>
> Sent from the cgal-discuss mailing list archive
> <http://cgal-discuss.949826.n4.nabble.com/> at Nabble.com.

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://www.x-plane.com/blog/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: