寻找不含点的给定半径的圆

Question

我正在研究一个问题，基本上可以归结为以下几个方面：

给予：

• 一组(x,y)点。这一盘可能有0点。
• 最小和最大x值和y值，其中最小值总是非负的.
• 半径r

确定是否可以将半径为r的圆放置在平面上的任何位置，使圆处于界内，并且不包含点的任何，如果是，则返回该位置。

交叉点是允许的-从集合中的点可以相交圆，但它们不能包含在圆中。圆可以切向接触最小值、最大值x值和y值，但不能超出界限。

结果将是一个(x,y)点，其中圆心将去，或一些虚拟的结果(即(-1,-1))/failure，如果没有这样的位置。如果存在多个有效解决方案，则可以返回任何解决方案。

对于这样的位置，有什么解决算法的想法吗？我将在java中实现，但我可以使用psuedocode。

Answer 1

回答

如果n是点的数目，我将告诉n >= 2情况的解决方案。

你可以找到两个圆圈，通过选定的2分。

​

​

如果圆圈在一个范围内，并且它正好包含零点，你可以输出这个圆圈。

所以，你可以选择对点(p[i], p[j])和检查所有的圆圈。

如果你不知道两个圆的解，请读这个。

通过两点的给定半径圆

您可以这样实现：

for i = 0 to n-1
    for j = 0 to n-1
        if dist(p[i], p[j]) <= 2 * r
            circle c1, c2 = circle that goes through p[i] and p[j]
            bool f1 = true
            for k = 0 to n-1
                if p[k] is in c1 -> f1 = false
            if f1 is true -> return center of c1
            bool f2 = true
            for k = 0 to n-1
                if p[k] is in c2 -> f2 = false
            if f2 is true -> return center of c2

如果找不到，可以使用蒙特卡罗算法。

如果你在随机选择的数千个点中找不到，我认为“找不到”是可以的。

Answer 2

构建一个切入点集的Delaunay三角剖分。对于每一点，执行以下过程。

在你的点周围画一个半径为2r的圆。如果所有的相邻点都在圆内，这个点是坏的，继续到下一个点。

如果不是，请考虑所有这个顶点的三角形。它们形成一些凸多边形。如果必要的话，把它修剪到你所在地区的边界(它仍然很复杂)。现在，您需要找到半径为r的圆，它位于这个多边形的内部，不包含当前点。这是一个简单的几何练习(在每对相邻的边缘上画一个半径r切线的圆；如果任何这样的圆不包含点集上的任何点，那么就完成了)。

你可以用不同的方式加速这一点(例如，如果任意三角形的外圈完全在你的矩形内，半径是r或更大，你就完成了)。