迷惑于Delaunay三角剖分和最大内切圆

Question

迷惑于Delaunay三角剖分和最大内切圆

algorithmgeometrycomputational-geometrycgaldelaunay

3

我需要找到凸多边形的最大内切圆，我在许多网站上搜索并发现可以使用 Delaunay 三角剖分来实现。我在 CGAL 讨论中找到了一个带有使用 CGAL 的算法的线程：

“您可以使用 CGAL 轻松计算此问题：首先，计算点的 Delaunay 三角剖分。然后，迭代所有三角剖分的有限面。对于每个有限面 f 计算其外心 c 将 c 定位于三角剖分中（为加快速度，您可以给出 f 的一个顶点作为起始提示）如果 locate(c,hint) 返回的面是有限的，则外心 c 在点的凸包中，因此 f 是候选面如果 f 是这样一个候选面，则计算其平方外接圆半径仅保留具有最小平方外接圆半径的面”

我对这个算法的最后一部分有些困惑。当我阅读它时，我理解的是三角剖分面的最小外接圆的圆周半径是最大内切圆的半径。但是从 Delaunay 三角剖分的多边形示例中看来，即使是最小外接圆有时也无法适应多边形，那么它如何具有与最大内切圆相同的半径呢？

- Linda

2

请重新阅读该主题的开头，它是关于一个不同的问题，所以答案不同是正常的... 您想要一个不与多边形相交的磁盘，而该主题是关于寻找一个不包含任何顶点（没有提及边缘）的磁盘。 - Marc Glisse

@MarcGlisse 谢谢您的回复。我再次阅读了帖子，所以“最大空心圆”问题不考虑边缘？我看到Naresh提到他想找到最大内切圆，但由于他使用点集而不是多边形顶点，所以我不能使用这个算法。您有解决这种问题的任何想法吗？ - Linda

你应该在一个新问题中询问这个。但首先，尝试理解问题的结构。你有n条线，对于每条线，你希望圆在该线的给定一侧。你能将其制定为线性规划吗？ - Marc Glisse

如果形状是由边界采样的点给出的，则此stackoverflow问题提供了一种基于Voronoi图的解决方案，这些图是Delaunay三角剖分的对偶。 - S. Huber

2个回答

0

最后一步是选择三角形的最小面。然后重复这个过程。

- Micromega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- S. Huber · Accepted Answer

多边形中的最大内切圆。 解决多边形最大内切圆问题的经典计算几何方法是使用多边形面的广义沃罗诺伊图或多边形的中轴线。这种方法在更一般的情况下也适用，比如带洞的多边形，请参见stackoverflow答案中类似问题的回答。

凸输入。 然而，您的输入多边形的凸性给问题增加了更多结构，我想对此进行评论。考虑以下凸输入多边形（黑色），其沃罗诺伊图（蓝色）和以沃罗诺伊节点为中心的最大内切圆（绿色）。

Voronoi diagram and maximum inscribed circle

经典的基于Voronoi图的解决方案是：(i)计算Voronoi图，(ii)选取具有最大间隙（即到其定义面的距离）的Voronoi节点。带孔多边形的Voronoi图（即顶点和边的集合）可以在O(n log n)时间内计算，详见Fortune's algorithm (1986)。稍后，Chin et alii (1999) 提供了简单多边形中轴线的O(n)算法。然而，对于凸多边形，由于Aggarwal et alii于1989年已知道Voronoi图的时间最优算法，耗时仅为O(n)。该算法基本思想如下：考虑向内以单位速度移动的灰色偏移曲线。如果将此运动投影到三维空间（其中z轴是时间），则可获得多边形上的单位斜面屋顶。

Roof model

这个屋顶模型可以描述为：在每个多边形边缘上放置一个半空间，与多边形成45度斜面（使它们包含多边形），并相交。因此，如果您可以快速计算半空间的相交，则也可以快速计算凸多边形的Voronoi图。实际上，对于最大内切圆问题，我们不需要回到Voronoi图，而是取屋顶的一个峰值，标记最大内切圆的中心。

现在，半空间被“对偶化”为点，然后半空间的交集对应于其对偶点的凸包。Aggarwal等人现在发现了一种O(n)算法，用于从该设置中产生的点的凸包。

关于任何维度的凸多面体的Voronoi图算法的构建摘要可以在我的blog article中找到。

简单且快速的实现。一个更简单的计算Voronoi图的算法是由straight skeletons激发的。对于凸多边形，Voronoi图和直线骨架是相同的。

直线骨架实现Stalgo背后的算法基本上模拟了波前结构（灰色偏移曲线）的演变。对于凸多边形，这归结为找到崩溃边缘的序列。

因此，一个简单的O(n log n)算法可能如下所示：

构建多边形边缘的循环列表。在波前传播期间计算每条边的折叠时间，并将此事件插入优先队列。
直到队列为空为止：取出下一个边缘折叠事件：从循环结构中删除该边缘，并更新已删除边缘的相邻边缘的折叠时间。

实际上，您可以进一步简化上述算法：您不需要在优先队列中更新边缘折叠，而只需插入新的边缘折叠：由于边缘的新折叠时间严格较低，因此您始终会首先获得正确的事件并放弃其他事件，队列不会增长超过2n。因此，您不会影响O（n log n）的时间复杂度。

对于最大内切圆问题，您甚至可以进一步简化上述算法：由于在优先队列循环结束时最后一个三角形折叠，因此您要查找的Voronoi节点（resp. straight skeleton node）是确定的。

这个算法在实践中应该很快，只需要几行代码。