ST_StraightSkeleton hangs on input

[robe2]

I compiled 1.3.x branch using CGAL 4.11 to try to see if this issue might have been fixed already,

I still get hanging even using branch of 1.3.x. Others have complained about cpu exhaustion with lower SFCGAL.

https://lists.osgeo.org/pipermail/postgis-devel/2018-January/026844.html

SELECT ST_StraightSkeleton('POLYGON((256 760,518 760,518 630,674 630,674 239,673 239,127 239,127 240,126 240,126 513,127 513,127 514,126 514,126 630,255 630,256 630,256 760),(128 629,128 423,270 423,270 422,271 422,271 240,672 240,672 629,128 629),(258 759,258 631,516 631,516 759,258 759),(128 421,128 240,269 240,269 421,128 421))'::geometry);

Same issue with /ST_ApproximateMedialAxis which I guess is expected since it's a wrapper around ST_StraightSkeleton.

[darkblue-b]

with pg10/sfcgal 1.3x, open a postgis database SELECT postgis_full_version(); SELECT postgis_sfcgal_version(); to load libs, then SELECT pg_backend_pid() to get a pid ; next, in a root terminal invoke gdb; (gdb) attach <pid>; Notice the symbol information load. In the other terminal, execute the problem SQL. I attempted the following, but no break occurred (?):

(gdb) set breakpoint pending on
(gdb) br sfcgal_geometry_straight_skeleton
(gdb) br sfcgal_straight_skeleton
(gdb) br SFCGAL::algorithm::straightSkeleton

[darkblue-b]

gdb break fixed:
rebuilt postgis 2.4.3 with ./configure --enable-debug CFLAGS='-Og';
Repeat the steps for pid.

(gdb) info sharedlibrary
(gdb) br sfcgal_version()
(gdb) continue

then in the target database, execute SELECT postgis_sfcgal_version(); Notice the breakpoint;
Similarly, the following does break into gdb upon a ST_StraightSkeleton() sql call;

(gdb) br SFCGAL::algorithm::straightSkeleton

[darkblue-b]

debug log:

(gdb) br SFCGAL::algorithm::straightSkeleton Breakpoint 1 at 0x7f29def30450 (8 locations) (gdb) continue Continuing.

Breakpoint 1, 0x00007f29def53190 in SFCGAL::algorithm::straightSkeleton(SFCGAL::Geometry const&, bool, bool, bool)@plt () from /usr/local/lib/libSFCGALd.so.1

(gdb) bt
#0 0x00007f29def53190 in SFCGAL::algorithm::straightSkeleton(SFCGAL::Geometry const&, bool, bool, bool)@plt ()
from /usr/local/lib/libSFCGALd.so.1
#1 0x00007f29df7cb986 in sfcgal_geometry_straight_skeleton (ga=0x55f581d42e70)
at /home/shared/srcs_xdrii/sfcgal_misc/SFCGAL-1.3.0/src/capi/sfcgal_c.cpp:762
#2 0x00007f29e08a6398 in sfcgal_straight_skeleton () from /usr/lib/postgresql/10/lib/postgis-2.4.so
#3 0x000055f58006ad9f in ?? ()
#4 0x000055f580113997 in ?? ()

(gdb) step
287 SFCGAL_ASSERT_GEOMETRY_VALIDITY_2D( g );
(gdb) explore g
The value of 'g' is a struct/class of type 'const SFCGAL::Geometry' with the following fields:

validityFlag_ = false .. (Value of type 'bool')

(gdb) list
282 }
283 }
284
285 std::auto_ptr< MultiLineString > straightSkeleton( const Geometry& g, bool autoOrientation, bool innerOnly, bool outputDistanceInM )
286 {
287 SFCGAL_ASSERT_GEOMETRY_VALIDITY_2D( g );
288
289 std::auto_ptr result( straightSkeleton( g, autoOrientation, NoValidityCheck(), innerOnly, outputDistanceInM ) );
290 propagateValidityFlag( *result, true );
291 return result;
(gdb) br SFCGAL::algorithm::straightSkeleton:289
Note: breakpoint 1 also set at pc 0x7f29df432ff0.
Note: breakpoint 1 also set at pc 0x7f29df433233.
Note: breakpoint 1 also set at pc 0x7f29df433340.
Note: breakpoint 1 also set at pc 0x7f29df433617.
Note: breakpoint 1 also set at pc 0x7f29def30450.
Note: breakpoint 1 also set at pc 0x7f29def37fe0.
Note: breakpoint 1 also set at pc 0x7f29def53190.
Note: breakpoint 1 also set at pc 0x7f29def62b80.
Breakpoint 2 at 0x7f29def30450 (8 locations)
(gdb) continue
Continuing.

Breakpoint 1, 0x00007f29def30450 in SFCGAL::algorithm::straightSkeleton(SFCGAL::Geometry const&, bool, SFCGAL::algorithm::NoValidityCheck, bool, bool)@plt () from /usr/local/lib/libSFCGALd.so.1

(gdb) list *$pc
0x7f29df432fcd is in SFCGAL::algorithm::straightSkeleton(SFCGAL::Geometry const&, bool, SFCGAL::algorithm::NoValidityCheck, bool, bool) (/home/shared/srcs_xdrii/sfcgal_misc/SFCGAL-1.3.0/src/algorithm/straightSkeleton.cpp:269).
264
265 ///
266 ///
267 ///
268 std::auto_ptr< MultiLineString > straightSkeleton( const Geometry& g, bool autoOrientation, NoValidityCheck, bool innerOnly, bool outputDistanceInM )
269 {
270 switch ( g.geometryTypeId() ) {
271 case TYPE_TRIANGLE:
272 return straightSkeleton( g.as< Triangle >().toPolygon(), autoOrientation, innerOnly, outputDistanceInM ) ;
273
(gdb) continue ## 3x here

oooo experiment with signals oooo

Program received signal SIGTERM, Terminated.
boost::optional_detail::optional_base<CGAL::Line_2<CGAL::Simple_cartesian<CGAL::Interval_nt > > >::optional_base (this=0x7fffad5df530, val=...) at /usr/include/boost/optional/optional.hpp:255
255 optional_base ( argument_type val )
(gdb) continue
Continuing.

Program received signal SIGINT, Interrupt.
0x00007f29df46e328 in boost::intrusive_ptr<CGAL::CGAL_SS_i::Trisegment_2<CGAL::Simple_cartesian<CGAL::Interval_nt > > >::swap (this=0x7fffad5df540, rhs=...) at /usr/include/boost/smart_ptr/intrusive_ptr.hpp:184
184 px = rhs.px;
(gdb) continue
Continuing.

Program received signal SIGTERM, Terminated.
0x00007f29defe6557 in CGAL::operator* (a=..., b=...) at /usr/include/CGAL/Interval_nt.h:576
576 return IA(-CGAL_IA_MUL(aa, -b.inf()), CGAL_IA_MUL(bb, b.sup()));
(gdb) cont
Continuing.

Program received signal SIGCONT, Continued.
0x000055f5801a41f0 in die ()
(gdb) continue
Continuing.

Program received signal SIGQUIT, Quit.
CGAL::internal::In_place_list_const_iterator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::Straight_skeleton_vertex_base_2<CGAL::HalfedgeDS_list_types<CGAL::Epick, CGAL::Straight_skeleton_items_2, std::allocator >, CGAL::Point_2CGAL::Epick, double> >, std::allocator<CGAL::HalfedgeDS_in_place_list_vertex<CGAL::Straight_skeleton_vertex_base_2<CGAL::HalfedgeDS_list_types<CGAL::Epick, CGAL::Straight_skeleton_items_2, std::allocator >, CGAL::Point_2CGAL::Epick, double> > > >::In_place_list_const_iterator (this=0x55f581dedb80, i=...)
at /usr/include/CGAL/In_place_list.h:139
139 In_place_list_const_iterator( Iterator i) : node(&*i) {}
(gdb) quit

[darkblue-b]

the core loop that never completes may be function:
Straight_skeleton_builder_2() in Straight_skeleton_builder_2_impl.h

notes on How to Kill a PostgreSQL Process -LINK-

[lbartoletti]

@robe2

Confirmed on windows with SFCGAL 1.3.7 / CGAL 4.14.3 / postgis 3.0.1

But it works (c)(tm) on FreeBSD with SFCGAL 1.3.7 / CGAL 5.0 / postgis 3.0.1