我正在编写一个需要实现中轴提取的程序，其中 Delaunay 三角剖分是其中的一个步骤。外部中轴是不需要的，因此打算移除相应的外部三角形。幸运的是，我找到了一个有很多图表的页面，也提示了确定内部和外部德劳内三角形的方法（“基于折线周长”），但这只是一个提示，没有详细解释。有人知道算法吗？
编辑：我忘了提到初始点是从封闭多边形的边界采样的，我的目的是确定每个德劳内三角形是否在多边形内。
问问题
6680 次
4 回答
14
此解决方案假定您有一个数据结构，该结构使用CGAL的方式使用“虚拟无限 Delaunay 顶点”表示 Delaunay 三角剖分（请参阅此处的详细信息）。
这个想法是找到边界Delaunay边缘：连接两个连续样本点的边缘；然后通过 Delaunay 三角剖分“泛洪”对 Delaunay 面进行分类。知道无限顶点是外部的，因此只要不跨越边界边，就可以将其邻居（以及邻居的邻居等）分类为外部。如果到达边界边缘，则可以简单地将相邻三角形标记为内部并以类似方式继续。
输入：对封闭形状的边界进行密集采样的点集，甚至可以包含孔
输出：形状内部的 Voronoi 图（形状中轴的近似值）
- 计算点的 Delaunay 三角剖分
- 标记连接两个连续采样点的 Delaunay 边。（请参阅本文第 4-5 页，如何通过在每个 Delaunay 边缘上进行本地测试来做到这一点）
- 将所有无限的 Delaunay 面分类为 OUTSIDE 并将它们推送到队列Q。
- 虽然Q不为空
- Delaunay 面 f = 来自Q的 Pop
- 对于f 的
每个未分类的相邻三角形t
- 如果标记了t和f共享的 Delaunay 边，则将t归类为f的相反
- 否则将t归类为f
- 推t到Q
- 对于每个 Delaunay 边e
- 如果两个相邻的德劳内三角形d1，d2都被归类为 INTERIOR，则输出连接d1和d2外心的线段。
对于这样的输入
，可以计算以下中轴近似值：
您可以使用Mesecina的免费 windows 二进制文件查看这种中轴近似在实践中的表现。源代码在这里。
于 2009-06-16T17:06:43.570 回答
2
您是否考虑过使用不创建外部三角形的不同形式的三角测量？我曾经参加过一门课程，花了很多时间讨论多边形三角剖分的理论方面。也许浏览课程网站会给您一些见解？http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation
编辑：实际上，我只是想到了别的东西。如果您已经有要尝试三角剖分的多边形，则可以使用格林定理。格林定理使用多边形的周长来计算其面积！更重要的是，在这种情况下，您可以通过查看面积符号来确定一个点是在一条线的一侧还是另一侧。在多边形上，格林定理解决了一个简单的减法问题。因此，取任何你知道在多边形内的点，并计算多边形每条边的面积。这会告诉您您的点需要位于每条线的哪一侧。现在只需在每个三角形内取一个点并做同样的事情。如果任何一个符号是错误的，那么你就有一个外部三角形。（注意：根据多边形的形状，这可能实际上不起作用。
于 2009-06-15T16:35:33.867 回答
0
也许我在这里做了太多假设，但听起来你有一个由一堆点组成的多边形，并且你正在对这些点进行三角剖分。然后你想丢弃所有落在多边形之外的三角形，对吧？
为什么不直接对多边形进行三角剖分（使用单调分解或类似的方法），这样您就不会创建任何外部三角形？我想这可能会增加运行时间（首先在 O(nlogn) 时间内进行三角剖分，然后在 O(n^2) 时间内创建一个 delaunay 三角剖分），但可能有更快的方法。
于 2009-06-15T16:24:48.880 回答
0
他们提出的算法看起来有点损坏，正如他们在其中一张图中所显示的那样，这可能是 Google Scholar 中似乎没有任何有用引用的原因。
于 2009-06-15T17:16:53.920 回答