Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Slow Performance when Computing the Minkowski Sum of two Simple Squares

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Slow Performance when Computing the Minkowski Sum of two Simple Squares


Chronological Thread 
  • From: Efi Fogel <>
  • To:
  • Subject: Re: [cgal-discuss] Slow Performance when Computing the Minkowski Sum of two Simple Squares
  • Date: Tue, 9 Jan 2024 09:10:53 +0200
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-data: A9a23:/9ezsq+uWD5yffQ24KL7DrUDTnuTJUtcMsCJ2f8bNWPcYEJGY0x3m DNKDG/QP//YZ2anedl1bIqx9hlQ6pfcndZkTwdsqCpEQiMRo6IpJ/zJdxaqZ3v6wu7rFR88s Z1GMrEsCOhuExcwcz/0auCJQUFUjP3OHPymYAL9EngZbRd+Tys8gg5Ulec8g4p56fC0GArlV ena+qUzA3f7nWYoWo4ow/jb8k835ayj4GpwUmEWPJingneOzxH5M7pEfcldH1OgKqFIE+izQ fr0zb3R1gs1KD9wYj8Nuu+TnnwiGtY+DyDW4pZlc/TKbix5m8AH+v1T2Mzwxqtgo27hc9hZk L2hvHErIOsjFvWkdO81C3G0H8ziVEHvFXCuzXWX6KSuI0P6n3TEx/ZjVWobYaIk1MFNH29w0 sdIEmhXYUXW7w626OrTpuhEg80iKIz2NdpatC09iz7eCvkiTNbIRKCiCd1whm9hwJATW6yEP YxFNFKDbzyYC/FLEloZCZw5k+qsrnb6ejxc7lmSoMLb5kCKkFEsi+a8boC9ltqiHp1RnmrE5 Vj6rm3bUhoQCYG/0iei2yf57gPItWahMG4IL5Wz+fduxVGS3WcOEwY+Tkq+ufD/i0ikWtsZJ VZ8x8Y1ha079UjuU9CkGhPk/TiLuRkTX9cWGOo/gO2Q9pfpD8+iLjBsZlZ8hBYO7afanBRzj gXXzeD6TydiqqOUQn+7/7KZ52H6cysMIGNIIWdOQQIZ6pOx6Ms+nzDefOZFSaSVt9zSHS2v4 jaoqCNlua4fo/RW3IqG/HfGoQmWmL73ciAP6D76ZFmVtjFCWNb9ZqiDy0Tq0vJbHYPIEniDp Cclnuad3sAvDLaMtiqHf8sVFpr05fzfaDz4qnxsFqkH6D6C1SOCf4dRwTcmP2ZvEJ8OVgHIa X/pmzF6xcFsLlrzSoRocaedNt8M8ZHwMfjECtXFcctoYLVqUQ2MoRFVek+b2l7ynHgWka0QP YmRdeCuBy04DZtL4SWXReAP960C3QE7mH3uQK7kwySd0baxYGCfTZEHOgCsasE79Ka1nxXHw e1ANselywRtb8OmW3P5qbUsFFEtKWQ3IbvUqMYNL+6KHVdAKVEbUvTUxessRpxhk6Frjdz3x 3CaWHJD6V/BlHbCeBSraHdiVevVZqxBj0kHZA4iAVX5/EIYQ9eLzLwefJ4Jb7UY5LRd7fprf cIkJeSEINpyEwrixRpMTKPAvLRDdQuqjz2gJyCKQiYyVL8+Sh3r+u3LRBrO9i4PBBWZrcEV+ uSR6i7Hc5g6HiBnANjcMv60/Wjsv3JHwONWdGnLK+l1Z0/D3tVLKSvwr/lvOOAKC0zJ6QW73 jasIyUzhLfysaoq1tjWlIa4r4uNOMlvLHpwRmX0w+6/CnjHwzCF34RFbtetQRncc2HFoIOZe uRfyqDHAs0txVplndJ1LOd28PgY+dDqmr59yzZkFlXta3CAKOtpAluC7Pl1mpx9/J1rkiroZ RvX4fhfA6uDB+39Gl1IJAYFUPWK5ctJphbst8YKMGfIzw4p2oGYUHdiHQiG0w1cC7pXDLkL4 8kcvOwu1gjurSZyb/iniHhP+nWuP04wdfwtlqsnDb/BjispzVB/YqLgNBLm3aHXVfJyNhgFH zzFoovDmLVW+WTaeVURC3Xm/LRQlLYOij9w3X4AIFW7wIPFj8AowSwLoCgWTxtU/DpDwelcK mhmDGwrBKSsrhNDptlPYHCoIC5FXCamw03Wz0AYslHWVGy6fzXpAFBlHN2S7Wc11nl5fAlL2 J25k0HbCS3LeuP11QsMAX9VkeTpF4FNx1eTifKZENSgNLhkRCjunYuFR3cC8jnjCuMP3Hz3n /FgprtMWPeqJBwrgvMJDqeB3u4tUzGCHmtJRM9h8I4vHW3xfDKT2yCEG3uue/FiduD7zkulN /NAfs5/dQyy9CKrnAApAaQhJ7xVnvlwwPEgfrjtB3ANsprBjz5Pna/TyBPDhz4Qc40zqfo+F 4LfSWvTWCjYz35ZgHTEo8R4K3K1K4tMLhH12Oeutv4FDdQfueVrals/yaawo27TCgZ84haIp 0nWUsc6FQC5JVhExOMA05mvBjlY7fv2XeWMtR266pFAMY6JPsDJuAcY7FLgOmy6+FfXt8tfz dywXBzfhSspf4ral0jWnpCAE+9C4sDasC9/LJfsNHcD9cedcJaE3vbAklxU7bRGldpc4o+sQ A7QhA5cszIKc481+UC5oBSy3/rQ52obo0sgSe6AQyywNyUg
  • Ironport-hdrordr: A9a23:KD83fqF03bO4sr3wpLqE0ceALOsnbusQ8zAXPiFKOGVom6mj/f xG885rsCMc5AxhOk3I3OrwW5VoIkm8yXcW2/h0AV7KZmCP01dAbrsD0WKI+UyGJ8SRzJ866U 6iScRD4R/LYGSSQfyU3OBwKbgd/OU=
  • Ironport-phdr: A9a23:F7SBJBTOoRkfHn5L0XYj7gDX99psotCWAWYlg6HPa5pwe6iut67vI FbYra00ygOTDcOBtqIP0rKM+4nbGkU+or+580o+OKRWUBEEjchE1ycBO+WiTXPBEfjxciYhF 95DXlI2t1uyMExSBdqsLwaK+i764jEdAAjwOhRoLerpBIHSk9631+ev8JHPfglEnjWwba1xI RmsswnctsobjYR/Jqot1BfCv2dFdflRyW50Kl2fmArx6N238JB/7Spbpugv99RHUaX0fqQ4S aJXATE7OG0r58PlqAfOQxKX6nQTTmsZnBxIAxPY7B7hRZf+rjH6tutm1yaEO8D9UK05Vi6j7 6dvTx/olTsHOjsk+2zZlsB8kKRWqw+nqhdiwYDbfZuVOeJxcaPTf9wURWRPUMVMWSJfHoyxd JEAA/YbMOtCs4Xxu1kDoB2jDgesHuPvzTpIi2f506000uQqDAHI3AsvH90QtHTfsdL4O7kcU eC0wqnIyjrDYO1S2Trm54jIdwouofCIXb5qbcXRzkwvGhrDg16NpoPrIymb2f4Rs2iH8eVgT +SvhnYlpg1vvDSixtshhIbGi48axF7I6yd0zog1K9C7TEN2bsOoHZtRui+aN4V7Q8MsT31nt ionyrALuZG1cTQWxZkowRPUdvKJc4+N4h35VeaRJy91hHNjeLKlhha961KsyuPmVsSyzV1Er TJFn8HSunwR0xHf8MuKR/tn8ku/xzqDyRrf5+5ELE0yiKHWNZohwqMrlpoPr0vDBDL4mET3j aCIbkgo5u6l4Pn9bLr8vJ+TLYp0hxn+Mqswnsy/Bvw1Mg0UUGia/eSwzaDj8lfkTLlTgP07n anUvIrVJcQcoa65DAtV3Zg55xmjCDem1cwUnXgBLF1bZBKKl5blN03KLfziDvqyg06gnCl1y /zYJLHsDZXAImDGkLj7fLZ970BcyBA0zdBa/59bFL8BIPP9Wk/2u9zXEBs5Phe7w+biEtp91 4ceVXiTDa+eNaPeqVmI6fk3LOmWeIAVoCr9K+Qi5/P2kHM1gUUdcrWx3ZsLdHC4GexrLFmWY XX2htcNCHoFvgslTOP2lV2CSiVTam2pX6M84zE7EJipAZ3CRoCrmryB3T20EodYZmBcWRixF 2z1fdCER+sUc3DVZdRwlyQNE7mnUY4okx+08xTrzqJuaevS9Cpfvp3q0J155vbYiAoppgFyF NmX832ISzR0gn8QXG1xm7tupFR0jFaFy6lxxfJCUsdC4utAFQY8O5mbxONzD5X+WxnKY8ySG 2ugWcisPTwhUocx38MWeBQ6XM6ziwjKmSusGb4c0bKRQ4cl97rVmHn3KcE6wHnP0OwtjkItX 9BUZlGh06Vw/gyWC4/SmFiCjI6rc74d1WjD7jSt122L6WxWUUZeVqrIWThLa0XXo9P260fqQ LqnCLBhOQxEn53RYpBWY8Hk2A0VDMzoP87TNjrZcwaYAB+JwunJd4/2YyAH2y6bDkEYkgcV9 HLANA4kBy7nrXiNRCd2GwfJZEXhufJ7tGv9VlU9mgyEbkNm2Lex0hEQjP2YDfgU2+FMoz8v/ g19B031xNfKE5yFrgtlcr9bZIYw7lZJ0m3UsyRyO5WhK+ZpgVtNOx9vsRbI0BN6Qp5FjdBsr H4uy19qLrmE1Vpaaz6C9ZX5O7mSN2CruR7zNujZ3VbR1NvQ8aAKgBghg3PkugzhVk8r8nE9l sJQz2PZ/JLBSgwbTZP2VE8zsRl8vbDTJCcntcvS0jV3PK+4vyWnuZphDfY5yhumY9ZUMb+VX A70HcoAAsGyKess01G3ZxMANepW+eY6JcSjP/eB3aeqOq5nklfExSxK7oFz1U2B8wJzT+fJ2 9AOxPTZlgqLWjHgjUuw59jtkNMMbjUTE2yjjCn8UdQJN+siIMBRUz3of5Dko7c2z4TgUHNZ6 lO5UlYP2cvzPAGXc0S4xwpbk0IevX2gnyK8iT1yiTAg6KSFj0msi6zvcgQKPmlTSSxsl1Dpd MK5gdEUW0elayAmkRKk4QDxwK0R98EdZyHDBFxFeST7NTQoX6WxuL2Nbspn55YhsCERW+O5K wPSWvv2pB0U1DnmFm1VyWUgdj2kjZ7+mgRzlGOXKHsbQGPxQchr3l+f4dXdQaQUxT8aXGxij jKRAFGgPt6v9NHSlpHZs+n4WXjzHpFUdCDqy8uHuk7ZrSVnDxyxmP++nvXoFAE71Wnw0NwiW SjTrRn6a5XmzOzgabMhLhQuXgWmrZYnUohl2pM9npQRxWQXivD3tTIcnGH/PM8akaPyYXwRR CIaltvc4QzrwkpmfTqCw4P0UGnYw9M0PYHrJDNLnHhntYYWVfTxjvQMhyZ+r1umoBiEZPF8m m1Y0v4y8DsAhOpPvgMxzyKbC7RUHE9CPCWqmQ7birL25KhRemurdqC9kURkmtX0RryMow9bV 3v9UpgnFC50qM54NRiftR+7opGhY9TWYd8J41eZnRbOiOdYLLo+k/MLgWxsPme37jU1juU8i xJpx5SzuoOKfn5s8KyOCRldLjTpZskX92KI7+4WjoOM0ouoBJkkBiQTUc6iU6ezCDxL/6evJ 0OUHTY7sHveBbfPAVrV9hJ9t3yWdvLjf3CPeCtCkJM7FUHbfhAAxlhTBmlyn4ZlRF72gpa6K wEguGhXvhmh+1NN0r46aUe5Cz+F4l/uMnBuEP39ZFJX9l0QuRmTa5DPqLIrWXkfpMXprRTRe DPBIV0USzhYAArcQAmzdri2uYufr67BXLf4d72WJuzQzI4WH/aQmcD2itsgpmnTcJXJZj44V rU6whYRBC8iXZ2Ix3NXDXRQznyFbtbH9k3kq2sn84bmqqStAEW2uu7tQ/NTKYk9oUnox/rTc bfB3mAhbm8JnpIUmS2SkeZZhgVDzXo0MWHqSOVIoyfJSOi4drZ/KRkdZmszMcJJ6/h5xQxRI YvBjdiz0Ldkj/kzAlMDVFr7m8jva9ZYa2e6fEjKAkqGLtHkbXXC3t33bKWgSLZRkPQcthu+v iyeGlPiOTLLnifgVhSmO+VBxC+BOxkWtIa4exdrQW/tKbCuIgW8K8NyhCYqzKccg3rLMSsBO GE5fR8Q6LKX6ixcj7N0HGkApntpIO+YmjqIuunVLpFF1JkjSi9wlu9c/DE70+4PtHACFKEzw nGI6IIz8DTE2qGVxzFqUQRDsGNOjYOP5wB5PLnBs4NHUjDC9Q4M6mOZD1ILocFkA5vhofM1q JCHmaTtJTNF69+R89EbAp2eJcyGPn0uPB7BFzvdDQ9DRjmufzK65QQVgLSJ+3uZo4Jv4IDrg 4YLQ6RHWUYdE/obDgF4FYVHLssqGDwjlrGfgYgD4n/0/3yzDI1K+5vAUPyVG/DmLj2U2KJFa xU/yrT9NY0PN4f/1iSKi3F/lYXOXlfZBJVD/nAnYQgzr0FAtnN5Sz9rs6oAQgyo6X4XU/Wzm 0xu4uORSeso/TbopVwwIwiTzBY=
  • Ironport-sdr: 659cf194_ODUnu0edM/PJ4gQlDlbe+zRpeinOXFCGT/kDvqrf6U8UO/p vJB6vQ2taz+d5MBHSq53CKnfW+XcSH7qkFOzcGA==

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




Archive powered by MHonArc 2.6.19+.

Top of Page