Scipy ConvexHull и QHull: ранг / размерность не максимальна

Question

Я пытаюсь создать выпуклый корпус, используя библиотеки Scipy и Convex Hull. Насколько я знаю, он называет 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)

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

Есть идеи? Я подумал передать некоторые qhull_options, так как в документах указано, как уже упоминалось в ответах, что:

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

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

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

Answer 1

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

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

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

на самом деле в документах упоминается, что:

Поднимает: 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
>>>