minkowski_sum has fatal bug for some special linestring and polygon

[Garbage123King]

Issue Details

./main
CGAL version: 6.0.0
terminate called after throwing an instance of 'CGAL::Assertion_exception'
what(): CGAL ERROR: assertion violation!
Expr: sl_iter != m_statusLine.end()
File: /usr/local/include/CGAL/Surface_sweep_2/No_intersection_surface_sweep_2_impl.h
Line: 547
adopted

Source Code

// main.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/minkowski_sum_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes_2;

int main() {
        std::cout << "CGAL version: "
              << CGAL_VERSION_MAJOR << "."
              << CGAL_VERSION_MINOR << "."
              << CGAL_VERSION_PATCH << std::endl;
    // Define a simple polygon (first geometry)
    Polygon_2 P;
    P.push_back(K::Point_2(824, 627));
    P.push_back(K::Point_2(689, 555));

    // Define another simple polygon (second geometry)
    Polygon_2 Q;
    Q.push_back(K::Point_2(130, 150));
    Q.push_back(K::Point_2(20, 40));
    Q.push_back(K::Point_2(50, 60));
    Q.push_back(K::Point_2(125, 100));

    // Compute Minkowski sum (correct type)
    Polygon_with_holes_2 sum = CGAL::minkowski_sum_by_full_convolution_2(P, Q);

    // Output result (just an example)
    std::cout << "Minkowski sum computed successfully." << std::endl;

    return 0;
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Linux 64bits
• Compiler: g++ or MSVC
• Release or debug mode: debug mode raise error, release mode crush
• Specific flags used (if any):
• CGAL version: 6.0, or 5.6, or 5.0 all have problem
• Boost version: 1.71 or 1.73
• Other libraries versions if used (Eigen, TBB, etc.):

[efifogel]

Use an exact construction kernel. ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

…

On Wed, 16 Oct 2024 at 07:06, Garbage123King ***@***.***> wrote: Issue Details ./main CGAL version: 6.0.0 terminate called after throwing an instance of 'CGAL::Assertion_exception' what(): CGAL ERROR: assertion violation! Expr: sl_iter != m_statusLine.end() File: /usr/local/include/CGAL/Surface_sweep_2/No_intersection_surface_sweep_2_impl.h Line: 547 adopted Source Code // main.cpp #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/minkowski_sum_2.h> #include <CGAL/Polygon_2.h> #include <CGAL/Polygon_with_holes_2.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Polygon_2 Polygon_2; typedef CGAL::Polygon_with_holes_2 Polygon_with_holes_2; int main() { std::cout << "CGAL version: " << CGAL_VERSION_MAJOR << "." << CGAL_VERSION_MINOR << "." << CGAL_VERSION_PATCH << std::endl; // Define a simple polygon (first geometry) Polygon_2 P; P.push_back(K::Point_2(824, 627)); P.push_back(K::Point_2(689, 555)); // Define another simple polygon (second geometry) Polygon_2 Q; Q.push_back(K::Point_2(130, 150)); Q.push_back(K::Point_2(20, 40)); Q.push_back(K::Point_2(50, 60)); Q.push_back(K::Point_2(125, 100)); // Compute Minkowski sum (correct type) Polygon_with_holes_2 sum = CGAL::minkowski_sum_by_full_convolution_2(P, Q); // Output result (just an example) std::cout << "Minkowski sum computed successfully." << std::endl; return 0; } Environment - Operating system (Windows/Mac/Linux, 32/64 bits): Linux 64bits - Compiler: g++ or MSVC - Release or debug mode: debug mode raise error, release mode crush - Specific flags used (if any): - CGAL version: 6.0, or 5.6, or 5.0 all have problem - Boost version: 1.71 or 1.73 - Other libraries versions if used (Eigen, TBB, etc.): — Reply to this email directly, view it on GitHub <#8551>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOFFN7ZZQWS26J3KCQTZ3XQ27AVCNFSM6AAAAABQAQRRNOVHI2DSMVQWIX3LMV43ASLTON2WKOZSGU4TANJUGU4TINQ> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[Garbage123King]

it's the same after the changes

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
typedef CGAL::Exact_predicates_exact_constructions_kernel K;

terminate called after throwing an instance of 'CGAL::Assertion_exception'
what(): CGAL ERROR: assertion violation!
Expr: sl_iter != m_statusLine.end()
File: /usr/local/include/CGAL/Surface_sweep_2/No_intersection_surface_sweep_2_impl.h
Line: 547
adopted

[sloriot]

P contains only 2 points so it's not a valid polygon.

[Garbage123King]

I somehow simplified the numbers of the test case, hoping it helps.

// main.cpp
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/minkowski_sum_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes_2;

int main() {
    // Define a simple polygon (first geometry)
    Polygon_2 P;
    P.push_back(K::Point_2(0, 0));
    P.push_back(K::Point_2(30, 16));

    // Define another simple polygon (second geometry)
    Polygon_2 Q;
    Q.push_back(K::Point_2(0, 0));
    Q.push_back(K::Point_2(5, 10));
    Q.push_back(K::Point_2(20, 18));
    Q.push_back(K::Point_2(20, 50));

    // Compute Minkowski sum (correct type)
    Polygon_with_holes_2 sum = CGAL::minkowski_sum_by_full_convolution_2(P, Q);

    // Output result (just an example)
    std::cout << "Minkowski sum computed successfully." << std::endl;

    return 0;
}

It looks like this:

The linestring is parallel to one edge of the polygon

[Garbage123King]

P contains only 2 points so it's not a valid polygon.

I don't know, but it's how SFCGAL use to calculate the minkowski_sum of linestring and polygon, it makes sense on math, and it works well with other linestrings and polygons.

SFCGAL-v1.5.0/src/algorithm/minkowskiSum.cpp:

void minkowskiSum( const LineString& gA, const Polygon_2& gB, Polygon_set_2& polygonSet )
{
    if ( gA.isEmpty() ) {
        return ;
    }

    int npt = gA.numPoints() ;

    for ( int i = 0; i < npt - 1 ; i++ ) {
        Polygon_2 P;
        P.push_back( gA.pointN( i ).toPoint_2() );
        P.push_back( gA.pointN( i+1 ).toPoint_2() );

        //
        // We want to compute the "minkowski sum" on each segment of the line string
        // This is not very well defined. But it appears CGAL supports it.
        // However we must use the explicit "full convolution" method for that particular case in CGAL >= 4.7
#if CGAL_VERSION_NR < 1040701000 // version 4.7
        Polygon_with_holes_2 part = minkowski_sum_2( P, gB );
#else
        Polygon_with_holes_2 part = minkowski_sum_by_full_convolution_2( P, gB );
#endif

        // merge into a polygon set
        if ( polygonSet.is_empty() ) {
            polygonSet.insert( part );
        }
        else {
            polygonSet.join( part );
        }
    }
}

[Garbage123King]

I believe I find it has problem with _convolution_cycle() in Minkowski_sum_conv_2.h
It can't simplify the circle completely
I will submit a commit to fix this.

before:

antenna equal check: 0 0 30 16; 30 16 35 26; line: -16 30 -0; -10 5 220; opp_nl: 10 -5 -220
antenna equal check: 30 16 35 26; 35 26 5 10; line: -10 5 220; 16 -30 220; opp_nl: -16 30 -220
antenna equal check: 35 26 5 10; 5 10 20 18; line: 16 -30 220; -8 15 -110; opp_nl: 8 -15 110
They are equal!
antenna equal check: 20 18 50 34; 50 34 50 66; line: -16 30 -220; -1 0 50; opp_nl: 1 -0 -50
antenna equal check: 50 34 50 66; 50 66 20 50; line: -1 0 50; 16 -30 1180; opp_nl: -16 30 -1180
antenna equal check: 50 66 20 50; 20 50 0 0; line: 16 -30 1180; 50 -20 -0; opp_nl: -50 20 -0
antenna equal check: 20 50 0 0; 0 0 30 16; line: 50 -20 -0; -16 30 -0; opp_nl: 16 -30 -0

after:

antenna equal check: 0 0 30 16; 30 16 35 26; line: -16 30 -0; -10 5 220; opp_nl: 10 -5 -220
antenna equal check: 30 16 35 26; 35 26 5 10; line: -10 5 220; 16 -30 220; opp_nl: -16 30 -220
antenna equal check: 35 26 5 10; 5 10 20 18; line: 16 -30 220; -8 15 -110; opp_nl: 8 -15 110
They are equal!
antenna equal check: 35 26 20 18; 20 18 50 34; line: 8 -15 110; -16 30 -220; opp_nl: 16 -30 220
They are equal!
antenna equal check: 35 26 50 34; 50 34 50 66; line: -8 15 -110; -1 0 50; opp_nl: 1 -0 -50
antenna equal check: 50 34 50 66; 50 66 20 50; line: -1 0 50; 16 -30 1180; opp_nl: -16 30 -1180
antenna equal check: 50 66 20 50; 20 50 0 0; line: 16 -30 1180; 50 -20 -0; opp_nl: -50 20 -0
antenna equal check: 20 50 0 0; 0 0 30 16; line: 50 -20 -0; -16 30 -0; opp_nl: 16 -30 -0