scipy voronoi 3d - не все точки гребня показаны

Question

У меня возникли проблемы с использованием функции Voronoi от scipy. Я следовал примеру 2d, однако, когда я выполнил аналогичный пример в 3d, не все вычисления ridge_points вычисляются. Мои данные коробка из 27 точек в [0,2] х [0,2] х [0,2]:

points = np.array([ 
    # bottom plane 
    [0,2,0], [1,2,0], [2,2,0], 
    [0,1,0], [1,1,0], [2,1,0], 
    [0,0,0], [1,0,0], [2,0,0], 
    # middle plane 
    [0,2,1], [1,2,1], [2,2,1], 
    [0,1,1], [1,1,1], [2,1,1], 
    [0,0,1], [1,0,1], [2,0,1], 
    # top plane 
    [0,2,2], [1,2,2], [2,2,2], 
    [0,1,2], [1,1,2], [2,1,2], 
    [0,0,2], [1,0,2], [2,0,2] 
    ]) 

vor = Voronoi(points) 

print vor.ridge_points 
# outputed 
array([[ 4, 7], 
     [ 4, 5], 
     [ 4, 3], 
     [ 4, 1], 
     [ 4, 13], 
     [ 3, 12], 
     [ 7, 16], 
     [15, 12], 
     [15, 16], 
     [ 9, 12], 
     [ 9, 10], 
     [ 1, 10], 
     [12, 21], 
     [12, 13], 
     [23, 14], 
     [23, 22], 
     [14, 17], 
     [14, 11], 
     [14, 5], 
     [14, 13], 
     [22, 19], 
     [22, 21], 
     [22, 13], 
     [22, 25], 
     [17, 16], 
     [11, 10], 
     [25, 16], 
     [16, 13], 
     [13, 10], 
     [19, 10], dtype=int32) 

Я заметил точки на углах:

points[0] = array([0, 2, 0]) 
points[2] = array([2, 2, 0]) 
points[6] = array([0, 0, 0]) 
points[8] = array([2, 0, 0]) 
points[18] = array([0, 2, 2]) 
points[20] = array([2, 2, 2]) 
points[24] = array([0, 0, 2]) 
points[26] = array([2, 0, 2]) 

не имеют никаких точек гребня. Я бы предположил (например, 2-й случай), что углы будут иметь точки гребня. Например, я предположил бы, что точки [6] = [0,0,0] будут иметь точки хребта с [1,0,0], [0,1,0] и [0,0,1]. Разве это невозможно вычислить с помощью scipy или я думал об этом неправильно?

Answer 1

Scipy использует Qhull для расчетов Delaunay/Voronoi/Convexhull. Данные, содержащиеся в ridge_points, являются сообщением qvoronoi Fv, хотя гребни необязательно перечислены в том же порядке. (В качестве проверки: https://gist.github.com/pv/2f756ec83cdf242ce691)

Документация Qhull для Fv (http://www.qhull.org/html/qh-optf.htm#Fv2) упоминает предостережение, что кажется уместным здесь:

Опция «Fv» не перечисляет гребни, которые требуют более одной средней точки. Например, диаграмма Вороного коферических точек перечисляет нулевые хребты (например, «rbox 10 s | qvoronoi Fv Qz»). Другими примерами являются диаграммы Вороного прямоугольной сетки (например, «rbox 27 M1,0 | qvoronoi Fv») или набор точек с прямоугольным углом (например, «rbox P4,4,4 P4,2,4 P2,4 , 4 P4,4,2 10 | qvoronoi Fv '). Оба случая пропускают неограниченные лучи по углам. Чтобы определить эти хребты, окружайте точки большим кубом (например, «rbox 10 s c G2.0 | qvoronoi Fv Qz»). Куб должен быть достаточно большим, чтобы связать все области Вороного исходного набора точек. Просьба сообщить о любых других случаях, которые были упущены. Если вы можете формально описать эти случаи или написать код для их обработки, отправьте электронное письмо на адрес qhull@qhull.org.

rbox 27 M1,0, упомянутый в тексте, представляет собой точно такой же набор точек, что и в вашем примере (в другом порядке).

Как правило, у Qhull возникают проблемы с геометрическими вырождениями, которые возникают, например, в прямоугольных сетках. Общим решением является установка qhull_options="QJ", который сообщает ему, чтобы добавить случайные возмущения к точкам данных до тех пор, пока не будут устранены дегенерации. Это типично генерирует диаграммы тесселяции/voronoi с несколькими дополнительными симплексами/гребнями, но может разрешать проблемы этого типа.