CGAL users discussion list

[Efi Fogel <>]

Hi Valentin,

I've decided to look into it, cause the timings seemed odd, and I found a few things.

I'm running an i7 core clocked at 2.20GHz:

cat /proc/cpuinfo  | grep 'name'| uniq
model name : Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz

I changed the single call to a loop and added the traits parameter.

I get ~20us on average on my machine per minkowski sum.

However, even with this I wasn't satisfied.

It turns out that there is some overhead that consumes some unexplained significant amount of time.

Attached is a patch that avoids (some of) the overhead.

It applies to 2 files:

modified:   Minkowski_sum_2/include/CGAL/Minkowski_sum_2/Minkowski_sum_decomp_2.h
modified:   Minkowski_sum_2/include/CGAL/minkowski_sum_2.h

It is based on the most recent version, so if the automatic application of the patch fails for you, apply it manually. It is rather simple.

Also, make sure to use the following snippet:

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Point = CGAL::Point_2<Kernel>;
using Container = std::vector<Point>;
using Arr_segment_traits = CGAL::Arr_segment_traits_2<Kernel>;
using Traits = CGAL::Gps_segment_traits_2<Kernel, Container, Arr_segment_traits>;

using Nop = CGAL::Polygon_nop_decomposition_2<Kernel, Container>;

Traits traits;

CGAL::minkowski_sum_by_decomposition_2(square_1, square_2, nop, traits);

which knocks out almost ~2/3 of the computation time, and I get ~7us.

Naturally, I'll continue to investigate the issue and fix the code base.

Best,

Efi

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

On Tue, 9 Jan 2024 at 19:22, Valentin Pi <> wrote:

You are right, I didn't try that yet. This cuts about 25µs of the runtime to about 175µs.

Am 09.01.24 um 15:57 schrieb Efi Fogel ( via cgal-discuss Mailing List):

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

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

diff --git a/Minkowski_sum_2/include/CGAL/Minkowski_sum_2/Minkowski_sum_decomp_2.h b/Minkowski_sum_2/include/CGAL/Minkowski_sum_2/Minkowski_sum_decomp_2.h
index bc3d4eb1441..a1db335211e 100644
--- a/Minkowski_sum_2/include/CGAL/Minkowski_sum_2/Minkowski_sum_decomp_2.h
+++ b/Minkowski_sum_2/include/CGAL/Minkowski_sum_2/Minkowski_sum_decomp_2.h
@@ -250,11 +250,25 @@ public:
    * \return The resulting polygon with holes, representing the sum.
    */
   Polygon_with_holes_2
-  operator()(const Polygon_2& pgn1, const Polygon_2& pgn2) const
+  operator()(const Polygon_2& pgn1, const Polygon_2& pgn2,
+             bool is_convex = false) const
   {
     CGAL_precondition(pgn1.is_simple());
     CGAL_precondition(pgn2.is_simple());
 
+    if (is_convex) {
+      Polygon_2 pgn;
+      _compute_sum_of_convex(pgn1, pgn2, pgn);
+      General_polygon_set_2 gps(*m_traits);
+      gps.join(pgn);
+      Arrangement_2& arr = gps.arrangement();
+      simplify(arr);
+      Polygon_with_holes_list sum;
+      gps.polygons_with_holes(std::back_inserter(sum));
+      CGAL_assertion(sum.size() == 1);
+      return sum.front();
+    }
+
     // Decompose both input polygons to convex sub-polygons.
     Polygons_list sub_pgns1;
     Polygons_list sub_pgns2;
@@ -347,7 +361,7 @@ public:
     return (*(sum.begin()));
   }
 
-private:
+public:
   /*! Merge mergeable edges
    * \param arr (in) The underlying arrangement.
    */
@@ -370,6 +384,7 @@ private:
     }
   }
 
+public:
   /*!
    * Compute the Minkowski sum of two convex polygons.
    * \param pgn1 The first convex polygon.
diff --git a/Minkowski_sum_2/include/CGAL/minkowski_sum_2.h b/Minkowski_sum_2/include/CGAL/minkowski_sum_2.h
index 7a782893e30..70b89605010 100644
--- a/Minkowski_sum_2/include/CGAL/minkowski_sum_2.h
+++ b/Minkowski_sum_2/include/CGAL/minkowski_sum_2.h
@@ -772,7 +772,7 @@ minkowski_sum_by_decomposition_2
       Minkowski_sum_by_decomposition_2<Nop_decomposition, Nop_decomposition,
                                        Container>
         mink_sum(decomp_nop, decomp_nop, traits);
-      return mink_sum(pgn1, pgn2);
+      return mink_sum(pgn1, pgn2, true);
     }
     Minkowski_sum_by_decomposition_2<Nop_decomposition, Decomposition,
                                      Container>