3D中Delaunay三角剖分转Voronoi图：薄四面体球心与算法稳定性问题

一、极薄四面体的外接球心计算优化 #

• 退化四面体的约束近似：当四面体极度扁平时，外接球心会趋于无穷远，此时可将其视为近似平面上的三角形，先计算该三角形的外接圆心，再沿平面法向量施加一个远小于点集坐标精度的微小偏移，得到能作为Voronoi有效顶点的近似球心，避免无效的远距点。
• 数值稳定的线性代数求解：计算外接球心的核心是解线性方程组，不要直接展开大行列式，改用LU分解、QR分解等数值稳定的方法。同时先对所有点做归一化处理——平移至原点附近、缩放至单位区间，减少浮点数舍入误差的影响。
• 厚度阈值判定与替代策略：预先计算四面体的“厚度指标”（比如体积与外接球半径的比值，或最小高度与最大边长的比值），当指标低于设定阈值时，直接标记为退化四面体，不生成对应的Voronoi顶点，而是用相邻四面体的球心插值得到替代点。

二、无精确算术时的Delaunay剖分稳定性保障 #

• 受控扰动与浮点过滤：给输入点集添加极小的随机扰动（扰动幅度远小于点间最小距离），避免四点共圆的退化场景；同时在拓扑判断步骤中，设置一个极小的误差容忍阈值，过滤掉浮点运算导致的微小偏差引发的错误判定。
• 增量算法的拓扑一致性校验：在增量插入点的过程中，不单纯依赖浮点计算的空圆包含性判断，同步检查空腔边界的拓扑闭合性——若出现矛盾（比如边界不闭合、重复边），则回溯调整插入逻辑，避免浮点误差破坏剖分拓扑。
• 自适应精度的关键判断：在四点共圆、点是否在球内等核心判断步骤，根据计算误差动态切换精度（比如从double切换到long double），仅在必要时提升精度，平衡效率与稳定性。
• 拓扑优先的松弛剖分策略：优先保证剖分的拓扑合法性（无重叠、无空洞、覆盖所有输入点），而非严格的Delaunay空圆特性。当浮点误差导致空圆条件难以严格满足时，允许少量非严格Delaunay三角形存在，后续通过局部边翻转做微调优化。

内容的提问来源于stack exchange，提问作者Михаил