Distancia de separación del círculo - Vecino más cercano Problema

Question

Tengo un conjunto de círculos con ubicaciones y radios dados en un plano bidimensional. Quiero determinar para cada círculo si se está cruzando con cualquier otro círculo y la distancia que se necesita para separar los dos. Bajo mi implementación actual, examino todas las posibles combinaciones de círculos y luego hago los cálculos. Desafortunadamente, este algoritmo es O (n^2), que es lento.

Los círculos generalmente se agruparán en grupos, y tendrán radios similares (pero diferentes). El máximo aproximado para el número de círculos es alrededor de 200. El algoritmo no tiene que ser exacto, pero debe estar cerca.

Aquí está una (lenta) aplicación actualmente tengo en 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++; 
} 

Además, yo apreciaría si usted explicó un buen algoritmo (KD árbol?) En la llanura Inglés: -/

Answer 1

Para empezar, su algoritmo anterior se acelerará mucho si se salta la llamada SQRT. Esa es la optimización simple más conocida para comparar distancias. También puede calcular previamente la distancia del "radio al cuadrado" para que no la vuelva a calcular de forma redundante.

Además, parece que hay muchos otros pequeños errores en algunos de sus algoritmos. Aquí está mi opinión sobre cómo solucionarlo a continuación.

Además, si desea deshacerse del algoritmo O (N-Squared), puede consultar el uso de kd-tree. Hay un costo inicial de construir el KD-Tree, pero con la ventaja de buscar vecinos más cercanos mucho más rápido.

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

Este artículo ha estado inactivo durante mucho tiempo, pero me he encontrado y solucionado este problema razonablemente bien, por lo publicaremos para que otros no tienen que hacer lo mismo rascarse la cabeza.

Puede tratar el problema vecino circular más cercano como una búsqueda de un vecino de punto 3d más cercano en un kd-tree o octree. Defina la distancia entre dos círculos A y B como

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

Esta es una cantidad negativa si los círculos se superponen. Para esta discusión asumiré un octárbol, pero un árbol kd con k = 3 es similar.

Almacena un triple (x, y, r) en el octárbol para cada círculo.

Para encontrar el vecino más cercano a un círculo objetivo T, utilice el algoritmo estándar:

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 

Aquí nst es una referencia al círculo más próximo a T encontrado hasta ahora. Inicialmente es nulo.

La parte un poco complicada es la determinación de if C contains any point nearer to T than nst. Para esto es suficiente considerar el punto único (x, y, r) dentro de C que es euclidiano más cercano a T en xey y tiene el valor máximo del rango r contenido en el paralelepípedo. En otras palabras, el cuboide representa un conjunto de círculos con centros que abarcan un área rectangular en xey y con un rango de radios. El punto que desea verificar es el que representa el círculo con el centro más cercano a T y con el radio más grande.

Tenga en cuenta que el radio de T no forma parte del algoritmo.Solo le interesan cuán lejos está dentro de cualquier otro círculo el centro de T. (Desearía que esto hubiera sido tan obvio al principio como parece ahora ...)