在迭代式Delaunay三角剖分中，无限初始边界三角形

Question

在迭代式Delaunay三角剖分中，无限初始边界三角形

coordinatescomputational-geometrytriangulationdelaunay

5

大多数迭代算法需要一个初始的空三角形来开始。似乎一个常用的技巧是将超级三角形与点集相比较，使其非常大。

但根据“Numerical recipes: the art of scientific computing”所述：

“……如果距离仅仅是有限的（对于边界点），则构建的三角剖分可能不是完全的Delaunay。例如，在不寻常的情况下，它的外边界可能略微凹陷，并且具有小的负角度，这些角度大约等于“真实”点集直径除以到“虚拟”（边界）点的距离。”

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

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

但是当a、b、c中有一个是无穷远点时呢？圆变成了半平面，然后测试是否变成了CCW检查？如果圆周上有2个或更多的无限点，那么圆会扩展成一个完整的平面，导致测试总是返回true吗？关于CCW，如何将一个点分类到具有一个或多个无限点的线上？

- Neal Alexander

2个回答

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;
   }

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

- Tim Gee

Tim，请问您能解释一下您选择边界点的逻辑是什么吗？ - chaitanya

请纠正我如果我错了，但我认为即使是完整的点列表也是在增量算法中提供的。我认为这些点可能是按随机顺序逐个添加到增量算法中的。此外，您能否解释一下您计算“超级三角形”坐标的基本几何学？我正在使用矩形的面积和周长来计算三角形的底边和高度。这是正确的做法吗？ - chaitanya

请参见 https://github.com/trickl/trickl-graph/blob/master/src/main/java/com/trickl/graph/generate/DelaunayGraphGenerator.java 中的 "createBounds"。 - Tim Gee

谢谢你的链接，Tim。我尝试将你的项目作为库导入，但是遇到了问题。我安装了m2eclipse来导入Maven项目，但在pom.xml文件中出现了缺少artifact的错误。你能告诉我如何将你的项目作为jar文件导入吗？ - chaitanya

谢谢Tim。我非常感激，尽管我本来想从Maven编译项目[这将是我的第一次尝试]。 - chaitanya

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BrunoLevy · Accepted Answer

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

一开始，您需要创建一个初始的有限四面体T0，该四面体由输入点集中的4个非共面点组成，然后创建四个连接T0每个面到无限顶点0的无限四面体（不要忘记沿其公共无限面适当地相互连接）。

然后，您按照通常的方式（Boyer-Watson算法）逐个插入每个点p，方法是（1）计算包含点p的四面体T（locate），并且（2）找到冲突区域，如下所示：

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

(2) 确定冲突区域需要进行小的修改：

一个点p与一个有限四面体T冲突，如果它在其外接球中（通常情况下）。
对于一个无限四面体T = (p1, p2, p3, p4)，其中p1、p2、p3、p4中的一个是无限顶点（例如p2，则T = (p1，无限，p3，p4)）。要检查p是否与T冲突，请用p替换无限顶点，并计算四面体的有符号体积：在我们的例子中为signed_volume(p1，p，p3，p4)，如果它是正数，则T与p冲突。如果它是负数，则T与p不冲突。如果p恰好在T的三个有限顶点的支撑平面上，则当T'与p冲突时，T与p冲突，其中T'是沿着T的有限面相邻的四面体（等效地，可以检查p是否在T的有限面的外接圆中，而不是查询T'）。

请参见实现：