CGAL users discussion list

[Efi Fogel <>]

If so, then use the decomposition Minkowski-sum method, with a nop decomposition operation; see https://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__nop__decomposition__2.html

Try something like this:

Polygon_with_holes result = CGAL::minkowski_sum_2(square_1, square_2, CGAL::Polygon_nop_decomposition_2<Kernel>());

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, 9 Jan 2024 at 12:58, Valentin Pi <> wrote:

Yes, I just checked. Would be surprising to me if not, since there are unique coordinates for each triangle in the code.

Am 09.01.24 um 11:31 schrieb Efi Fogel ( via cgal-discuss Mailing List):

Do you have any guarantee about the input polygons being convex?

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, 9 Jan 2024 at 10:41, Valentin Pi <> wrote:

Thanks for the quick reply.
1. I have now tried a couple of versions, but only from the header-only versions. Denoted with the tag names each, I give the following table of observed average times. The numbers I gave initially were with v5.6, as already said.

Release tag - Observed average runtime
6.0-dev [1] - 200µs
       v5.6 - 200µs
       v5.5 - 185µs
       v5.4 - 275µs
       v5.3 - 300µs
       v5.2 - 275µs
       v5.1 - 250µs

[1] The current version at commit a15af8ef645c414956640348d036609b9a0a5c38.

I do not detect a degradation with any particular version, except for a slight jump from 275µs to 185µs between v5.4 and v5.5. For the complexity of the problem anything over a couple of µs is too much for our application, so all of these times are problematic for us. I could try older versions if you think it would make a difference.
2. I have tried convolution (in v5.6) and it gives about the same time.

Am 09.01.24 um 08:10 schrieb Efi Fogel ( via cgal-discuss Mailing List):

1. Have you measured it with a different version? I mean, are you detecting a degradation?

2. Have you tried other implemented alg, or at least other decomposition methods?

The call without a decomposition method invokes the partial-convolution method, which is the most efficient in most cases:

CGAL::minkowski_sum_2(square_1, square_2);

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, 9 Jan 2024 at 01:09, Valentin Pi <> wrote:

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

--
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

--
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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss