圆分离距离 - 最近邻问题

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-tree。建立KD-Tree有一个前期的成本，但有利于更快地搜索最近的邻居。

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上找不到。最初它是空的。

稍微棘手的部分是确定if C contains any point nearer to T than nst。为此，可以考虑C中的唯一点（x，y，r），它是x和y中最接近于T的欧几里得，并且具有包含在长方体中的r范围的最大值。换句话说，长方体代表一组圆，其中心在x和y的矩形区域中，并且具有一定范围的半径。您要检查的点是代表中心距T最近且半径最大的圆。

注意，T的半径根本不参与算法。你只会承认在其他任何圈内有多远T的谎言的中心位置在。 （我希望这一开始像现在这样明显...）