# Optimal way to iteratively unite 2D triangles

6 messages
Open this post in threaded view
|

## Optimal way to iteratively unite 2D triangles

 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
Open this post in threaded view
|

## Re: Optimal way to iteratively unite 2D triangles

 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```
Open this post in threaded view
|

## Re: Optimal way to iteratively unite 2D triangles

 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```
Open this post in threaded view
|

## Re: Optimal way to iteratively unite 2D triangles

 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