我需要找到一个最大的凸多边形内接圆，我已经搜索了许多网站，我得到这可以通过使用delaunay三角测量。我在使用cgal的算法的cgal讨论中发现athread：
使用CGAL可以轻松计算：
首先，计算点的delaunay三角剖分。
然后，迭代三角剖分的所有有限面。
对于每个有限面f
计算它的外心c
在三角测量中找到c（为了加快速度，你可以给
f的顶点作为点位置的起始提示）
如果locate（c，hint）返回的面是有限的，那么
c位于点的凸壳中，因此，f是候选者
如果f是这样一个候选面，计算它的平方外半径
只保留外圆半径平方最小的面
cgal手册（第2d章三角测量，以及一些东西
从内核）显示了执行此操作的每个基本函数
我对这个算法的最后一部分有点困惑。当我读到它的时候，我的理解是，三角测量面的最小外半径是最大的被测圆的半径。但是从Delaunay三角剖分的多边形的例子来看，即使是最小的外接圆有时也不适合多边形内部，那么这怎么可能具有与最大内接圆相同的半径呢？
最佳答案
多边形的最大内接圆。
多边形最大内接圆问题的经典计算几何解法是利用多边形面的“AA>”。多边形的generalized Voronoi diagram。这种方法适用于更一般的设置，如带有孔的多边形，请参见类似问题的medial axis。
凸输入。
然而，输入多边形的凸性给问题带来了更多的结构，我想对此进行评论。考虑下面的凸输入多边形（黑色）、Voronoi图（蓝色）和以Voronoi节点为中心的最大内接圆（绿色）。
基于voronoi的经典解是（i）计算voronoi图，（ii）取间隙最大的voronoi节点（即到其定义面的距离）。
有孔多边形（即顶点和边的集合）的Voronoi图可以在O（n logn）时间，c.f.stackoverflow answer内计算后来的AA>给出了一个简单多边形的中轴的O（n）算法。
然而，对于凸多边形，由于Fortune's algorithm (1986)，在O（n）时间内运行的Voronoi图的时间最优算法在1989年就已经知道了该算法基本上遵循以下思想：考虑单位速度向内移动的灰色偏移曲线如果将这个运动投射到Z轴为三的空间，则在多边形上得到单位倾斜屋顶：
该屋盖模型还具有以下特点：在每个多边形边缘上放置一个与多边形成45°坡度的半空间（使它们包含多边形），并将它们全部相交。所以如果你能快速计算半空间的交集，那么你也能快速计算凸多边形的voronoi图。事实上，对于最大内接圆问题，我们不需要回到Voronoi图，而是取屋顶的一个顶峰，这标志着最大内接圆的中心。
现在半空间被对偶成点，然后半空间的交点对应其对偶点的凸壳Aggarwal等人现在找到了一个O（n）算法的凸包点，源于这个设置。
在我的AChin et alii (1999)中可以找到这种构造的摘要，它导致了任意维凸多面体的Voronoi图算法。
简单快速的实现计算voronoi图的简单算法是由Aggarwal et alii驱动的。对于凸多边形，voronoi图和直骨架是相同的。
直接骨架实现后的算法基本上模拟了波前结构（灰度偏移曲线）的演化。对于凸面多边形，这会减少查找折叠边的序列。
所以一个简单的o（n logn）算法可以是这样的：
构造多边形边的圆形列表。计算波前传播过程中每个边缘的崩溃时间，并将此事件插入优先级队列。
直到队列为空：取出下一个边折叠事件：从圆形结构中移除边并更新移除边的相邻边的折叠时间。
实际上，您可以进一步简化上面的算法：您不需要更新优先级队列中的边折叠，只需插入新的边折叠：由于新的边折叠时间严格较低，您总是先得到正确的事件，然后忽略其他事件，队列的增长不超过2n。因此，您不会损害o（n logn）时间复杂度。
对于最大内接圆问题，可以进一步简化上述算法：Voronoi节点（RESP）。（直骨架节点）查找的原因是循环结束时优先级队列上的最后一个三角形折叠。
这个算法在实践中应该很快，而且只需要几行代码。
关于algorithm - Delaunay三角剖分和最大内切圆的混淆，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27872964/