predicado proximidad geométrica rápida

Question

Tengo 3 puntos (A, B y X) y una distancia (d). Necesito hacer una función que pruebe si el punto X está más cerca que la distancia d a cualquier punto en el segmento de línea AB.

La pregunta es, en primer lugar, si mi solución es correcta y luego encontrar una solución mejor (más rápida).

Mi primer paso es el siguiente

AX = X-A 
BX = X-B 
AB = A-B 

    // closer than d to A (done squared to avoid needing to compute the sqrt in mag) 
If d^2 > AX.mag^2 return true 

    // closer than d to B 
If d^2 > BX.mag^2 return true 

    // "beyond" B 
If (dot(BX,AB) < 0) return false 

    // "beyond" A 
If (dot(AX,AB) > 0) return false 

    // find component of BX perpendicular to AB 
Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 < d^2 

Este código va a terminar siendo el funcionamiento para una amplia serie de P y un gran conjunto de/B/trillizos D A con la intención de encontrar que pase de P para al menos un A/B/d, así que sospecho que hay una manera de reducir el costo total basado en eso, pero aún no lo he investigado.

(Por cierto:. Soy consciente de que algunos reordenamiento, algunos valores temporales y algunas identidades algebraicas podría disminuir el costo de los anteriores sólo les omitido para mayor claridad.)

---

EDIT: se trata de una Problema 2D (pero la solución que se generaliza a 3D sería genial

Editar: En una reflexión más profunda, espero que la tasa de aciertos sea de alrededor del 50%. El punto X se puede formar en una jerarquía anidada, así que espero poder para podar los grandes subárboles como todo pasa y todo falla. El A/B/d que limita a los trillizos será más de un tr ick.

Edición: d está en el mismo orden de magnitud que AB.

---

editar: Artelius ha publicado una buena solución. No estoy seguro de entender exactamente a qué se está enfrentando ya que me bajé en una tangente antes de entenderlo por completo. De todos modos, otro pensamiento vino a mi mente como resultado:

• Primera pieza de Artelius, precablea una matriz que colocará AB centrada en el origen y alineada con el eje X. (2 añade, 4 mul y 2 añade)
• veces todo en la primera cuadrante (2 abs)
• escala en X & Y para hacer que la porción central de la zona en un cuadrado de la unidad (2 mul)
• prueba si el punto está en que cuadrada (2 test) está así que deja de
• prueba de la tapa del extremo (volver a los valores sin escala
  • traducen en x para colocar el extremo en el origen (1 add)
  • cuadrado y agregar (2 mul, 1 agregar)
  • comparan con d^2 (1 cmp)

Estoy bastante seguro de que esto es mucho mejor que mi solución.

(si nada mejor viene sone Artelius recibe el "premio" :)

Answer 1

Si su juego de (a, B, C) en fijo , puedes calcular un par de matrices para que cada uno traduzca el sistema de coordenadas, por lo que la línea AB se convierte en el eje X, y el punto medio de AB es el origen.

I que esta es una manera simple de construir las matrices:

trans = - ((A + B)/2)  // translate midpoint of AB to origin 

rot.col1 = AB/AB.mag   // unit vector in AB direction 

         0 -1  
rot.col2 = rot.col1 * ( ) // unit vector perp to AB 
         1 0 

rot = rot.inverse()   // but it needs to be done in reverse 

A continuación, sólo se toman cada X y hacer rot * (X + trans).

La región en cuestión es simétrica en los ejes x e y, de modo que puede tomar el valor absoluto de la coordenada x y de la coordenada y.

Entonces sólo tiene que comprobar:

y < d && x < AB.mag/2   //"along" the line segment 
|| (x - AB.mag/2)^2 + y^2 < d^2 // the "end cap". 

Usted puede hacer otra truco; la matriz puede reducirse por un factor de AB.mag/2 (recuerde que las matrices solo se calculan una vez por (A, B) lo que significa que es mejor que encontrarlas sea más lento que el cheque real). Esto significa que su cheque se convierte en:

y < 2*d/AB.mag && x < 1 
|| (x - 1)^2 + y^2 < (2*d/AB.mag)^2 

haber sustituido dos instancias de AB.mag/2 con la constante 1, que podría ser un poco más rápido. Y, por supuesto, también puede precalcular 2*d/AB.mag y (2*d/AB.mag)^2.

Si esto funcionará más rápido que otros métodos depende de las entradas que le dé. Pero si la duración de AB es larga en comparación con d, creo que resultará considerablemente más rápido que el método que publicaste.

Answer 2

Hmmmmmmm .... ¿Cuál es la tasa de éxito? ¿Con qué frecuencia el punto "X" cumple con los requisitos de proximidad?

Creo que su algoritmo existente es bueno, y cualquier optimización adicional vendrá de sintonía con los datos reales. Por ejemplo, si el punto "X" cumple con la prueba de proximidad el 99% del tiempo, entonces creo que su estrategia de optimización debería ser considerablemente diferente de si solo pasa la prueba el 1% del tiempo.

---

Por cierto, cuando llegue al punto en el que se está ejecutando este algoritmo con miles de puntos, se debe organizar todos los puntos en un árbol K-dimensional (o KDTree). Hace que el cálculo del "vecino más cercano" sea mucho más simple.

Su problema es un poco más complejo que un vecino más cercano básico (porque está comprobando la proximidad de un segmento de línea en lugar de solo la proximidad a un punto) pero sigo creyendo que el KDTree ser útil.

Answer 3

Este código se ejecutará para un conjunto grande de P y un conjunto grande de trillizos A/B/d con la intención de encontrar todas las P que pasen al menos una A/B/d, así que sospecho que hay una manera de reducir el costo total basado en eso, pero aún no lo he investigado.

En el caso cuando d ~ AB, para un punto dado X, primero puede probar si X pertenece a una de las muchas esferas de radio d y al centro Ai o Bi. Mira la foto:

 ......  ..... 
    ........... ........... 
........................... 
.......A-------------B....... 
........................... 
    ........... ........... 
    .....   ..... 

Las dos primeras pruebas

If d^2 > AX.mag^2 return true 
If d^2 > BX.mag^2 return true 

son los más rápidos, y si d ~ AB son también los que tienen mayor probabilidad de tener éxito (dado que la prueba tiene éxito en todas). X dado, puede hacer todas las "pruebas de esfera" primero, y luego todos los finales:

Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2

Answer 4

Si leo esto correctamente, entonces esto es casi lo mismo que la prueba intersección clásico ray/esfera y usadas en trazado de rayos 3D.

En este caso, tiene una esfera en la ubicación X de radio d, y está tratando de averiguar si la línea AB corta la esfera. La única diferencia con el trazado de rayos es que en este caso usted tiene una línea específica AB, mientras que en el trazado de rayos del rayo es normalmente generalizar como lo origin + distance * direction, y no importa qué tan avanzado la línea infinita es AB+ .

En pseudo-código de mi propio trazador de rayos (basado en el algoritmo dado en "Una introducción al trazado de rayos" (ed Glassner):.

Vector v = X - A 
Vector d = normalise(B - A) // unit direction vector of AB 
double b = dot(v, B - A) 
double discrim = b^2 - dot(v, v) + d^2 
if (discrim < 0) 
    return false   // definitely no intersection 

Si ha llegado hasta aquí, . luego está algunos posibilidad de que se cumpla su condición Sólo hay que averiguar si la intersección (s) está en la línea AB:

discrim = sqrt(discrim) 
double t2 = b + discrim 
if (t2 <= 0) 
    return false    // intersection is before A 

double t1 = b - discrim 

result = (t1 < length(AB) || (t2 < length(AB)) 

Answer 5

Si el número de conjuntos de A/B/d es grande, y definitivamente está en 2D, considere usar R-trees (o sus equivalentes octogonales) donde cada entrada en el árbol R es el cuadro delimitador mínimo del A/B/d triple. Esto le permitiría eliminar la necesidad de probar muchas de las tripletas A/B/D. & enfoque la potencia de su CPU solo en las pocas donde cada punto X se encuentra dentro de los cuadros delimitadores del triple A/B/d. Luego haz una prueba más detallada como la que mencionas.