嘿，要算立方体里的3D Voronoi图对吧？我整理了几个业界常用的算法，每个都有自己的适用场景，你可以根据生成点规模、精度要求和开发成本来选：

• 3D扩展版Fortune算法
  这是经典2D Fortune扫线算法的三维升级，核心思路是用一个扫面平面遍历所有生成点，逐步构建Voronoi图的面、边和顶点。它的时间复杂度是O(n log n)，效率很高，适合中等到大规模的生成点集。不过实现门槛比较高，尤其是处理立方体边界的时候，得额外做截断逻辑，把超出立方体范围的Voronoi部分切掉。

• Delaunay三角剖分对偶转换法
  3D Voronoi图和Delaunay三角剖分是严格对偶的关系——每个Delaunay四面体对应Voronoi图里的一个顶点，每个Delaunay边对应Voronoi面，反过来也成立。你可以先对立方体里的生成点做3D Delaunay剖分，再通过对偶变换得到Voronoi图。常用的Delaunay算法有：

  • Bowyer-Watson算法：逻辑简单，容易手动实现，适合小规模点集（比如几百个点以内）。
  • 增量插入算法：效率更高，时间复杂度O(n log n)，适合中大规模点集。
    这种方法的好处是很多成熟的几何库已经实现了3D Delaunay，你可以直接复用，只需要自己处理对偶转换和立方体边界的裁剪工作。

• 网格遍历近似法
  如果你的生成点数量不多，或者对精度要求没那么苛刻，这种方法绝对是最省心的。把整个立方体划分成规则的3D网格（比如每个小立方体的边长固定），然后对每个网格点计算距离最近的生成点，把属于同一个生成点的网格点归为一类，就能得到近似的Voronoi区域。优点是实现超级简单，不需要复杂的几何计算；缺点是精度完全依赖网格密度，网格太密的话计算量会直线上升（时间复杂度O(mn)，m是网格点数，n是生成点数），而且得到的是离散的近似结果，不是精确的连续Voronoi面。

• 增量构造算法
  从一个简单的初始Voronoi图（比如先处理2-3个生成点）开始，逐个添加新的生成点，每次添加时找到受影响的现有Voronoi单元，更新这些单元的边界。这种方法特别适合需要动态添加生成点的场景（比如交互式建模工具）。不过每次添加点时需要做不少几何判断来定位受影响的区域，实现起来有一定复杂度，每次更新的时间大概是O(k log n)，k是受影响的单元数量。

实用小提示 #

要是不想从零造轮子，很多开源几何库都内置了3D Voronoi计算功能，比如C++的CGAL、Python的scipy.spatial.Voronoi。不过要注意，这些库默认计算的是整个无限空间的Voronoi图，你需要自己写逻辑把超出立方体范围的部分裁剪掉，只保留内部的Voronoi结构。

内容的提问来源于stack exchange，提问作者ShilZoyer