基于Bowyer-Watson算法的Delaunay三角剖分重叠问题求助

• 检查超级三角形边界处理
  点集规模扩大后，若超级三角形边界设得太小，会导致本该被剔除的边界三角没被正确移除。算法最后阶段必须严格过滤所有包含超级三角形顶点的三角，建议在代码里加个校验，打印或断言最终三角集合里有没有带超级顶点的项。

• 修正空圆测试的精度误差
  大规模点集下浮点数计算误差会放大，直接导致空圆测试误判：

  • 别直接比浮点数相等，用epsilon阈值（比如1e-8）判断点和外接圆的位置关系；
  • 换用距离平方比较替代开根号，比如计算点到圆心的距离平方，和外接圆半径平方对比，避免平方根带来的精度丢失；
  • 检查外接圆圆心、半径的计算逻辑，有没有溢出或者精度损耗的情况。

• 排查三角边的去重逻辑
  移除坏三角后收集边界边并去重，这步要是失效，会生成大量重叠三角：

  • 存储边的时候用有序顶点对（比如把两个顶点按坐标大小排序后再存），避免(A,B)和(B,A)被当成不同边；
  • 检查边集合的去重代码，确保重复边被正确过滤。

• 处理点集中的重复点
  随机生成的点集大概率存在重复坐标点，小规模时没影响，大规模会触发大量错误的空圆测试。在输入算法前先做去重：用哈希表存已有的点坐标（带epsilon容差），过滤掉重复点。

• 用中等规模点集调试定位
  拿50-100个点的中等规模集合做测试，加日志输出：

  • 记录每个点添加后，坏三角数量、边界边数量、新生成三角数量；
  • 可视化中间步骤的三角，看从哪个点开始出现冗余三角，缩小问题范围。

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