如何找到嵌套在采样边界内的最大圆？

Question

给定一组二维点，它们是不规则形状的边界，可能不是凸的，并且可能有内部孔洞。是否存在一种算法来找到适合于这些边界的最大圆？

我已经做了很多搜索，我确实找到了一些接近的算法，例如最大空心圆问题，但迄今为止没有找到符合我的约束条件的算法。

- drb

---

@aioobe：这并不是直接的重复，因为该算法适用于多边形，而我的边界是不规则点集。但是感谢您指出这一点，因为我认为我可以进行调整。 - drb

@Michał：最大点数通常会在低百位数。我认为实现最简单的方法就足够了。 - drb

一张图片胜过千言万语！给我们展示一个你所说的例子。 - Jean-François Corbett

一个有限点集通常围成零面积，因此按照所述问题的答案是微不足道的（以任何点为中心的零半径圆）。也许您需要更准确地说明它。 - n. m.

@drb 什么是多边形和一组不规则点之间的区别？多边形只是由一组点定义的线段集合。 - corsiKa

Answer 1

动机. 给定由采样形状的点所给出的形状，首先让我想起了alpha shapes的概念以及它们与持久拓扑的关系。请参见这些幻灯片获取相关图片。

无论如何，alpha shapes与点的Voronoi图有密切关系，而点的Voronoi图则是作为Delaunay三角剖分的对偶平面图的。

解决方案. 我建议考虑所有的Voronoi节点，并将具有最大间隙半径（到其定义点的距离）的节点作为您要查找的点：

在Delaunay三角剖分的对偶设置中，此节点对应于具有最大外接圆的Delaunay三角形。

这个解决方案也受到计算几何中最大内切圆问题的启发。

另一种看待它的方式是Voronoi图的草火解释：考虑从每个输入点开始的草火。火在每个方向上以单位速度增长。中间的红点是凸包中最后被到达的点。

分析和实现。 该算法的时间复杂度为O(n log n)用于Voronoi图，对于具有最大间隙的Voronoi节点则为O(n)。一个经典的实现是qhull。似乎还有一个C++实现在boost中可以为您完成此项任务。但是任何Delaunay三角剖分代码也可以。

可能存在的问题。 如果形状类似于Omega字母-它具有一个大的口袋-那么具有最大间隙的Voronoi节点就在Omega形状的“外面”。因此，需要更好地掌握采样形状的“内部”和“外部”的概念。这里再次提到的alpha shape可能会有所帮助，例如Edelsbrunner发明的调查。

- S. Huber

Answer 2

问题没有很好地定义，因为点集不限制任何区域。你提到的边界应该是一些曲线，可能是多边形。如果没有这个定义，就无法说有内部孔洞，也不能要求圆在边界内。根据这个定义，你可以在“外面”上创建任意大小的圆，接触几个点。

如果你使用多边形来指定边界，Aioobe的链接是一个好选择。如果你重新定义问题，寻找至少接触给定点集的三个点的最大半径圆，那么它与检查Dalaunay三角剖分的周围圆相同。

- Ante

Answer 3

一个非常愚蠢的算法 :) （可能有更快的算法）

最大的圆应该至少与3个对象（对象可以是顶点或线）相接触。

因此，您可以计算所有组合O(n^3)，为每个组合构建一个圆形，检查它是否在区域内（O(n)），并选择最大的一个。总共 - O(n^4)。

- maxim1000

---

@JimMischel：胡说八道。最大圆总是接触3个点的观察结果，将潜在需要搜索以找到最优解的解集从无限大小减少到了多项式大小。 - j_random_hacker