给定一组二维点，这些点是不规则形状的边界，该形状可能不是凸的并且可能有内孔，是否有一种算法可以找到适合边界的最大圆？
我已经做了很多搜索，并且确实找到了接近的算法，例如最大的空圆问题，但到目前为止我发现没有一个与我所拥有的约束相匹配。
动机。由对形状进行采样的点给出的形状首先让我想起了以下概念阿尔法形状以及它们与持久拓扑的关系。看看这些slides以获得相关图片。
无论如何，阿尔法形状与沃罗诺伊图点，它是对偶（作为平面图）德劳内三角剖分.
解决方案。我的建议是考虑所有 Voronoi 节点，并将间隙半径（到其定义点的距离）最大的节点作为要查找的点：
在 Delaunay 三角剖分的对偶设置中，该节点对应于具有最大外接圆的 Delaunay 三角形。
该解决方案也是受到计算几何中的最大内接圆问题的启发。
另一种看待它的方法是 Voronoi 图的草地火灾解释：考虑从每个输入点开始的草地火灾。火势以单位速度向各个方向蔓延。中间的红点是凸包内最晚到达的点。
分析与实施。该算法的时间复杂度对于 Voronoi 图来说是 O(n log n)，而找到间隙最大的 Voronoi 节点的时间复杂度是 O(n)。一个经典的实现是qhull。似乎有一个 C++ 实现boost这对你来说是这样的。但任何 Delaunay 三角剖分代码也都可以。
可能出现的问题。如果形状类似于具有大口袋的 Omega 字母，则具有最大间隙的 Voronoi 节点位于 Omega 形状的“外部”。因此，人们需要更好地掌握采样形状的“内部”和“外部”概念。在这里，最初提到的 alpha 形状可能会有所帮助，参见： Asurvey由发明阿尔法形状的 Edelsbrunner 设计。
