如何找到位于采样边界内的最大圆? [英] How to find the largest circle that lies within a sampled boundary?

问题描述

给定一组 2D 点，它们是不规则形状的边界，该形状可能不是凸面且可能有内部孔洞，是否有算法可以找到适合边界的最大圆?

Given sets of 2D points which are the boundaries of an irregular shape, a shape which may not be convex and may have internal holes, is there an algorithm to find the largest circle that fits within the boundaries?

我进行了大量搜索，确实找到了接近的算法，例如最大的空心圆问题，但到目前为止我发现没有一个算法与我的约束相匹配.

I've done a good bit of searching, and I do find algorithms that are close, such as the largest empty circle problem, but none that I have found so far match the constraints I have.

推荐答案

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

Problem is not good defined since set of points don't bound any area. Boundary you mention should be some curve, probably polygon. Without that you can't say that there are internal holes, and also can't ask for circle to be within boundary. With this definition, you can create circle of any size on "outside" that touches few set points.

如果你使用多边形来指定边界，Aioobe 的链接是一个很好的链接.如果您重新定义问题以找到接触给定集合的至少 3 个点的最大半径圆，则与检查 达劳内三角剖分.

If you use polygon to specify boundary, Aioobe's link is good one. If you redefine problem to find maximal radius circle touching at least 3 points of given set, than it is same as checking for circumcircles of Dalaunay triangulation.

这篇关于如何找到位于采样边界内的最大圆?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！