cgal
cgal copied to clipboard
CGAL
minkowski_sum has fatal bug for some special linestring and polygon
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.):
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 https://github.com/CGAL/cgal/issues/8551, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABVBNOFFN7ZZQWS26J3KCQTZ3XQ27AVCNFSM6AAAAABQAQRRNOVHI2DSMVQWIX3LMV43ASLTON2WKOZSGU4TANJUGU4TINQ . You are receiving this because you are subscribed to this thread.Message ID: @.***>
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
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
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 );
}
}
}
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