如何判断德劳内三角形是内三角形还是外三角形？

我正在编写一个程序，需要实现中轴提取，其中 Delaunay 三角测量是其中的一个步骤。外部中轴是不需要的，因此相应的外部三角形应被删除。幸运的是我遇到了a page用了很多图，还暗示了一种确定内、外Delaunay三角形的方法（“基于折线周长”），但这只是一个提示，没有详细解释。有人知道算法吗？

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

该解决方案假设您有一个数据结构，使用“虚拟无限 Delaunay 顶点”的方式表示 Delaunay 三角剖分CGAL可以 （请参阅此处的详细信息).

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

Input：对封闭形状边界进行密集采样的点集，甚至可以包含孔
Output：形状内部的 Voronoi 图（形状中轴的近似值）

1. 计算点的 Delaunay 三角剖分
2. 标记连接两个连续采样点的 Delaunay 边。 （看本文第 4-5 页如何通过在每个Delaunay边缘进行本地测试来完成此操作）
3. 将所有无限 Delaunay 面分类为 OUTSIDE 并将它们推入队列Q.
4. While Q is not empty
   1. Delaunay 面 f = Pop fromQ
   2. For every unclassified neighbor triangle t of f
      • 如果 Delaunay 边共享t and f被标记， 分类t作为相反的f
      • 否则分类t一样的喜欢f
      • push t to Q
5. For every Delaunay edge e
   • 如果两个相邻的 Delaunay 三角形d1, d2都分类为 INTERIOR，输出连接 的外心的线段d1 and d2.

For an input like this

the following medial axis approximation can be computed:

您可以使用免费的 Windows 二进制文件来查看该中轴近似在实践中的表现Mesecina。源代码here.