查找给定半径的不包含点的圆

Question

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

给定：

null

对于这样一个位置，有什么算法的想法吗？我最终将使用java实现，但我可以使用PsuedoCode。

Answer 1

回答

如果n是点数，我将给出情况n>=2的解法。

你可以找到两个圆，通过选择的2点。

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

如果找不到，可以用蒙特卡洛算法。
如果你在随机选择的几千个点中找不到，我认为“找不到”是可以的。