7

I am trying to create a Convex Hull using the library Scipy and ConvexHull. As far as I know, it calls QHull.

The problem appears when the points I want to add do not have 'full dimension'. Example:

from scipy.spatial import ConvexHull
import numpy as np
points = np.append([[0,2]],[[2,0]],axis=0)
hull = ConvexHull(points)

Has for output:

Traceback (most recent call last):
  File "C:/folder/vertices_scipy2.py", line 5, in <module>
hull = ConvexHull(points)
  File "scipy\spatial\qhull.pyx", line 2230, in scipy.spatial.qhull.ConvexHull.__init__ (scipy\spatial\qhull.c:20317)
  File "scipy\spatial\qhull.pyx", line 328, in scipy.spatial.qhull._Qhull.__init__ (scipy\spatial\qhull.c:3639)
QhullError: Qhull error

However, if I add an extra points, so that the convex hull has full dimension:

from scipy.spatial import ConvexHull
import numpy as np
points = np.append([[0,0],[0,2]],[[2,0]],axis=0)
hull = ConvexHull(points)

then everything works. The difference between one example and the other (I have done many other examples, so that I am certain) is that the convex hull in the first case is 1-dimensional in 2-dimensional space, while in the second one, is 2-dimensional in 2-dimensional space (i.e. full dimensional).

Any ideas? I thought passing some qhull_options since the docs indicate, as it has been mentioned on the answers that:

QHullError Raised when Qhull encounters an error condition, such as geometrical degeneracy when options to resolve are not enabled.

however, I have read many of the options in QHull and none of them seem to address this problem. I have tried some of them at random, with little success.

Any help would be helpful. I am working on a program that creates hundreds of these hulls and some of them are not full-dimensional.

Jesus Martinez Garcia
  • 269
  • 2
  • 10

2 Answers2

4

It seems that ConvexHull does not support degenerate convex hulls.

The number of points must be at least the number of dimensions plus one to have a non-degenerate convex-hull.

For example in a plane, you need 3 points in order to have a non-degenerate hull: the convex hull for 3 points would be a triangle, while the degenerate hull would be the segment between 2 points.

in fact the docs mention that:

Raises: QhullError Raised when Qhull encounters an error condition, such as geometrical degeneracy when options to resolve are not enabled.

gg349
  • 21,996
  • 5
  • 54
  • 64
  • So you are sure of this? It does not admit 'degenerate' convex hulls? I started with a much bigger number of points, but in some situations the combination is 'linearly dependent', which is annoying. This is why I ask what are the options to solve 'geometrical degeneracy'. I'll write it more clearly in the question. Thanks! – Jesus Martinez Garcia May 08 '15 at 21:09
  • 1
    Just to make it more precise, even if I have many points (which is the real problem going on, not the MWE I built), this still happens, e.g. points (1,1)(2,2) (3,3)... etc – Jesus Martinez Garcia May 08 '15 at 21:16
  • 1
    Actually, sir, you have given me the key to the solution: the word degeneracy (as a mathematician, I had never seen it applied to this context, but to points at infinity). If I substitute the last line by the line: `hull = ConvexHull(points, qhull_options="QJn")` it works like a charm. Thanks! – Jesus Martinez Garcia May 08 '15 at 21:22
  • 1
    Actually, on second thought that is not a good option. What QJn does is basically move all the points a wee bit to the sides randomly until the maximum dimension is reached. For the purposes I am working on (deciding if a point is in the boundary of the convex hull) this is not a good solution. – Jesus Martinez Garcia May 08 '15 at 22:14
  • @JesusMartinezGarcia The help says "QJ". What's the difference with "QJn"? – endolith Oct 08 '18 at 01:01
  • @endolith it's been a long time so I don't remember but from my comment it seems that QJn perturbs the values of the generating points slightly to avoid situations where the points lie in a lower dimensional set. Think of three points in a line on the plane. Their convex hull is a segment. If inperturb one of them slightly their convex hull is a triangle (whose area is very small). – Jesus Martinez Garcia Oct 09 '18 at 07:24
  • @JesusMartinezGarcia Yeah I mean the help says ` - use 'QJ' to joggle the input and make it full dimensional` – endolith Oct 09 '18 at 14:05
  • 1
    @endolith Oh, I see. I am afraid I do not know. I was doing trial and error and, if I recall correctly, in the end I took a different solution (projecting in a lower-dimensional subspace so that the image was maximal). – Jesus Martinez Garcia Oct 16 '18 at 15:16
2

I can't comment, so this is not really answer, but you can get much better error description with:

>>> points2 = np.append([[0,0],[1,1]],[[2,2]],axis=0)
>>> hull = ConvexHull(points2)
QH6154 qhull precision error: initial facet 1 is coplanar with the interior point
ERRONEOUS FACET:
- f1
    - flags: bottom simplicial flipped
    - normal:   -0.7071   0.7071
    - offset:         -0
    - vertices: p2(v1) p0(v0)
    - neighboring facets: f2 f3

While executing:  | qhull i Qt
Options selected for Qhull 2012.1 2012/02/18:
  run-id 972186139  incidence  Qtriangulate  _pre-merge  _zero-centrum
  _max-width  2  Error-roundoff 1.7e-15  _one-merge 8.6e-15
  _near-inside 4.3e-14  Visible-distance 3.4e-15  U-coplanar-distance 3.4e-15
  Width-outside 6.9e-15  _wide-facet 2.1e-14

The input to qhull appears to be less than 2 dimensional, or a
computation has overflowed.

Qhull could not construct a clearly convex simplex from points:
- p1(v2):     1     1
- p2(v1):     2     2
- p0(v0):     0     0

The center point is coplanar with a facet, or a vertex is coplanar
with a neighboring facet.  The maximum round off error for
computing distances is 1.7e-15.  The center point, facets and distances
to the center point are as follows:

center point        1        1

facet p2 p0 distance=    0
facet p1 p0 distance=    0
facet p1 p2 distance=    0

These points either have a maximum or minimum x-coordinate, or
they maximize the determinant for k coordinates.  Trial points
are first selected from points that maximize a coordinate.

The min and max coordinates for each dimension are:
  0:         0         2  difference=    2
  1:         0         2  difference=    2

If the input should be full dimensional, you have several options that
may determine an initial simplex:
  - use 'QJ'  to joggle the input and make it full dimensional
  - use 'QbB' to scale the points to the unit cube
  - use 'QR0' to randomly rotate the input for different maximum points
  - use 'Qs'  to search all points for the initial simplex
  - use 'En'  to specify a maximum roundoff error less than 1.7e-15.
  - trace execution with 'T3' to see the determinant for each point.

If the input is lower dimensional:
  - use 'QJ' to joggle the input and make it full dimensional
  - use 'Qbk:0Bk:0' to delete coordinate k from the input.  You should
    pick the coordinate with the least range.  The hull will have the
    correct topology.
  - determine the flat containing the points, rotate the points
    into a coordinate plane, and delete the other coordinates.
  - add one or more points to make the input full dimensional.
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "qhull.pyx", line 2230, in scipy.spatial.qhull.ConvexHull.__init__ (scipy/spatial/qhull.c:19173)
  File "qhull.pyx", line 328, in scipy.spatial.qhull._Qhull.__init__ (scipy/spatial/qhull.c:3670)
scipy.spatial.qhull.QhullError: Qhull error
>>>
MacHala
  • 2,159
  • 1
  • 15
  • 18
  • 1
    It is not an answer, but it is quite useful. How did you get it to print that info? Is it Python you are using? – Jesus Martinez Garcia May 08 '15 at 21:11
  • 1
    I have probably just newer version of scipy than you (0.14.1), because I get more verbose error descriptions overall (for your example it was just that 2 points aren't enough, and then list of options with which was Qhull called). – MacHala May 08 '15 at 22:55