computational-geometry - 从 Qhull 输出中获取 3D Voronoi 细胞

Question

我的目标是从 Qhull 的 qvoronoi 子例程的输出中获取单个 3D Voronoi 单元（顶点和边）。但是，我无法理解 voronoi 脊（输出“Fv”）。输出中的示例行是：

7 0 1 1 0 4 5 3

第一个数字是行中的顶点数，接下来的两个是被脊分隔的顶点的索引，其余的数字是脊上的顶点索引。我天真地尝试连接相邻的顶点（即4->5, 5->3, 3->1等），它似乎有效，但我不确定这是否正确。这些点如何相互连接？

此外，从 qvoronoi 输出（选项“FN”）中，我可以获得每个区域的顶点，但没有关于顶点之间连接性的信息。我想知道这些信息在哪里。它是在 ridges 输出中，还是在不同的 qvoronoi 输出选项中？

score 2 · Accepted Answer

山脊的指数似乎不是循环顺序的。因此，重建多边形面可能是不可能的。

另一种方法是将gvoronoi每个单元的输出传递qconvex给构造凸包。这不能很好地扩展，但如果您想要可视化或分析的单元格很少，则可能没问题。

例如，要获取 30 个输入站点中输入站点 5 的 Voronoi 单元：

$ rbox 30 D3 | qvoronoi QV5 p | qconvex G

score 0 · Accepted Answer

因为 Voronoi 只保证凸多面体，所以有一种通过找到凸包（在我的情况下为scipy.spatial.ConvexHull()）来找到它的 hacky 方法。您的 Voronoi 区域周围的最小凸包将等同于您想要的，scipy.spatial甚至免费为您提供更多东西

hull=scipy.spatial.ConvexHull(vertices)
volume=hull.volume
triangle_mesh_hull=vertices[hull.simplices] # shape is (n,3,3)

归功于Jaime上面非常简短、优雅的线条。如果你想在此之后对网格的每个三角形部分做一些事情，你可以像这样访问它：

for triangle in triangle_mesh_hull:
  do_stuff_to(triangle)
  ...
  ...
  ...
  do_more_stuff_with(triangle)
  ...
  ...
  ...

2 回答 2