Distanza di separazione cerchio - Problema vicino più prossimo

Question

Ho un set di cerchi con posizioni e raggi dati su un piano bidimensionale. Voglio determinare per ogni cerchio se si interseca con qualsiasi altro cerchio e la distanza necessaria per separare i due. Sotto la mia attuale implementazione, passo semplicemente a tutte le possibili combinazioni di cerchi e poi eseguo i calcoli. Sfortunatamente, questo algoritmo è O (n^2), che è lento.

I cerchi saranno generalmente raggruppati in gruppi e avranno raggi simili (ma diversi). Il massimo approssimativo per il numero di cerchi è intorno a 200. L'algoritmo non deve essere esatto, ma dovrebbe essere vicino.

Ecco un (lento) implementazione Al momento ho in 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++; 
} 

Inoltre, le sarei grato se lei ha spiegato un buon algoritmo (KD Tree?) In parole povere: -/

Answer 1

Per i principianti, il tuo algoritmo sopra verrà notevolmente accelerato se hai saltato la chiamata SQRT. Questa è la più semplice ottimizzazione per confrontare le distanze. È anche possibile precomputare la distanza "raggio quadrato" in modo da non ricalcolarla in modo ridondante.

Inoltre, sembra che ci siano molti altri piccoli bug in alcuni dei vostri algoritmi. Ecco la mia opinione su come risolverlo qui sotto.

Inoltre, se si desidera eliminare l'algoritmo O (N-Squared), è possibile utilizzare uno kd-tree. C'è un costo iniziale per la costruzione dell'albero KD, ma con il vantaggio di cercare i vicini più vicini più velocemente.

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

Questo articolo è stato inattivo per molto tempo, ma ho incontrato e risolto questo problema abbastanza bene, quindi pubblicheremo in modo che gli altri non hanno a che fare la stessa testa di graffiare.

È possibile trattare il problema del vicino di cerchio più vicino come un punto 3d più vicino alla ricerca del vicino in un albero di kd o in un albero di ocra. Definire la distanza tra due cerchi A e B come

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

Questa è una quantità negativa se i cerchi si sovrappongono. Per questa discussione assumerò un albero, ma un albero kd con k = 3 è simile.

Memorizza una tripla (x, y, r) nell'ombra per ciascun cerchio.

Per trovare il vicino più prossimo a un cerchio bersaglio T, utilizzare l'algoritmo standard:

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 

Qui nst è un riferimento al cerchio più vicino al T trovato finora. Inizialmente è nullo.

La parte leggermente difficile sta determinando if C contains any point nearer to T than nst. Per questo è sufficiente considerare il punto unico (x, y, r) all'interno di C che è Euclideo più vicino a T in xey ed ha il valore massimo della scala r contenuta nel cuboide. In altre parole, il cuboide rappresenta un insieme di cerchi con centri che si estendono su un'area rettangolare in x e y e con un intervallo di raggi. Il punto che si desidera controllare è quello che rappresenta il cerchio con il centro più vicino a T e con il raggio più grande.

Nota il raggio di T non ha alcun ruolo nell'algoritmo.Ti viene concessa solo la distanza all'interno di qualsiasi altro cerchio al centro di T bugie. (Vorrei che all'inizio fosse così ovvio come sembra ora ...)