Algoritmo para encontrar el objeto más cercano en la cuadrícula 2D

Question

Supongamos que tiene una cuadrícula 2D con cada punto en la cuadrícula que tiene x número de objetos (con x> = 0). Tengo problemas para pensar en un algoritmo clean, de modo que cuando un usuario especifica una coordenada, el algoritmo encuentre la coordenada más cercana (incluida la que se especifica) con un objeto sobre ella.

Por simplicidad, asumiremos que si 2 coordenadas están a la misma distancia, se devolverá la primera (o si su algoritmo no funciona de esta manera, entonces la última, no importa).

Editar: Una coordenada que está a 1 distancia debe ser 1 arriba, abajo, izquierda o derecha. Las coordenadas que están en diagonal son 2.

Como nota al margen, ¿qué es una gran referencia gratuita en línea para los algoritmos?

Answer 1

uDate

Con la nueva información:

Suponiendo que una coordenada en diagonal es 2 distancia

Este algoritmo funcionaría. El algoritmo busca hacia afuera en una forma un poco espiral probando cada punto en cada 'anillo' iniciado desde adentro.

Tenga en cuenta que no maneja situaciones fuera de límites. Entonces debe cambiar esto para que se ajuste a sus necesidades.

int xs, ys; // Start coordinates 

// Check point (xs, ys) 

for (int d = 1; d<maxDistance; d++) 
{ 
    for (int i = 0; i < d + 1; i++) 
    { 
     int x1 = xs - d + i; 
     int y1 = ys - i; 

     // Check point (x1, y1) 

     int x2 = xs + d - i; 
     int y2 = ys + i; 

     // Check point (x2, y2) 
    } 


    for (int i = 1; i < d; i++) 
    { 
     int x1 = xs - i; 
     int y1 = ys + d - i; 

     // Check point (x1, y1) 

     int x2 = xs + d - i; 
     int y2 = ys - i; 

     // Check point (x2, y2) 
    } 
} 

antigua versión

Suponiendo que en su rejilla 2D la distancia entre (0, 0) y (1, 0) es el mismo que (0, 0) y (1, 1) . Este algoritmo funcionaría. El algoritmo busca hacia afuera en una forma un poco espiral probando cada punto en cada 'anillo' iniciado desde adentro.

Tenga en cuenta que no maneja situaciones fuera de límites. Entonces debe cambiar esto para que se ajuste a sus necesidades.

int xs, ys; // Start coordinates 

if (CheckPoint(xs, ys) == true) 
{ 
    return (xs, ys); 
} 

for (int d = 0; d<maxDistance; d++) 
{ 
    for (int x = xs-d; x < xs+d+1; x++) 
    { 
     // Point to check: (x, ys - d) and (x, ys + d) 
     if (CheckPoint(x, ys - d) == true) 
     { 
      return (x, ys - d); 
     } 

     if (CheckPoint(x, ys + d) == true) 
     { 
      return (x, ys - d); 
     } 
    } 

    for (int y = ys-d+1; y < ys+d; y++) 
    { 
     // Point to check = (xs - d, y) and (xs + d, y) 
     if (CheckPoint(x, ys - d) == true) 
     { 
      return (xs - d, y); 
     } 

     if (CheckPoint(x, ys + d) == true) 
     { 
      return (xs - d, y); 
     } 
    } 
} 

Answer 2

Si usted tiene una lista de objetos

Si tuviera todas las posiciones de todos los objetos en una lista, esto sería mucho más fácil, ya que no tendría que buscar todas las casillas vacías y podría realizar 2D distance calculations para determinar el más cercano a usted. Bucle a través de su lista de objetos y calcular la distancia de la siguiente manera:

Define your two points. Point 1 at (x1, y1) and Point 2 at (x2, y2). 

    xd = x2-x1 
    yd = y2-y1 
    Distance = SquareRoot(xd*xd + yd*yd) 

Luego Sólo tiene que elegir el que tenga la distancia más corta.

Si sólo tiene una matriz 2D

Sin embargo, si el problema que se describe asume una matriz 2D, donde la ubicación de los objetos no se pueden enumerar sin primero la búsqueda de todos ellos, entonces usted va a tener hacer un ciclo en espiral

La búsqueda de 'Spiral Search Method' ofrece algunos enlaces interesantes. Here is some code that does a spiral loop alrededor de una matriz, sin embargo, esto no funciona desde un punto arbitrario y sale en espiral hacia afuera, pero debe darle algunas buenas ideas sobre cómo lograr lo que desea.

Aquí hay un similar question sobre el llenado de valores en orden espiral en una matriz 2D.

De todos modos, aquí es cómo iba a abordar el problema:

punto P Teniendo en cuenta, crear un par de vectores que especifica un área alrededor de P.

Así que si P = 4,4 Luego, su par de vectores habría 3,3|5,5

Loop cada valor de esos límites.

for x = 3 to 5 
    for y = 3 to 5 
     check(x,y) 
    next 
next 

Si se encuentra un valor, salga. Si no, aumente los límites en uno nuevamente. Entonces, en este caso iríamos a 2,2 | 6,6

Al hacer un bucle para verificar los valores, asegurarnos de que no hemos entrado en ningún índice negativo, y también asegurarnos de no haber excedido el tamaño de la matriz .

Además, si amplía los límites n veces, solo necesita realizar un bucle en los valores del límite exterior, no necesita volver a comprobar los valores internos.

¿Qué método es más rápido?

Todo depende de:

• La densidad de la matriz
• técnica Distribución
• Número de objetos

Densidad de la matriz

Si tiene una matriz de 500x500 con 2 ob Jects en él, entonces looping la lista siempre superan a haciendo una espiral

técnica Distribución

Si existen patrones de distribución (es decir, los objetos tienden a agruparse alrededor de la otra), entonces una espiral puede llevar a cabo con mayor rapidez.

Número de objetos

Una espiral probablemente le hará más rápido si hay un millón de objetos, como la técnica de la lista requiere que verificar y calcular todas las distancias.

Debería poder calcular la solución más rápida calculando la probabilidad de que se llene un espacio, en comparación con el hecho de que la solución de la lista debe verificar cada objeto en todo momento.

Sin embargo, con la técnica de lista, es posible que pueda hacer una clasificación inteligente para mejorar el rendimiento. Probablemente valga la pena investigarlo.

Answer 3

Si sus objetos son densos, buscar los puntos cercanos probablemente sea la mejor manera de encontrar el objeto más cercano, saliendo en espiral desde el centro. Si sus objetos son escasos, entonces una estructura de datos quadtree o relacionada (árbol R, etc.) es probablemente mejor. Aquí hay un writeup con ejemplos.

No conozco una buena referencia de algoritmo en línea, pero puedo decir que si va a escribir algo más que una línea ocasional de código, ahorrará unos centavos para comprar CLRS que valdrá la pena el dinero. Hay conferencias basadas en este libro en línea que han sido escrupulosamente anotadas por Peteris Krumins, pero solo cubren parte del libro. Este es uno de los pocos libros que debes tener.

Answer 4

La siguiente solución simple supone que se lo puede permitir el almacenamiento de información adicional por celda de la cuadrícula, y que el costo de tiempo de agregar nuevos objetos a la red se le permite ser relativamente alta.

La idea es que cada celda contiene una referencia a la celda ocupada más cercana, lo que permite O (1) tiempo de consulta. Cada vez que se agrega un objeto a la posición (i, j), realice un escaneo de las celdas circundantes, cubriendo anillos de tamaño creciente. Para cada celda escaneada, evalúe su referencia de celda ocupada más cercana actual y reemplácela si es necesario. El proceso finaliza cuando el último anillo que se escanea no se modifica en absoluto. En el peor de los casos, el proceso escanea todas las celdas de la grilla, pero finalmente mejora cuando la grilla se vuelve lo suficientemente densa.

Esta solución es fácil de implementar, puede tener una sobrecarga de espacio significativa (dependiendo de cómo se organice la cuadrícula en la memoria), pero proporciona un tiempo de consulta óptimo.