圆间隔距离 - 最近邻问题

Question

我有一组在二维平面上具有给定位置和半径的圆。我想确定每个圆是否与任何其他圆相交以及分隔两个圆所需的距离。在我当前的实现下，我只是遍历所有可能的圆圈组合，然后进行计算。不幸的是，这个算法是 O(n^2)，速度很慢。

这些圆通常会聚集成组，并且它们将具有相似（但不同）的半径。圆圈数量的最大值大约为 200 左右。该算法不必非常精确，但应该接近。

这是我目前在 JavaScript 中的一个（缓慢的）实现：

// Makes a new circle
var circle = function(x,y,radius) {
    return {
        x:x,
        y:y,
        radius:radius
    };
};

// These points are not representative of the true data set. I just made them up.
var points = [
    circle(3,3,2),
    circle(7,5,4),
    circle(16,6,4),
    circle(17,12,3),
    circle(26,20,1)
];


var k = 0,
    len = points.length;
for (var i = 0; i < len; i++) {
    for (var j = k; j < len; j++) {
        if (i !== j) {
            var c1 = points[i],
                c2 = points[j],
                radiiSum = c1.radius+c2.radius,
                deltaX = Math.abs(c1.x-c2.x);

            if (deltaX < radiiSum) {
                var deltaY = Math.abs(c1.y-c2.y);

                if (deltaY < radiiSum) {
                    var distance = Math.sqrt(deltaX*deltaX+deltaY*deltaY);

                    if (distance < radiiSum) {
                        var separation = radiiSum - distance;
                        console.log(c1,c2,separation);
                    }
                }
            }
        }
    }

    k++;
}

另外，如果您用简单的英语解释一个好的算法（KD 树？），我将不胜感激：-/

Answer 1

对于初学者来说，如果您跳过 SQRT 调用，上面的算法将会大大加快。这是最著名的比较距离的简单优化。您还可以预先计算“平方半径”距离，这样就不必重复地重新计算它。

此外，您的某些算法中似乎还存在许多其他小错误。下面是我对如何修复它的看法。

另外，如果你想摆脱 O(N-Squared) 算法，你可以考虑使用 kd-树。构建 KD 树需要一定的前期成本，但其好处是可以更快地搜索最近的邻居。

function Distance_Squared(c1, c2) {

    var deltaX = (c1.x - c2.x);
    var deltaY = (c1.y - c2.y);
    return (deltaX * deltaX + deltaY * deltaY);
}



// returns false if it's possible that the circles intersect.  Returns true if the bounding box test proves there is no chance for intersection
function TrivialRejectIntersection(c1, c2) {
    return ((c1.left >= c2.right) || (c2.right <= c1.left) || (c1.top >= c2.bottom) || (c2.bottom <= c1.top));
}

    var circle = function(x,y,radius) {
        return {
            x:x,
            y:y,
            radius:radius,

            // some helper properties
            radius_squared : (radius*radius), // precompute the "squared distance"
            left : (x-radius),
            right: (x+radius),
            top : (y - radius),
            bottom : (y+radius)
        };
    };

    // These points are not representative of the true data set. I just made them up.
    var points = [
        circle(3,3,2),
        circle(7,5,4),
        circle(16,6,4),
        circle(17,12,3),
        circle(26,20,1)
    ];


    var k = 0;
    var len = points.length;
    var c1, c2;
    var distance_squared;
    var deltaX, deltaY;
    var min_distance;
    var seperation;

    for (var i = 0; i < len; i++) {
        for (var j = (i+1); j < len; j++) {
            c1 = points[i];
            c2 = points[j];

            // try for trivial rejections first. Jury is still out if this will help
            if (TrivialRejectIntesection(c1, c2)) {
                 continue;
            }



            //distance_squared is the actual distance between c1 and c2 'squared'
            distance_squared = Distance_Squared(c1, c2);

            // min_distance_squared is how much "squared distance" is required for these two circles to not intersect
            min_distance_squared = (c1.radius_squared + c2.radius_squared + (c1.radius*c2.radius*2)); // D**2 == deltaX*deltaX + deltaY*deltaY + 2*deltaX*deltaY

            // and so it follows
            if (distance_squared < min_distance_squared) {

                // intersection detected

                // now subtract actual distance from "min distance"
                seperation = c1.radius + c2.radius - Math.sqrt(distance_squared);
                Console.log(c1, c2, seperation);
            }
        }
    }

Answer 2

这篇文章已经休眠很长时间了，但我已经遇到并很好地解决了这个问题，所以将发布，以便其他人不必做同样的头痛。

您可以将最近圆邻居问题视为 kd 树或八叉树中的 3d 点最近邻搜索。将两个圆 A 和 B 之间的距离定义为 当且

D(A,B) =  sqrt( (xA - xB)^2 + (yA - yB)^2 ) - rA - rB

仅当圆重叠时，这是一个负数。对于本次讨论，我将假设一个八叉树，但 k=3 的 kd 树是类似的。

在每个圆的八叉树中存储一个三元组 (x,y,r)。

要找到距离目标圆 T 最近的邻居，请使用标准算法：

def search(node, T, nst)
  if node is a leaf
    update nst with node's (x,y,r) nearest to T
  else
    for each cuboid C subdividing node (there are 8 of them)
       if C contains any point nearer to T than nst
          search(C, T, nst)
  end
end

这里 nst 是对迄今为止找到的距离 T 最近的圆的引用。最初它是空的。

稍微棘手的部分是确定 C 是否包含比 nst 更接近 T 的任何点。为此，考虑 C 中唯一点 (x,y,r) 就足够了，该点是 x 和 y 中最接近 T 的欧几里得点，并且具有长方体中包含的 r 范围的最大值。换句话说，长方体表示一组圆，其圆心分布在 x 和 y 方向上的矩形区域上，并且具有一定的半径范围。您要检查的点是代表圆心最接近 T 且半径最大的圆的点。

请注意，T 的半径在算法中根本不起作用。您只关心 T 的中心在任何其他圆内有多远。 （我希望这一点一开始就像现在一样明显......）