如何找到位于采样边界内的最大圆？ [英] 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屋！