圓分離距離 - 最近鄰問題

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的謊言的中心位置在。 （我希望這一開始像現在這樣明顯...）