Closed jmetz closed 10 years ago
This works for me with SciPy 0.12.0. Which version are you using?
Also 0.12.0. The issue is being caused by the call to qhull, perhaps my version has a bug that has since been fixed... I have qhull version (2009.1-3) (from ubuntu 13.04 repos).
I just upgraded to scipy 0.13.2, and also found that scipy 0.12.0 was also using qhull 2012.1 2012/02/18 (as is 0.13.2) - so it's not an old qhull bug... But I get the same error regardless.
The full qhull error message is:
Success on cropped
Success on Expanded and shifted
QH6228
Qhull internal error (qh_findbestlower): all neighbors of facet 3 are flipped or upper Delaunay.
Please report this error to qhull_bug@qhull.org with the input and all of the output.
ERRONEOUS FACET:
- f3
- flags: top simplicial upperDelaunay
- normal: -0.6912 -0.654 0.3075
- offset: 1043.28
- vertices: p156(v3) p5(v2) p78(v0)
- neighboring facets: f26 f17 f7
While executing: | qhull d Qbb Qz Qc Qt
Options selected for Qhull 2012.1 2012/02/18:
run-id 535251457 delaunay Qbbound-last Qz-infinity-point Qcoplanar-keep
Qtriangulate _pre-merge _zero-centrum Qinterior-keep Pgood _max-width 11
Error-roundoff 1.3e-12 _one-merge 9.4e-12 Visible-distance 2.7e-12
U-coplanar-distance 2.7e-12 Width-outside 5.4e-12 _wide-facet 1.6e-11
Last point added to hull was p97.
At error exit:
Delaunay triangulation by the convex hull of 157 points in 3-d:
Number of input sites and at-infinity: 12
Number of nearly incident points: 12
Number of Delaunay regions: 0
Statistics for: | qhull d Qbb Qz Qc Qt
Number of points processed: 12
Number of hyperplanes created: 39
Number of facets in hull: 20
Number of distance tests for qhull: 1308
precision problems (corrected unless 'Q0' or an error)
11 coplanar points during partitioning
Traceback (most recent call last):
File "convex_hull_error.py", line 37, in <module>
chull_im = skmo.convex_hull_image(imageBig)
File "/usr/local/lib/python2.7/dist-packages/scikit_image-0.9dev-py2.7-linux-x86_64.egg/skimage/morphology/convex_hull.py", line 55, in convex_hull_image
chull = Delaunay(coords).convex_hull
File "qhull.pyx", line 1701, in scipy.spatial.qhull.Delaunay.__init__ (scipy/spatial/qhull.c:13548)
File "qhull.pyx", line 323, in scipy.spatial.qhull._Qhull.__init__ (scipy/spatial/qhull.c:3592)
scipy.spatial.qhull.QhullError: Qhull error
I've found a workaround; as the full error implies this is a precision issue, so I tried subtracting the mean as follows and it works (NB as well as subtracting the mean a full fix should probably scale the set of points into [-1,1]).
My temporary fix is essentially:
# skimage/morphology/convex_hull.py line 53
# Find the convex hull
offset = coords.mean(axis=0)
coords -= offset
chull = Delaunay(coords).convex_hull
v = coords[np.unique(chull)]
# Sort vertices clock-wise
v_centred = v - v.mean(axis=0)
angles = np.arctan2(v_centred[:, 0], v_centred[:, 1])
v = v[np.argsort(angles)]
# Add back here
v += offset
As I hinted, as well as subtracting the offset, a full fix would possibly also scale ( ~ /= coords.max(axis=0)
) though this could introduce other issues.
I'm going to wait and see if anyone else confirms this bug before submitting the patch...
Is this a bug in QHull, or is that expected behavior?
I don't know enough to be sure; but I also submitted a query to qhull_bug@qhull.org . I'd consider it a bug given the results from the test code, at least for the purposes of scikit-image.
This has also been reported here: https://gist.github.com/automata/5447635, so I'm going to put in a pull request with my workaround.
I came across the following bug when calling
convex_hull_objects
, which I found was caused by a call toconvex_hull_image
on one of the labelled objects.Below is a minimal(ish) snippet to reproduce the error.
I get