algorithm - 如何获得圆的下界和上界半径？

Question

问题和附近的解​​决方案图片:

问题:网格与每个节点的距离相等。网格的每个小节点都是一个半径为 r 的圆(图:灰色圆)，如果我们制作任何圆(图:蓝色)那么我们如何制作一组具有上界(图:红色圆)和下界的圆(图:红圈)。基本上我们需要找到上界半径和下界半径。

已知值是:

1. 小圆(灰色)的半径r。
2. 两个灰色圆圈/node_of_grid 从中心到中心的距离 = 4 X r。
3. 大圆(蓝色)的半径 rb。//这可能会有所不同，但将是 r 的倍数。在此图中，直径 d = 2(20 x r)。
4. 大圆心只能是小圆心。

如何找到上圆和下圆的半径。大圆周内的每个蓝色小圆圈都应在上限之下，反之亦然。

目前我想出了这个不正确的解决方案: unpper_bound_radius = rb + (r + (rb/(3.1415926 * 2r))) lower_bound_radius = rb - (r + (rb/(3.1415926 * 2r)))

谢谢

Answer 1

如果您正在寻找一种算法来确定哪些灰点与蓝色圆圈相交，并计算包含所选灰点的边界的半径，您可以这样做:

• 给内外边界一个等于蓝色圆圈的半径。
• 中心正上方与蓝色圆圈相交或刚好在蓝色圆圈上方的灰点是起点。
• 计算该点到中心点的距离；如果它在 rb-r 和 rb+r 之间，蓝色圆圈与这个灰色点相交。
• 如果相交，根据需要将内边界调整为distance - r，将外边界调整为distance + r。
• 如果不是，而且距离比较远，试试下面的网格点；如果不是，并且距离较小，请尝试右侧的网格点。
• 这样做，直到您移出 45° 扇区；你只需要检查八分之一的圆，其他结果是对称的。

示例计算:

• 顶部的第一个网格点距中心 5×4r；边界在 5×4r-r 和 5×4r+r。
• 右边的下一个网格点距中心 5.09902×4r，因此外边界增加到 5.09902×4r+r。
• 右边的下一个网格点在距中心 5.38516×4r 的位置，即在蓝色圆圈外 1.54066×r(太远)。
• 下一个向下的格点是距离中心4.47216×4r，也就是蓝圈内1.88854×r(太近)。
• 右边的下一个网格点正好位于距中心 5×4r 的位置，因此边界不会改变。
• 右边的下一个网格点距中心 5.65686×4r，在蓝色圆圈外 2.62742×r(太远)。
• 下一个向下的网格点向右倾斜超过 45°。

结果:内边界在5×4r-r，外边界在5.09902×4r+r。

function boundaries(b) {
    var i = b, o = b, x = 0, y = Math.ceil(b / 4) * 4;
    while (Math.atan2(y, x) >= Math.PI / 4) {
        var d = Math.sqrt(x * x + y * y);
        if (d < b - 1) x += 4;           // too close, go right
        else if (d > b + 1) y -= 4;      // too far, go down
        else {                           // intersection
            if (i > d - 1) i = d - 1;    // adjust inner
            if (o < d + 1) o = d + 1;    // adjust outer
            x += 4;                      // go right
        }
    }
    return {i: i, o: o};
}

var res = boundaries(20);
document.write("inner: r&times;" + res.i + "<br>outer: r&times;" + res.o);