CGAL users discussion list

[Valentin Pi <>]

Hello everyone,

I hope this issue fits this list. In our current project we need to compute a lot of small Minkowski sums, and I wanted to ask if someone could please give me some help in speeding that process up. The following CGAL program computing the Minkowski sum of two small polygons demonstrates the problem.

main.cpp:

#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_convex_decomposition_2.h>
#include <CGAL/Polygon_triangulation_decomposition_2.h>
#include <CGAL/minkowski_sum_2.h>

#include <chrono>
#include <iostream>
#include <vector>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Point_2<Kernel> Point;
typedef CGAL::Polygon_2<Kernel> Polygon;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes;

int main(int argc, char** argv) {
    using std::vector;
    using std::chrono::high_resolution_clock;

    vector square_1_points({Point(0, 0), Point(4, 0), Point(4, 4)});
    vector square_2_points({Point(2, 1), Point(3, 1), Point(3, 2)});
    Polygon square_1(square_1_points.begin(), square_1_points.end());
    Polygon square_2(square_2_points.begin(), square_2_points.end());
    auto t1 = high_resolution_clock::now();
    Polygon_with_holes result =
        CGAL::minkowski_sum_2(square_1, square_2, CGAL::Hertel_Mehlhorn_convex_decomposition_2<Kernel>());
    auto t2 = high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count() << "µs" << std::endl;

    return EXIT_SUCCESS;
}

CMakeLists.txt:

cmake_minimum_required(VERSION 3.19.1)
# SotMS: "Slowness of the Minkowski Sum"
project(sotms)
find_package(CGAL 5.6 REQUIRED COMPONENTS Core)

add_compile_options(-O2)
set(CMAKE_BUILD_TYPE Release)

add_executable(sotms src/main.cpp)
target_link_libraries(sotms CGAL::CGAL_Core)

Compilation and execution (move the main.cpp in a folder named src and the CMakeLists.txt in a folder above before):

$ cd src
$ cmake ..
$ make -j
$ ./sotms

I have observed the following:
1. The execution times for CGAL::minkowski_sum_2 for the above program lie around 200µs. This gives room for about 5000 Minkowski sums per second, which is not a lot, given the complexity of the above problem.
2. In the main project we usually have runtimes of about 1500µs. In some executions of our main project program the runtime jumps to several seconds up to minutes, but I cannot reproduce that well yet.
3. Repeating the above code (by introducing a for loop wrapping around the lines 23-27) yields runtimes of about 20µs, but I think this is due to optimizations, but 20µs is still too much.
4. Disabling optimizations (-O0) gives runtimes of about 1000µs for the first Minkowski sum, which then upon repetition of the computation breaks down to about 200µs again for some reason.

I have already tried changing the kernel to an inexact kernel, which still gives poor performance and does not suit our use case, since it often crashes. I am on an Arch Linux (x64) laptop, CGAL is compiled with GMP and MPFR, everything is up to date. The CGAL version in the Arch repository is 5.6

Best
Valentin