convex_hull of simple polygon returns invalid convex hull

[tobiasmaier]

Expected behavior and actual behavior.

convex_hull should give a valid convex hull.

Input Polygon:

Returned "convex hull":

Note that changing one of the coordinates [0, 1, 3, 4] a little bit leads to an expected convex hull.

Steps to reproduce the problem.

import matplotlib.pyplot as plt
import numpy as np
from shapely.geometry import Polygon

x = [163.29604426963272, 133.88336054231894, 55.360841751097887, 30.360841751097915, 20.26827882848472,
     204.2523809886139, 163.29604426963272]
y = [-0.7051283277805496, 4.933187636462063, 4.933187636462094, 24.778118339507945, 26.712829880088947,
     4.933187636462042, -0.7051283277805496]

poly = Polygon(zip(x, y))
convex_hull_x, convex_hull_y = [z.tolist() for z in poly.convex_hull.exterior.coords.xy]

plt.figure(1)
plt.plot(x, y, '-x')
for idx, (i, j) in enumerate(zip(x, y)):
    plt.text(i, j, str(idx))

plt.figure(2)
plt.plot(convex_hull_x, convex_hull_y)
for idx, (i, j) in enumerate(zip(convex_hull_x, convex_hull_y)):
    plt.text(i, j, str(idx))

plt.show()

Operating system

Linux

Shapely version and provenance

1.6.2post1 installed from PyPI using pip

[sgillies]

@tobiasmaier confirmed on my mac with the same Shapely (and GEOS library) version. This kind of bug drives me nuts. Even without changing coordinate values, I get different results by closing the polygon on a different vertex. Results that are what we'd expect. Check out this code:

import matplotlib.pyplot as plt
import numpy as np
from shapely.geometry import Polygon

x = [163.29604426963272, 133.88336054231894, 55.360841751097887, 30.360841751097915, 20.26827882848472,
     204.2523809886139, 163.29604426963272]
y = [-0.7051283277805496, 4.933187636462063, 4.933187636462094, 24.778118339507945, 26.712829880088947,
     4.933187636462042, -0.7051283277805496]

# Open and close the polygon at the second vertex in the original sequence.
x = x[1:] + [x[1]]
y = y[1:] + [y[1]]

poly = Polygon(zip(x, y))
convex_hull_x, convex_hull_y = [z.tolist() for z in poly.convex_hull.exterior.coords.xy]

plt.figure(1)
plt.plot(x, y, '-x')
for idx, (i, j) in enumerate(zip(x, y)):
    plt.text(i, j, str(idx))

plt.figure(2)
plt.plot(convex_hull_x, convex_hull_y)
for idx, (i, j) in enumerate(zip(convex_hull_x, convex_hull_y)):
    plt.text(i, j, str(idx))

plt.show()

Yields:

and

[sgillies]

@tobiasmaier would you be willing to try downgrading to shapely==1.6.0 to see if this is a new or old GEOS bug? 1.6.0 contains GEOS 3.4.2, while 1.6.2 contains GEOS 3.6.2.

[tobiasmaier]

@sgillies the bug is already in the old GEOS version (3.4.2).
Closing the the shape at a different position seems to only help if it breaks the sequence from 0 to 4. In my original polygon there were much more vertices in between 4 and closing. Using this as a workaround would need some iterations to find the right point.

[sgillies]

Thanks for checking @tobiasmaier . I don't think that moving the closing point is a good work-around, but it's a data point I'll take upstream to the GEOS issue tracker.

[sgillies]

Closing. We've had 5 minor versions of GEOS since. Let's reopen if needed.