小编Nea*_*der的帖子

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

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

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

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

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

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

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

delaunay triangulation coordinates computational-geometry

5
推荐指数
1
解决办法
1139
查看次数