2

为什么有些 Voronoi 区域是空的？

我有一个人的表面点云，我试图找到它的 Voronoi 图。所以我发现scipy.spatial.Voronoi()，包括一些相当不错的文档。但有时vor.regions包括空白区域，并且文档并没有完全解释它们为什么在那里。它充其量解释了与其 Delaunay 计算的关系“请注意，由于与上述 Delaunay 三角剖分类似的数值精度问题，Voronoi 区域可能比输入点少。” 但如果是这样，那只是因为 qhull 使用与用于 Delaunay 三角剖分的相似（或完全相同）的算法计算 Voronoi，才会发生这种情况。在数学上，Voronoi 区域应该为空的唯一原因是它的点是否重复

具体目标：

我希望复制本文的结果，该结果使用 Voronoi 图来计算每个输入点的法线向量。所以我可以做一个解决方法，我使用与附近点的正确计算法线相似的法线，或者我可以忽略任何给出零 Voronoi 区域的点。但我真的很想知道如何解决这些空白区域，这样我就可以尽可能多地使用输入数据。

背景和其他研究

这个答案表明Voronoi(points, qhull_options='Qbb Qc Qx')并且在文档中scipy 建议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 为什么这样做或如何解决它，请告诉我您为从点云制作高质量网格所做的工作

4

0 回答 0