Optimal way to iteratively unite 2D triangles

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

Optimal way to iteratively unite 2D triangles

tfmk
Hi, I would like to achieve the best possible performance when iteratively
uniting (2D boolean union) 2D triangles into one larger polygon. I expect to
unite a lot of triangles, so I think that using a BSP tree for the larger
polygon would be useful. I expect CGAL to use BSP trees, but I think that
the default behaviour for CGAL would be to reconstruct the tree every time I
called the CGAL::join() function to add another triangle. What should I do
to avoid reconstructing the BSP tree? I should stress that I have to perform
the unions iteratively - I can't unite them all at once.

Also, given the scenario, is there a faster way to perform this than to use
Polygon_2 for the individual triangles, Polygon_with_holes_2 for the
resulting polygon and then CGAL::join them together? I know there is a class
Triangle_2, but the CGAL::join() doesn't seem to accept it as an input.

Thank you.



--
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: Optimal way to iteratively unite 2D triangles

andreas.fabri

Hello,

And what kind of operation do you perform with the intermediate results?

Best,

Andreas

On 3/16/2019 10:59 PM, tfmk wrote:
Hi, I would like to achieve the best possible performance when iteratively
uniting (2D boolean union) 2D triangles into one larger polygon. I expect to
unite a lot of triangles, so I think that using a BSP tree for the larger
polygon would be useful. I expect CGAL to use BSP trees, but I think that
the default behaviour for CGAL would be to reconstruct the tree every time I
called the CGAL::join() function to add another triangle. What should I do
to avoid reconstructing the BSP tree? I should stress that I have to perform
the unions iteratively - I can't unite them all at once.

Also, given the scenario, is there a faster way to perform this than to use
Polygon_2 for the individual triangles, Polygon_with_holes_2 for the
resulting polygon and then CGAL::join them together? I know there is a class
Triangle_2, but the CGAL::join() doesn't seem to accept it as an input.

Thank you.



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
Reply | Threaded
Open this post in threaded view
|

Re: Optimal way to iteratively unite 2D triangles

Efi Fogel
Hi tfmk,

1. The CGAL::join() function from the 2D Regularized Boolean Operations package has several overloads that accept ranges of polygons, so you can provide all the triangles at once.
2. It uses a mixture of divide-and-conquer and plane-sweep. There is a parameter that kind of controls when to move from divide-an-conquer to plane-sweep. I think it's not documented, but if you look at the code, you will see that there is an additional (last) integral argument with a default value. You can play with it.

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




On Mon, 18 Mar 2019 at 10:15, Andreas Fabri <[hidden email]> wrote:

Hello,

And what kind of operation do you perform with the intermediate results?

Best,

Andreas

On 3/16/2019 10:59 PM, tfmk wrote:
Hi, I would like to achieve the best possible performance when iteratively
uniting (2D boolean union) 2D triangles into one larger polygon. I expect to
unite a lot of triangles, so I think that using a BSP tree for the larger
polygon would be useful. I expect CGAL to use BSP trees, but I think that
the default behaviour for CGAL would be to reconstruct the tree every time I
called the CGAL::join() function to add another triangle. What should I do
to avoid reconstructing the BSP tree? I should stress that I have to perform
the unions iteratively - I can't unite them all at once.

Also, given the scenario, is there a faster way to perform this than to use
Polygon_2 for the individual triangles, Polygon_with_holes_2 for the
resulting polygon and then CGAL::join them together? I know there is a class
Triangle_2, but the CGAL::join() doesn't seem to accept it as an input.

Thank you.



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
Reply | Threaded
Open this post in threaded view
|

Re: Optimal way to iteratively unite 2D triangles

tfmk
In reply to this post by andreas.fabri
The intermediate polygon is subtracted from a triangle (which may or may not
be intersecting the polygon). Then, some other triangles might be subtracted
from the triangle and then the triangle (or rather what remained of it) is
added to the polygon. This process repeats for all triangles.



--
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: Optimal way to iteratively unite 2D triangles

tfmk
In reply to this post by Efi Fogel
Thank you Efi,

I've looked at the code and I found the default parameter 'int k=5'. I will
experiment with the value, but right now I still have to complete some
essential parts of my program to do so.

However, I'm not sure if it allows me to do what I need. What I meant to ask
was if there is any way to obtain intermediate results that the algorithm
creates, and use those results in its later invocations. So for example I
would call CGAL::join() (or similar function) and receive not only the
resulting polygon, but also some data which I could later give by argument
to the next CGAL::join() call, which would help the algorithm perform better
(for example it wouldn't need to "construct the BSP tree again"). I looked
at the code more closely but right now I can't find what I'm looking for.



--
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: Optimal way to iteratively unite 2D triangles

Efi Fogel
The intermediate data is a 2D arrangement.
You can work directly with the arrangement data structure.
For starters, you can create a Polygon_set_2 object, say PS, call the PS.join(range-of-polygons) function, and obtain the underlying arrangement via the call PS.arrangement().

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




On Mon, 18 Mar 2019 at 16:01, tfmk <[hidden email]> wrote:
Thank you Efi,

I've looked at the code and I found the default parameter 'int k=5'. I will
experiment with the value, but right now I still have to complete some
essential parts of my program to do so.

However, I'm not sure if it allows me to do what I need. What I meant to ask
was if there is any way to obtain intermediate results that the algorithm
creates, and use those results in its later invocations. So for example I
would call CGAL::join() (or similar function) and receive not only the
resulting polygon, but also some data which I could later give by argument
to the next CGAL::join() call, which would help the algorithm perform better
(for example it wouldn't need to "construct the BSP tree again"). I looked
at the code more closely but right now I can't find what I'm looking for.



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