Delaunay 三角剖分和最大内切圆的混淆
Lin*_*nda 2 algorithm geometry delaunay cgal computational-geometry
我需要找到一个凸多边形的最大内切圆，我搜索了很多网站，我知道这可以通过使用 Delaunay 三角剖分来完成。我在 CGAL 讨论中找到了一个使用 CGAL 的算法的线程：
您可以使用 CGAL 轻松计算：
首先，计算点的 Delaunay 三角剖分。
然后，迭代三角剖分的所有有限面。对于每个有限面 f
- 计算它的外心 c
- 在三角剖分中定位 c（为了加快速度，您可以将 f 的一个顶点作为点位置的起始提示）
- 如果 locate(c,hint) 返回的面是有限的，则外心 c 位于点的凸包中，因此，f 是候选者
- 如果 f 是这样的候选人脸，计算它的平方外接圆半径，只保留最小平方外接圆半径的脸
CGAL 手册（第 2 章 2D 三角剖分，以及内核中的一些内容）显示了执行此操作的每个基本功能。
我对这个算法的最后一部分有点困惑。当我阅读它时，我从中了解到三角剖分面的最小外接半径是最大内切圆的半径。但是从使用 Delaunay 三角剖分的多边形示例来看，似乎即使是最小的外接圆有时也无法放入多边形内，那么它如何与最大的内切圆具有相同的半径？
多边形中的最大内切圆。 多边形最大内切圆问题的经典计算几何解决方案是使用多边形面的广义 Voronoi 图。的中轴多边形的。这种方法适用于更一般的设置，例如带孔的多边形，请参阅类似问题的这个stackoverflow 答案。
凸输入。 但是，输入多边形的凸性使问题更具结构性，我想对此发表评论。考虑以下凸输入多边形（黑色）、Voronoi 图（蓝色）和以 Voronoi 节点为中心的最大内切圆（绿色）。
经典的基于 Voronoi 的解决方案是 (i) 计算 Voronoi 图和 (ii) 取具有最大间隙（即到其定义面的距离）的 Voronoi 节点。
带孔的多边形的 Voronoi 图（即顶点和边的集合）可以在 O(n log n) 时间内计算，参见Fortune 算法 (1986)。后来Chin et alii (1999)给出了一个简单多边形中轴的 O(n) 算法。
然而，对于凸多边形，由于Aggarwal 等人，在 1989 年已经知道了一种在 O(n) 时间内运行的 Voronoi 图的时间最优算法。该算法基本上遵循以下思想：考虑以单位速度向内移动的灰度偏移曲线。如果您将此运动投影到三个空间中，其中 z 轴是时间，您将在多边形上得到一个单位坡度屋顶：
这个屋顶模型也可以描述如下：在每个多边形边上放置一个与多边形成 45° 坡度的半空间（这样它们包含多边形）并与它们全部相交。因此，如果您可以快速计算半空间的交集，那么您也可以快速计算凸多边形的 Voronoi 图。实际上，对于最大内切圆问题，我们不需要回到 Voronoi 图，而是取屋顶的一个峰，它标志着最大内切圆的中心。
现在将半空间对偶化为点，然后半空间的交集对应于其对偶点的凸包。阿加瓦尔等人。现在找到了一个 O(n) 算法，用于源于此设置的点的凸包。
可以在我的博客文章中找到此构造的摘要，该构造导致任何维度的凸多面体的 Voronoi 图算法。
简单快速的实施。一种更简单的计算 Voronoi 图的算法是由直骨架驱动的。对于凸多边形，Voronoi 图和直骨架是相同的。
直骨架实现Stalgo背后的算法基本上模拟了波前结构（灰度偏移曲线）的演变。对于凸多边形，这简化为查找折叠边的序列。
所以一个简单的 O(n log n) 算法可能如下所示：
- 构建多边形边的圆形列表。计算波前传播过程中每条边的塌陷时间，并将该事件插入到优先级队列中。
- 直到队列为空：取出下一个边缘折叠事件：从圆形结构中移除边并更新移除边的相邻边的折叠次数。
实际上，您可以进一步简化上述算法：您不需要更新优先级队列中的边缘折叠，而只需插入新的边缘折叠：由于边缘的新折叠时间严格较低，因此您总是首先获得正确的事件并关闭其他事件并且队列的增长不会超过 2n。因此，您不会妥协 O(n log n) 时间复杂度。
对于最大内切圆问题，您可以进一步简化上述算法：您寻找的 Voronoi 节点（相应的直骨架节点）是由于优先级队列上循环结束时最终三角形的坍塌。
这个算法在实践中应该很快，只有几行代码。