CGAL users discussion list

[Ben Supnik <>]

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 
> <
> <mailto:>>
>  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: 

Developer mailing list: