algorithm - array - Algoritmo para encontrar el objeto más cercano en una grilla 2D

processing array of lines

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 limpio para que cuando un usuario especifique 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 algoritmos?

Answer 1

La siguiente solución simple asume que puede permitirse almacenar información adicional por celda de la grilla, y que el costo de tiempo de agregar nuevos objetos a la grilla se permite relativamente alto.

La idea es que cada celda contenga 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 simple de implementar, puede tener una sobrecarga de espacio significativa (dependiendo de cómo se organice su grilla en la memoria), pero proporciona un tiempo de consulta óptimo.

Answer 2

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

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

Answer 3

Si tienes 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 necesitaría buscar todos los cuadrados vacíos y podría realizar cálculos de distancia 2D para determinar el más cercano a usted. Pasa por tu lista de objetos y calcula 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)

Entonces simplemente elige el que tenga la distancia más corta.

Si solo tienes una matriz 2D

Sin embargo, si el problema tal como se describe supone una matriz 2D en la que las ubicaciones de los objetos no se pueden enumerar sin buscar primero todas ellas, entonces tendrá que hacer un ciclo en espiral.

La búsqueda del '' Método de búsqueda en espiral '' ofrece algunos enlaces interesantes. Aquí hay un código que realiza un ciclo en espiral alrededor de una matriz, sin embargo, esto no funciona desde un punto arbitrario y sale en espiral hacia afuera, sino que debe darle algunas buenas ideas sobre cómo lograr lo que desea.

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

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

Dado el punto P , crea un par vectorial que especifique un área alrededor de P

Entonces, si P = 4,4 Entonces su par vectorial sería 3,3|5,5

Bucle cada valor en 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

Cuando buclee para verificar los valores, asegúrese de que no hayamos ingresado en ningún índice negativo, y también de que no hayamos excedido el tamaño de la matriz.

Además, si amplía los límites n veces, solo necesita repetir los valores límite externos, no necesita volver a verificar los valores internos.

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

Todo depende de:

• La densidad de tu matriz
• Técnica de distribución
• Número de objetos

Densidad de matriz

Si tiene una matriz de 500x500 con 2 objetos, el bucle de la lista siempre superará al hacer una espiral

Técnica de distribución

Si hay patrones de distribución (es decir, los objetos tienden a agruparse uno alrededor del otro), entonces una espiral puede funcionar más rápido.

Número de objetos

Una espiral probablemente funcionará más rápido si hay un millón de objetos, ya que la técnica de lista requiere que verifique y calcule cada distancia.

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 4

Udate

Con nueva información:

Suponiendo que una coordenada en diagonal está a 2

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)
    }
}

Versión antigua

Suponiendo que en su cuadrícula 2D la distancia entre (0, 0) y (1, 0) es la misma 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);
        }
    }
}