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)));