sgillies/shapely — Issue #19: convex_hull not behaving as expected
Author: tomiskou
Created: 2011-11-03 00:10:49+00:00
State: open

Hey,
I believe I found a bug. I need to construct a convex hull of a set of points and so I create a MultiPoint out of those points and call .convex_hull on it. Unfortunately, I believe the result of that call is incorrect, i.e. convex hull created doesn't contain all the points from the MultiPoint.

To reproduce the bug, I am attaching a short script (listed below). Trying to minimize the dependences, it provides only a text output. After reading the output, it would appear that only first ~10 points are taken into account during the construction of the convex hull. The behaviour is the same if I call .convex_hull on LineString constructed out of these points.

I am able to produce the same result on two different systems:
1st system runs Ubuntu 9.10 32-bit with python 2.6.4, shapely 1.0.12, libgeos 3.1.0, ctypes =1.1.0 (all installed from standard 9.10 packages)
2nd system runs Scientific Linux 4.6 32-bit with python 2.7.1, shapely 1.2.13, libgeos 3.3.1 and ctypes = 1.1.0 (all except the OS itself was compiled from sources)

If you need more info, let me know!

Thanks!
T.

```python
#!/usr/bin/env python

from shapely.geometry import MultiPoint, LineString

a = [(2678.760220242234, 1.3225619205235399),
(2725.1850158373895, 2.8225076260934374),
(2771.6098114325446, 4.8519984423855265),
(2818.0346070277001, 6.2105633284913013),
(2864.4594026228551, 6.8169878130638084),
(2910.8841982180106, 7.3383136523649561),
(2957.3089938131661, 7.587796064763646),
(3003.7337894083212, 7.7371969492039803),
(3050.1585850034767, 7.6649924765776092),
(3096.5833805986317, 7.5898586425359538),
(3143.0081761937872, 7.3745938421814374),
(3189.4329717889423, 7.1421445871900628),
## the following points are commented only to shorten the print statement output
## uncommenting them doesn't affect the result, though
# (3235.8577673840978, 6.8596857592765614),
# (3282.2825629792533, 6.5929509128819275),
# (3328.7073585744083, 6.2034182801245281),
# (3375.1321541695638, 5.8981528140300661),
# (3421.5569497647193, 5.6028867539678906),
# (3467.9817453598744, 5.2397937610780847),
# (3514.4065409550299, 4.9144906210205326),
# (3560.8313365501849, 4.6732127811220483),
# (3607.2561321453404, 4.2973526941694766),
# (3653.6809277404955, 4.0209337777323411),
# (3700.105723335651, 3.697198303045341),
# (3746.5305189308065, 3.4642599188106087),
# (3792.9553145259615, 3.1938778016061367),
# (3839.380110121117, 2.9429908153875686),
# (3885.8049057162725, 2.7260364129684032),
# (3932.2297013114276, 2.4730509886473051),
# (3978.6544969065826, 2.3088032778714815),
# (4025.0792925017381, 2.0968243666911119),
# (4071.5040880968936, 1.9280425194737563),
# (4117.9288836920487, 1.769548652451312),
# (4164.3536792872037, 1.6029157340961189),
# (4210.7784748823597, 1.4789421129459561),
# (4257.2032704775147, 1.3552202650004883),
# (4303.6280660726698, 1.2220322148528033),
# (4350.0528616678257, 1.1205496084886686),
# (4396.4776572629808, 1.018959176809874),
# (4442.9024528581358, 0.9298570960008794),
# (4489.3272484532918, 0.85553096720831612),
# (4535.7520440484468, 0.77865550267667538),
# (4582.1768396436019, 0.70818117461063446),
# (4628.6016352387578, 0.64244122341871057),
# (4675.0264308339129, 0.58514965693027832),
# (4721.4512264290679, 0.54072488551177689),
# (4767.8760220242239, 0.48732196869559735),
# (4814.300817619378, 0.44723937114163953),
# (4860.725613214534, 0.41091539987403153),
# (4907.150408809689, 0.37011977461396273),
# (4953.575204404844, 0.33661709099703813),
(5000.0, 0.30753352517602206)]

mp = MultiPoint(a)
ls = LineString(a)

print "original sequence of points", a
print "convex hull of a MultiPoint", [p for p in mp.convex_hull.exterior.coords]
print "convex hull of a LineString", [p for p in ls.convex_hull.exterior.coords]
```