algorithm - 如何确定Delaunay三角形是内部的还是外部的？

我正在编写一个程序，该程序需要实现中间轴提取，其中Delaunay三角剖分是其中的一步。不需要外部内轴，因此打算删除相应的外部三角形。幸运的是，我遇到了a page，其中包含许多图表，也暗示了一种确定内部和外部Delaunay三角形的方法(“基于虚线周长”)，但这只是一个提示，没有详细说明。有人知道算法吗？

编辑:我忘了提到初始点是从封闭多边形的边界中采样的，我的意图是确定每个Delaunay三角形是否在多边形内部。

最佳答案

此解决方案假定您具有一个数据结构，该数据结构使用CGAL(see details here)的方式使用“虚拟无限Delaunay顶点”表示Delaunay三角剖分。

这个想法是找到边界Delaunay边缘:连接两个连续采样点的边缘；然后通过Delaunay三角剖分进行“泛洪”以对Delaunay的面孔进行分类。人们知道无限顶点是外部的，因此只要一个不跨越边界边缘，就可以将其邻居(和邻居的邻居等)分类为外部。如果一个人到达边界边缘，则可以简单地将相邻三角形标记为内部三角形，然后类似地继续。

输入:密集采样封闭形状边界的点集，该边界甚至可以包含孔
输出:形状内部的Voronoi图(形状中轴的近似值)

计算您的点的Delaunay三角剖分

标记连接两个连续采样点的Delaunay边缘。 (请参阅page 4-5 of this paper，如何在每个Delaunay边缘上进行本地测试来做到这一点)

将所有无限Delaunay面孔分类为OUTSIDE，并将其插入队列Q。

Q不为空时

Delaunay的脸f = Q的流行音乐

对于f的每个未分类邻居三角形t

如果标记了t和f共享的Delaunay边，
将t分类为f

的反义词

else像f

一样对t进行分类

将t推至Q

对于每个Delaunay边缘e

如果两个相邻的Delaunay三角形d1，d2都被分类为INTERIOR，则输出连接d1和d2的外接点的线段。

对于这样的输入

可以计算以下中间轴近似值:

您可以使用Mesecina的免费windows二进制文件检查该中间轴逼近的实际行为。源代码here。