CGAL users discussion list

[Guillaume Damiand <>]

Hi Bruno;

Instead of inserting each segment successively, insert them "simultaneously" using the following insert free function:
https://doc.cgal.org/latest/Arrangement_on_surface_2/group__PkgArrangementOnSurface2Insert.html#ga744ea4ef5e40e521af139e106b6480f8

The complexity of the global method is almost in O(nlogn), while it is O(n^2) for the other solution.

cf. also https://doc.cgal.org/latest/Arrangement_on_surface_2/index.html#title68

Best
Guillaume



Le 05/11/2021 à 13:37, Bruno Silva a écrit :

        Hi Andreas,

Now, I've put this code on gist.github.com: https://gist.github.com/BrunoRammon/c2850f4aef513571ba27e69773c5d3eb

                      arrangementInsertion.cpp
                    
                      GitHub Gist: instantly share code, notes, and
                      snippets.
                    
                      gist.github.com

Best,

Bruno

---

De: em nome de Andreas Fabri
Enviado: sexta-feira, 5 de novembro de 2021 06:51
Para: Bruno Silva ( via cgal-discuss Mailing List)
Assunto: Re: [cgal-discuss] Speeding Up Arrangement Insertion

 

Hello,

Ideally, you put code on gist.github.com

 

Best,

Andreas

On 11/5/2021 12:39 PM, Bruno Silva ( via cgal-discuss Mailing List) wrote:

Just sending the code once again with some small changes:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

#include <CGAL/Arr_naive_point_location.h>

#include <CGAL/Arr_non_caching_segment_basic_traits_2.h>

#include <CGAL/Segment_2.h>

#include <CGAL/Arr_segment_traits_2.h>

#include <CGAL/Arrangement_2.h>

#include <CGAL/Delaunay_triangulation_2.h>

#include <CGAL/Constrained_Delaunay_triangulation_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel                       K1;

typedef CGAL::Arr_segment_traits_2<K1>                                          Traits_2;

typedef CGAL::Arrangement_2<Traits_2>                                           Arrangement_2;

typedef CGAL::Delaunay_triangulation_2<K1>                                      Delaunay2;

typedef CGAL::Constrained_Delaunay_triangulation_2<K1, CGAL::Default, Itag>     CDT2;

typedef Traits_2::Point_2                                                       Point_2;

typedef Traits_2::X_monotone_curve_2                                            Segment_2;

typedef CGAL::Arr_naive_point_location<Arrangement_2>                           WalkPL_2;

int main()

{

    ExternalDataSet datas("data1.txt","data2.txt");

   

    Arrangement_2 arr;

    WalkPL_2 walkPL(arr);

    // first step of insertions

    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();

    std::vector<Segment_2> segmentSet1 = datas.externalData(0);

    CGAL::insert_non_intersecting_curves(arr, segmentSet1.begin(), segmentSet1.end());

    segmentSet1.clear();

    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

    if (verbose) std::cout << "Time spent - First Insertion: " << std::setprecision(6) << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count()/1.0e+6 << std::fixed << " sec." << std::endl;  

   

    //Second step of insertions

    begin = std::chrono::steady_clock::now();

    std::vector<Segment_2> segmentSet2 = datas.externalData(1);

    // #pragma omp parallel for if(_parallelOptimization)

    for(auto seg = segmentSet2.begin(); seg < segmentSet2.end(); ++seg)

    {

        CGAL::insert(arr, *seg, walkPL);

    }

    segmentSet2.clear();

    end = std::chrono::steady_clock::now();

    if (verbose) std::cout << "Time spent - Second Insertion: " << std::setprecision(6) << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count()/1.0e+6 << std::fixed << " sec." << std::endl;  

   

    CDT2 cdt;

    // Constrained Delaunay package to triangulate the arrangement

    begin = std::chrono::steady_clock::now();

    for (auto it = arr.edges_begin(); it != arr.edges_end(); ++it) {

        cdt.insert(it->source()->point(), it->target()->point());

    }

    end = std::chrono::steady_clock::now();

    if (verbose) std::cout << "Time spent - Creation of the Constrained Delaunay Triangulation: " << std::setprecision(6) << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count()/1.0e+6 << std::fixed << " sec." << std::endl;  

}

-------

Att, 

Bruno Rammon Silva Souza

---

De: Bruno Silva
Enviado: sexta-feira, 5 de novembro de 2021 06:20
Para: <>
Assunto: Speeding Up Arrangement Insertion

 

            Hi everyone,

I'm having a problem with efficiency when computing arrangements by CGAL. Thus, I would like to know whether there's any way to improve the efficiency of this.

The code is:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

#include <CGAL/Arr_naive_point_location.h>

#include <CGAL/Arr_non_caching_segment_basic_traits_2.h>

#include <CGAL/Segment_2.h>

#include <CGAL/Arr_segment_traits_2.h>

#include <CGAL/Arrangement_2.h>

#include <CGAL/Delaunay_triangulation_2.h>

#include <CGAL/Constrained_Delaunay_triangulation_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel                       K1;

typedef CGAL::Arr_segment_traits_2<K1>                                          Traits_2;

typedef CGAL::Arrangement_2<Traits_2>                                           Arrangement_2;

typedef CGAL::Delaunay_triangulation_2<K1>                                      Delaunay2;

typedef CGAL::Constrained_Delaunay_triangulation_2<K1, CGAL::Default, Itag>     CDT2;

typedef Traits_2::Point_2                                                       Point_2;

typedef Traits_2::X_monotone_curve_2                                            Segment_2;

typedef CGAL::Arr_naive_point_location<Arrangement_2>                           WalkPL_2;

int main()

{

    ExternalDataSet datas("data1.txt","data2.txt");

    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();

    std::vector<Segment_2> segmentSet1 = datas.externalData(0);

    CGAL::insert_non_intersecting_curves(arr, segmentSet1.begin(), segmentSet1.end());

    segmentSet1.clear();std::chrono::steady_clock::time_point

   

    end = std::chrono::steady_clock::now();

    if (verbose) std::cout << "Time spent - First Insertion: " << std::setprecision(6) <<          std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count()/1.0e+6 << std::fixed << " sec." << std::endl;

   

    // Insertion of the second set of segments

    begin = std::chrono::steady_clock::now();

    std::vector<Segment_2> segmentSet2 = datas.externalData(1);

    // #pragma omp parallel for //Parllellization is not working!!

    for(auto seg = segments1.begin(); seg < segments1.end(); ++seg)

    {

        CGAL::insert(arr, *seg, walkPL);

    }

    segmentSet2.clear();

   

    end = std::chrono::steady_clock::now();

    if (verbose) std::cout << "Time spent - Second Insertion: " << std::setprecision(6) << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count()/1.0e+6 << std::fixed << " sec." << std::endl;  

   

    // Section 2 - It is using the constrained Delaunay package to triangulate the arrangement vertices and constrained edges

    begin = std::chrono::steady_clock::now();

    for (auto it = arr.edges_begin(); it != arr.edges_end(); ++it) {

        CDT.insert(it->source()->point(), it->target()->point());

    }

    end = std::chrono::steady_clock::now();

    if (verbose) std::cout << "Time spent - Creation of the Constrained Delaunay Triangulation: " << std::setprecision(6) << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count()/1.0e+6 << std::fixed << " sec." << std::endl;  

}

I have two distinct sets of segments (std::vector<Segment_2> segmentSet1 and std::vector<Segment_2> segmentSet2 ) that comes up from external data. The segments in segmentSet1 don't intersect with others segments in this set. This is also true for the segments in segmentSet2. However, the segments in segmentSet1 certainly intersects with the segments in segmentSet2.

I insert the first set of segments by the function CGAL::insert_non_intersecting_curves(arr, segmentSet1.begin(), segmentSet1.end()). The insertions of the second set of segments are performed by the function CGAL::insert(arr, *seg, walkPL). The efficiency first intersection is pretty good, but the second one is very inefficient. After these insertions, a Constrained Delaunay Triangulation is created.

I would like to know whether there is a way to improve the efficiency of this second insection. I've tried without success to perform a parallelization of the loop in the second insertion.

Is there any way to parallelize this for-loop for the second insertion? Or should I try another approach to improve the overall efficiency?

-------

Best, 

Bruno Souza

            -- 
            You are currently subscribed to cgal-discuss.
            To unsubscribe or access the archives, go to
            https://sympa.inria.fr/sympa/info/cgal-discuss
            
          
        
-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project
        
          
          -- 
          You are currently subscribed to cgal-discuss.
          To unsubscribe or access the archives, go to
          https://sympa.inria.fr/sympa/info/cgal-discuss
          
        
      
      
        -- 
        You are currently subscribed to cgal-discuss.
        To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        
      
    
    
    
-- 
===================================================================
Guillaume DAMIAND

CNRS - LIRIS UMR 5205
Université Claude Bernard
Bâtiment Nautibus (710)
43 Boulevard du 11 Novembre 1918
69622 Villeurbanne Cedex (France)
-------------------------------------------------------------------
Tél: +33 (0)4.72.43.14.34                 Fax: +33 (0)4.72.43.15.36
Mail: 
Web: http://liris.cnrs.fr/guillaume.damiand/
===================================================================

Attachment: smime.p7s
Description: Signature cryptographique S/MIME