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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

(2) 确定冲突区域需要一个小的修改:

点 p 与有限四面体 T 冲突，如果它在其外 catch 体中(像往常一样)

对于无限四面体 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'。

见实现:

地理:http://alice.loria.fr/software/geogram/doc/html/classGEO_1_1Delaunay3d.html

CGAL:http://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay