寻找多个圆内一定半径范围内的点的算法？

Question

我有很多半径为1的圆，需要找到一个点(或者更可能是许多点的平均值)，这个点包含在所有这些圆的半径内。是否有一种算法可以做到这一点，而不必强制执行它？

下面是我添加的评论，更加具体地说明了我的问题：

"为了增加一些具体性: 我试图找到一个点(或者非常接近它的地方，至少在0.05的单位精度范围内)。唯一提供给我找到这个点的信息是一组大约50个点，所有这些点都在某个误差半径(在本例中为1个单位)内。因此，我试图找到的点在所有给定的圆的半径内。我正在寻找一种算法，除了强制执行大量随机点，直到有1个满足所有条件之外。如果我的问题非常模糊，对不起，这是一个抽象的问题，很难解释。"

- nardavin

---

你能给一个例子吗？许多点的平均值是什么意思？包含在半径内是指什么？你想要一个在所有圆的交集内部的点吗？ - A. Sarid

为了更具体一些：我正在尝试寻找一个点（或者至少在非常靠近该点的某个地方，至少精度在0.05单位以内）。给定给我的唯一信息是大约50个点的集合，所有这些点都在某个误差半径（在本例中为1单位）以内。因此，我要找的点位于所有给定的圆的半径范围内。我正在寻找一种不是通过暴力随机生成大量点直到符合所有条件的算法。如果我的问题很模糊，请原谅，这是一个抽象的问题，很难解释。 - nardavin

此外，圆圈不一定均匀分布在点周围，因此圆心的平均值不是一个有效的估计。 - nardavin

@MCEmperor 它已经完成了。 - nardavin

看一下这个非常相似的问题从一组坐标中确定准确的中心点，另外你应该添加一个样本输入/输出图像，这样我们才能明确地了解你的意思。 - Spektre

Answer 1

这个问题的最简单解决方案是 O(n^3) 的时间复杂度解决方案。

其中，n = 圆的数量

至少一个圆与圆之间的交点将是一个好答案。

找出所有圆之间可能的交点。现在，在这些交点中找到一个交点，它在所有其他圆内部。

以下是一个简单的伪代码：

vector<Point> points;
vector<Circles> circs;    
for(i=0;i<circs.size();i++) {
for(j=i+1;j<circs.size();j++) {
    points.push_back(find_intersection(circs[i],circs[j]));
    //here you will find at most 2 intersections push both in this list
}

for(i=0;i<points.size();i++) {
    int cicrs_covered = 0;
    for(j=0;j<circs.size();j++) {
        if(is_point_inside_circle(points[i],circs[j])) {
            cicrs_covered++;
        }
    }
    if(cicrs_covered == circs.size()) {
        //answer is points[i]
    }
}

- Ayon Nahiyan