algorithm - 找到一组圆中完全被覆盖的圆

Question

我们在一个矩形区域中有一组圆，所有圆都有相同的半径，我想找到完全被其他圆覆盖的圆。 有什么算法吗？

Answer 1

几何

首先找到所有圆心距主圆中心距离小于2×r的圆；距离较远的圆圈不会重叠。

^{示例:主(黑色)圆圈和 3 个重叠圆圈。}

然后，要知道主圆被完全覆盖，您必须找到一组圆，其中位于主(黑色)圆内的两个圆的每个相交点都被第三个圆覆盖。

算法

实际上，您从 2 个圆圈(例如蓝色和红色)开始，找到它们相交的 2 个点(紫色点)。如果一个或两个点都在主(黑色)圆内，则这些点必须被一个附加圆覆盖。

然后，逐个添加一个额外的圆圈(例如绿色)，并查看它是否覆盖了未覆盖的点(在示例中确实覆盖了)。然而，这个新圆圈添加了与集合中已有的其他圆圈(蓝色和红色)的新交点；找到这些点(青色和棕色点)并检查它们是否被任何圆圈覆盖(青色点被红色圆圈覆盖，但棕色点未被蓝色圆圈覆盖)。

不断向集合中添加圆，直到主(黑色)圆内的每个交点都被集合中的另一个圆覆盖(在这种情况下，整个主圆都被覆盖)，或者直到用完圆(在这种情况下)如果主圆没有被完全覆盖)。

特殊情况:
如果其中一个圆的中心点与主圆完全相同，则它会自行覆盖主圆。
如果没有一个圆在主圆内有交点，则主圆不被覆盖。

代码示例

此代码示例演示了如何找到两个圆的交点，它处理了算法中所需的大部分几何图形。

function intersections(p, q, r) {
    var d = distance(p, q);
    if (d > 2 * r) return [];
    var m = middle(p, q);
    if (d == 2 * r) return [m];
    var a = angle(p, q) + Math.PI / 2;
    var l = length(d, r);
    return [{x: m.x + l * Math.cos(a), y: m.y + l * Math.sin(a)},
            {x: m.x - l * Math.cos(a), y: m.y - l * Math.sin(a)}];

    function distance(p, q) {
        return Math.sqrt(Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2));
    }
    function middle(p, q) {
        return {x: (p.x + q.x) / 2, y: (p.y + q.y) / 2};
    }
    function angle(p, q) {
        return Math.atan2(q.y - p.y, q.x - p.x);
    }
    function length(d, r) {
        return Math.sqrt(Math.pow(r, 2) - Math.pow(d, 2) / 4);
    }
}

document.write(JSON.stringify(intersections({x:1, y:2}, {x:3, y:-4}, 5)));