search

Oslandia / SFCGAL

MOVED TO GITLAB: https://gitlab.com/sfcgal/SFCGAL. A wrapper around CGAL that intents to implement 2D and 3D operations on OGC standards models
https://sfcgal.org
Other
112 stars 54 forks source link

Crash under sfcgal_geometry_triangulate_2dz / SFCGAL::algorithm::isValid #194

Open Algunenano opened 5 years ago

Algunenano commented 5 years ago

Hi, we've detected a crash from Posgis' ST_ConstrainedDelaunayTriangles which created an sfcgal geometry and calls sfcgal_geometry_triangulate_2dz:

#29 0x00007f30f5783619 in SFCGAL::algorithm::selfIntersectsImpl<2> (line=...) at /usr/include/boost/ptr_container/detail/void_ptr_iterator.hpp:66
#30 0x00007f30f5773286 in SFCGAL::algorithm::selfIntersects (l=...) at /tmp/yaourt-tmp-raul/aur-sfcgal-git/src/sfcgal/src/algorithm/intersects.cpp:503
#31 0x00007f30f5785f1e in SFCGAL::algorithm::isValid (p=..., toleranceAbs=@0x7ffec4a45930: 1.0000000000000001e-09) at /usr/include/c++/9.1.0/bits/stl_vector.h:1058
#32 0x00007f30f57870ff in SFCGAL::algorithm::isValid (mp=..., toleranceAbs=@0x7ffec4a45930: 1.0000000000000001e-09) at /tmp/yaourt-tmp-raul/aur-sfcgal-git/src/sfcgal/include/SFCGAL/MultiPolygon.h:76
#33 0x00007f30f5788a52 in SFCGAL::algorithm::isValid (g=..., toleranceAbs=@0x7ffec4a45930: 1.0000000000000001e-09) at /tmp/yaourt-tmp-raul/aur-sfcgal-git/src/sfcgal/src/algorithm/isValid.cpp:540
#34 0x00007f30f5788be5 in SFCGAL::SFCGAL_ASSERT_GEOMETRY_VALIDITY_ (g=..., ctxt="") at /tmp/yaourt-tmp-raul/aur-sfcgal-git/src/sfcgal/src/algorithm/isValid.cpp:63
#35 0x00007f30f5788c58 in SFCGAL::SFCGAL_ASSERT_GEOMETRY_VALIDITY (g=...) at /usr/include/c++/9.1.0/bits/char_traits.h:300
--Type <RET> for more, q to quit, c to continue without paging--
#36 0x00007f30f5788d91 in SFCGAL::SFCGAL_ASSERT_GEOMETRY_VALIDITY_2D (g=...) at /tmp/yaourt-tmp-raul/aur-sfcgal-git/src/sfcgal/src/algorithm/isValid.cpp:92
#37 0x00007f30f5987951 in SFCGAL::triangulate::triangulate2DZ (g=..., triangulation=...) at /tmp/yaourt-tmp-raul/aur-sfcgal-git/src/sfcgal/src/triangulate/triangulate2DZ.cpp:112

The call appears in SFCGAL::algorithm::selfIntersects, which looks very similar to https://github.com/Oslandia/SFCGAL/issues/171 that is still crashing for me.

Versions:

Full callstack from Postgis: bt.txt Full geometry WKT: geom.txt

lbartoletti commented 4 years ago

Confirmed on FreeBSD with SFCGAL 1.3.7 cgal 5.0.2 boost 1.72

Error with SELECT ST_ConstrainedDelaunayTriangles(ST_GeomFromEWKT(...)):

CGAL error: precondition violation!
Expression : is_simple_2(first, last, traits)
File       : /usr/local/include/CGAL/Polygon_2/Polygon_2_algorithms_impl.h
Line       : 510
Explanation: 
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
NOTICE:  During triangulate_2d(A) :
NOTICE:    with A: MULTIPOLYGON(((6598827514628421/8589934592 3814349091280397/536870912,6601303672940447/8589934592 7628535277308075/1073741824,3301064529522225/4294967296 7628486405732253/1073741824,6602520031409511/8589934592 238389351714275/33554432,1650879795752275/2147483648 7628220327152807/1073741824,1651107862965225/2147483648 3814112878663951/536870912,412828552372807/536870912 953504462649965/134217728,6604040479495839/8589934592 7627818494196095/1073741824,1650955818156591/2147483648 7627726181219557/1073741824,6603692948504677/8589934592 7627655588943377/1073741824,6605517486208277/8589934592 3813808788858867/536870912,6605865017199439/8589934592 7627378650013741/1073741824,3303453805086463/4294967296 476709468696143/67108864,6608210851389779/8589934592 476704717292939/67108864,6608167410015889/8589934592 1906755064614439/268435456,6609948506345591/8589934592 1906700762863533/268435456,1652476266242923/2147483648 238335389349311/33554432,1652476266242923/2147483648 953323909328199/134217728,826341306384463/1073741824 476653130629577/67108864,6608819030624315/8589934592 7625988525190519/1073741824,6606733844677341/8589934592 7626026536416151/1073741824,3302693581043295/4294967296 1906548717960991/268435456,6603084769270149/8589934592 7626004815715793/1073741824,1650163013083003/2147483648 3812980687157533/536870912,412516317497935/536870912 238302638605795/33554432,6599783224854111/8589934592 7625537820657985/1073741824,3300412908913799/4294967296 7625445507681447/1073741824,1650043549304793/2147483648 7625326043829445/1073741824,3300000215861793/4294967296 1906323365694727/268435456,824918601389395/1073741824 3812622295601543/536870912,6599305369741261/8589934592 3812603289988727/536870912,3299587522809787/4294967296 238283802685949/33554432,6598566866385047/8589934592 7625070825600189/1073741824,3298740416018835/4294967296 7625054535074915/1073741824,3298327722966829/4294967296 1906206616930275/268435456,6595612852960171/8589934592 7624793886670563/1073741824,3297567498923661/4294967296 7624783026320373/107
ERROR:  CGAL ERROR: precondition violation!
Expr: is_simple_2(first, last, traits)
File: /usr/local/include/CGAL/Polygon_2/Polygon_2_algorithms_impl.h
Line: 510
lbartoletti commented 4 years ago

@sloriot Can you take a look at this issue since the error is reported by CGAL? Do you want me to open a ticket upstream?

mhugo commented 4 years ago

@lbartoletti CGAL warns that one of its precondition is violated. So there is high chance the problem is in SFCGAL which calls a CGAL function without respecting this precondition.

Besides, @Algunenano 's initial crash seems to refer to a problem in selfIntersectsImpl (comparing Points), which seems different from yours. Do you have a full stack trace to compare ?

sloriot commented 4 years ago

A non simple polygon is basically a polygon that has some self-intersections (it can be an intersection in the interior of edges or a pinching)

sloriot commented 4 years ago

What's surprizing is that the triangulation should be able to handle it (with the valid flag) but anyway this assertion comes from before calling the triangulation I think.