Segfault in geos::algorithm::ConvexHull::preSort with extreme outlier

[sgillies]

First reported in ​https://github.com/Toblerity/Shapely/issues/555, I've been able to reproduce it with GEOS 3.5.1 from Debian Stretch.

The user's input has an extreme outlier, the first point:

[(280756800.63603467, 7571780.5096410504),
 (-0.00043553364940478493, -1.1745985126662545e-05),
 (-0.0040809829767810965, -0.00011006076189068978),
 (-0.0041201583341660313, -0.00011111728913462023),
 (-0.006976907320408115, -0.00018816146492247227),
 (-0.0069397726510486172, -0.00018715997340633273),
 (-0.0074676533800189931, -0.000201396483469504),
 (-0.13462489887442128, -0.0036307230426676734),
 (-0.010721780626750072, -0.00028915762480866283),
 (-0.010775949783764172, -0.00029061852246303201),
 (-0.011934357539045426, -0.0003218598289746266),
 (-0.019390152385490519, -0.00052293649740946452),
 (-0.016403812662021146, -0.00044239736574681491),
 (-0.013937679796751739, -0.00037588778618408299),
 (-0.0073628397580766435, -0.00019856974598662623),
 (-0.0013082267409651623, -3.5281801617658642e-05),
 (-0.0019059940589774278, -5.14030956166791e-05)]

(gdb) run test.py
Starting program: /tmp/venv/bin/python3 test.py
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff5240204 in ?? () from /usr/lib/x86_64-linux-gnu/libgeos-3.5.1.so
(gdb) up
#1  0x00007ffff5240a22 in geos::algorithm::ConvexHull::preSort(std::vector<geos::geom::Coordinate const*, std::allocator<geos::geom::Coordinate const*> >&) ()
   from /usr/lib/x86_64-linux-gnu/libgeos-3.5.1.so

If the outlier is removed from the input, the convex hull computation succeeds.

[robe]

Is this an issue in 3.6?

[dbaston]

Yup, crashes PostGIS trunk w/GEOS master. Here is a failing wkb:

01040000001100000001010000002bd3a24002bcb0417ff59d2051e25c4101010000003aebcec70a8b3cbfdb123fe713a2e8be0101000000afa0bb8638b770bf7fc1d77d0dda1cbf01010000009519cb944ce070bf1a46cd7df4201dbf010100000079444b4cd1937cbfa6ca29ada6a928bf010100000083323f09e16c7cbfd36d07ee0b8828bf01010000009081b8f066967ebf915fbc9ebe652abf0101000000134cf280633bc1bf37b754972dbe6dbf0101000000ea992c094df585bf1bbabc8a42f332bf0101000000c0a13c7fb31186bf9af7b10cc50b33bf0101000000a0bba15a0a7188bf8fba7870e91735bf01010000000fc8701903db93bf93bdbe93b52241bf01010000007701a73b29cc90bfb770bc3732fe3cbf010100000036fa45b75b8b8cbf1cfca5bf59a238bf0101000000a54e773f7f287ebf910d4621e5062abf01010000004b5b5dc4196f55bfa51f0579717f02bf01010000007e549489513a5fbfa57bacea34f30abf

[dbaston]

This is apparently fixed with the introduction of the robust orientation index. Added a test case in 36d1c696/git. Not sure if it's feasible to backport anything to 3.6/3.7.