5

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

但根据“数值配方：科学计算的艺术”：

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

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

Incircle (a,b,c) Infinity -> False。假设 a,b,c 是有限的。

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

4

2 回答 2

1

通过在无穷远处添加一个点来实现 Delaunay 三角剖分非常容易。为无限顶点选择一个约定（例如，顶点索引-1）。

开始时，您在取自输入点集的 4 个非共面点之间创建一个初始有限四面体 T0，然后创建四个无限四面体，将 T0 的每个面连接到无限顶点 0（并且不要忘记将它们正确互连）他们共同的无限面孔）。

然后像往常一样（Boyer-Watson 算法），通过（1）计算包含点 p（定位）的四面体 T 和（2）找到冲突区域，一个接一个地插入每个点 p，如下所示：

(1) locate 是未修改的：你从一个随机有限四面体走到 p 。在行走过程中，如果你到达一个无限四面体，那么你就停在那里（这意味着该点在先前插入的点的凸包之外）

(2) 确定冲突区域需要稍作修改：

  • 一个点 p 与有限四面体 T 冲突，如果它在它的外接球体中（像往常一样）

  • 对于无限四面体 T = (p1, p2, p3, p4)，p1,p2,p3,p4 之一是无限顶点（例如 p2，则 T = (p1,infinite,p3,p4)）。要检查 p 是否与 T 冲突，将无限顶点替换为 p，并计算四面体的有符号体积：在我们的示例中为 signed_volume(p1, p, p3, p4)，如果为正，则 T 冲突与 p。如果它是负数，那么 T 与 p 不冲突。如果 p恰好在 T 的三个有限顶点的支撑平面上，则如果 T' 与 p 冲突，则 T 与 p 冲突，其中 T' 是沿 T 的有限面与 T 相邻的四面体（等效地，可以检查 p 是否在 T 的有限面的外接圆内，而不是查询 T'。

请参阅以下实现：

于 2015-07-14T11:55:10.410 回答
0

我认为你试图定义包含无限远点的几何的完整数学，这让你自己的生活变得困难。对于准确计算 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;
   }

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

于 2011-12-15T17:13:20.690 回答