Почему scipy.spatial.Voronoi () выводит нулевые области, даже если нет повторяющихся точек ввода? - PullRequest
Новая
       86

Почему scipy.spatial.Voronoi () выводит нулевые области, даже если нет повторяющихся точек ввода?

0 голосов
/ 31 декабря 2018

Почему некоторые районы Вороного пусты?

У меня есть облако точек поверхности человека, на котором я пытаюсь найти диаграмму Вороного.Итак, я нашел scipy.spatial.Voronoi(), включая довольно неплохую документацию .Но иногда vor.regions включает пустые регионы, и документация не совсем объясняет, почему они там есть.В лучшем случае это объясняет связь с расчетом Делоне: «Обратите внимание, что из-за проблем точности чисел, аналогичных описанным выше при триангуляции Делоне, воронойских областей может быть меньше, чем входных точек».Но если это так, то это происходит только потому, что qhull вычисляет Вороного, используя аналогичный (или точно такой же) алгоритм, который используется для триангуляции Делоне.Математически единственная причина, по которой регион Вороного должен быть пустым, заключается в том, что его точки дублированы

Конкретные цели:

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

Предпосылки и другие исследования

Этот ответ предлагает Voronoi(points, qhull_options='Qbb Qc Qx') и в документах Сципи предлагает qhull_options="QJ Pp"

входные данные: http://columbia.edu/~nxb2101/minimal_stickfig_.npy

Код: 

import numpy as np; np.set_err(all='raise')
import scipy.spatial
pt_cloud=np.load('minimal_stickfig_.npy')
vor=scipy.spatial.Voronoi(pt_cloud)

for idx in range(len(vor.regions)):
  region=vor.regions[idx]
  vertices = vor.vertices[region]
  hull=scipy.spatial.ConvexHull(vertices)
  volume=hull.volume
  triangle_mesh_hull=vertices[hull.simplices] # (n,3,3)
  # triang mesh calculation taken from
  #   https://stackoverflow.com/questions/26434726/return-surface-triangle-of-3d-scipy-spatial-delaunay/26516915

  inner_pt = np.mean(vertices[:2],axis=0).reshape((1,3))
  CoM=np.zeros((3,))
  pif("inner_pt is {0}".format(inner_pt))
  for triangle in triangle_mesh_hull:
    pif("triangle is: \n{0}".format(triangle))
    tetra=np.concatenate((inner_pt,triangle),axis=0)
    CoM_tetra=np.mean(tetra,axis=0)
    vol_tetra=volume_tetra(tetra)
    CoM+=(CoM_tetra*vol_tetra)
  CoM /= volume
  # do more with CoM, and volume

Любойвид помощи приветствуется;если вы не уверены, почему qhull это делает или как обойти это, пожалуйста, дайте мне знать, что вы сделали, чтобы сделать высококачественную сетку из облака точек

...