CGAL users discussion list

[Graviton <>]

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]> 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]

> <mailto:[hidden email]>> 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]
Developer mailing list: [hidden email]

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

---

View this message in context: Re: Get the overlapped face info for multiple arrangements
Sent from the cgal-discuss mailing list archive at Nabble.com.