Scipy ConvexHull и QHull: rank/dimension не является максимальным

Question

Я пытаюсь создать выпуклый корпус с помощью библиотеки Scipy и ConvexHull. Насколько я знаю, он называет QHull.

Проблема возникает, когда точки, которые я хочу добавить, не имеют «полного измерения». Пример:

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

Имеет для вывода:

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 

Однако, если добавить дополнительные очки, так что выпуклая оболочка имеет полный размер:

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

то все работает. Разница между одним примером и другим (я сделал много других примеров, так что я уверен) состоит в том, что выпуклая оболочка в первом случае является одномерной в двумерном пространстве, а во втором - 2- мерного в двумерном пространстве (т. е. полноразмерном).

Любые идеи? Я думал, проходя некоторые qhull_options с моментом docs показывают, как это было упомянуто в ответах, что:

QHullError Воспитанного когда Qhull встречает условие ошибки, такие как геометрическое вырождение, когда варианты решения не включены.

Однако, я прочитал многие из options in QHull, и ни один из них, похоже, не затрагивает эту проблему. Я пробовал некоторые из них наугад, с небольшим успехом.

Любая помощь была бы полезна. Я работаю над программой, которая создает сотни этих корпусов, а некоторые из них не являются полноразмерными.

Answer 1

Кажется, что выпуклая оболочка не поддерживает вырожденные выпуклые оболочки.

Число точек должно быть не менее, чем число измерений плюс один, чтобы иметь невырожденную выпуклую оболочку.

Например, в плоскости необходимо иметь 3 точки, чтобы иметь невырожденный корпус: выпуклая оболочка для трех точек будет треугольником, а вырожденная оболочка будет отрезком между двумя точками.

фактически docs отметить, что:

Поднимает: QhullError Возникает, когда Qhull встречает состояние ошибки, такие как геометрическое вырождение, когда различные варианты для решения не включено.

Answer 2

Я не могу комментировать, так что это на самом деле не ответить, но вы можете получить гораздо лучшее описание ошибки с:

>>> 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 
>>>