CGAL users discussion list

[Bruno Silva <>]

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