CGAL users discussion list

[Bruno Silva <>]

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