convex_hull crash

[PokerChang]

Please note

If you are reporting an installation or module import issue, please note that
this project only accepts reports about problems with packages downloaded from
the Python Package Index. Conda users should take issues to one of the
following trackers:

• https://github.com/ContinuumIO/anaconda-issues/issues
• https://github.com/conda-forge/shapely-feedstock

Expected behavior and actual behavior.

Actual: Segmentation fault
Expected: no crash
(For example: the area of my geometry is 1.417 when it should be 1.414.)

Steps to reproduce the problem.

(For example, a script with required data)
from shapely.geometry import MultiPoint
output =[(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)]
output_convex = MultiPoint(output).convex_hull

Operating system

(For example, Mac OS X 10.12.3)
Linux 4.9.0-5-amd64

Shapely version and provenance

1.6.3 installed using pip
(For example, 1.6b4 installed from PyPI using pip)

[sgillies]

@PokerChang I created a Debian Stretch container using Docker to test this. I can reproduce the error. It's not a Shapely bug, however, but a problem with the GEOS library. It seems to be precision related.

The first point in the output list is an extreme outlier from the others. I removed it and the program runs without problem. With the outlier there is indeed a crash. The gdb program shows:

(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

I don't see a crash with the outlier on my Mac.

My recommendation: to work around this issue, do whatever you can to exclude extreme outliers when you compute a convex hull.

[PokerChang]

Thanks for looking into this! Could you please open an upstream bug or keep this one open?

[sgillies]

Upstream ticket: https://trac.osgeo.org/geos/ticket/850