迭代 Delaunay 三角剖分器中的无限初始边界三角形

Question

大多数迭代算法需要一个初始的空三角形来让球滚动。似乎一个常用的技巧就是将超级三角形与点集相比变得非常大。

但根据“数值食谱：科学计算的艺术”：

“...如果距离仅仅是有限的（到边界点），则构造的三角剖分可能不太符合德劳内。例如，在不寻常的情况下，它的外边界可能会略微凹入，具有直径数量级的小负角的“真实”点集除以到“虚构”（边界）点的距离。

那么有哪些选项可以用无穷远处的点来增强笛卡尔坐标，而不必将所有输入转换为不同的坐标系，例如齐次坐标？这些点如何与通常的几何谓词 CCW 和 Incircle 相吻合？

内圆 (a,b,c) 无穷大 -> 假。假设 a,b,c 是有限的。

但是当 a,b,c 之一是无穷远点时呢？圆会变成半平面，然后测试变成逆时针检查吗？如果外接圆上有 2 个或更多点是无限的怎么办？圆是否扩展成一个完整的平面导致测试总是产生真？CCW呢？你如何根据一条在无穷远处有一个或多个点的线对一个点进行分类？

Answer 1

我认为你试图定义包含无限距离点的几何的完整数学，这让你自己的生活变得困难。对于准确计算 Delaunay 三角剖分的原始问题而言，这并不是必需的。

我不久前用 Java 编写了一个 Delaunay 生成器，可以在这里使用： http: //open.trickl.com/trickl-graph/index.html

请参阅http://open.trickl.com/trickl-graph/apidocs/index.html，特别是：

    // Check if fourth point is within the circumcircle defined by the first three
   private boolean isWithinCircumcircle(PlanarGraph<V, E> graph, V first,
           V second,
           V third,
           V fourth) {
      // Treat the boundary as if infinitely far away
      Coordinate p = vertexToCoordinate.get(fourth);
      if (PlanarGraphs.isVertexBoundary(graph, first)) {
         return isLeftOf(third, second, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, second)) {
         return isLeftOf(first, third, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, third)) {
         return isLeftOf(second, first, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, fourth)) {
         return false;
      }

      Coordinate a = vertexToCoordinate.get(first);
      Coordinate b = vertexToCoordinate.get(second);
      Coordinate c = vertexToCoordinate.get(third);

      boolean within = (a.x * a.x + a.y * a.y) * getDblOrientedTriangleArea(b, c, p)
              - (b.x * b.x + b.y * b.y) * getDblOrientedTriangleArea(a, c, p)
              + (c.x * c.x + c.y * c.y) * getDblOrientedTriangleArea(a, b, p)
              - (p.x * p.x + p.y * p.y) * getDblOrientedTriangleArea(a, b, c) > 0;

      return within;
   }

这里，在检查外接圆条件时明确检查边界点，因此可以有效地将它们视为“无限”远。这比弄清楚你所描述的所有几何含义要容易得多。