如何找到位于采样边界内的最大圆？

Question

给定一组2D点作为不规则形状的边界,一个可能不是凸面并且可能有内部孔的形状,是否有算法找到适合边界的最大圆？

我已经做了很多搜索,我确实找到了接近的算法,比如最大的空圆问题,但到目前为止我找不到的算法与我的约束相匹配.

Answer 1

问题没有很好地定义，因为点集不限制任何区域。你提到的边界应该是一些曲线，可能是多边形。没有它，你就不能说有内孔，也不能要求圆在边界之内。通过这个定义，您可以在“外部”创建任意大小的圆，接触很少的设定点。

如果您使用多边形来指定边界，Aioobe 的链接是不错的选择。如果您重新定义问题以找到接触给定集合的至少 3 个点的最大半径圆，则与检查Dalaunay 三角剖分的外接圆相同。