videos ubicados puntos plano los julioprofe entre ejemplos ejemplo distancia algorithm 2d points

algorithm - ubicados - Punto más cercano a un punto dado



ejemplos distancia entre 2 puntos (8)

Coloque los puntos en un árbol KD, después de esto es muy rápido encontrar al vecino más cercano. Vea this artículo en Wikipedia para más detalles.

Tengo un conjunto K de píxeles seleccionados al azar en una imagen 2D. Para cada otro píxel en la imagen, necesito averiguar qué píxel en el conjunto K está más cercano a él (usando la medida de distancia estándar sqrt (dx ^ 2 + dy ^ 2)). Soy consciente de que puede haber más de una solución para cada píxel. Obviamente, se puede hacer mediante fuerza bruta contra cada píxel del conjunto, pero prefiero evitar esto ya que no es eficiente. ¿Alguna otra buena sugerencia?

Aclamaciones.

Dependiendo de cuán densamente este gráfico esté lleno de píxeles, es posible que sea mejor buscar solo desde el píxel de origen.

Programé algo como esto para una emulación de terminal gráfica. Lo que terminé haciendo fue programar un patrón de búsqueda con la forma de una espiral cuadrada que surgió desde el punto central, y la dejé crecer hasta que golpeó algo. Eso fue lo suficientemente rápido para el propósito, incluso en una vieja CPU.

Esto se llama la búsqueda vecina más cercana. Donald Knuth lo llamó el problema de la oficina de correos.

Existen varias soluciones: búsqueda lineal, hash sensible a la localidad, archivos de aproximación vectorial y partición de espacios.

Buscar en Google debería ayudar.

No olvides que no necesitas molestarte con la raíz cuadrada.

Si solo quieres encontrar el más cercano (y no la distancia real) solo usa dx^2 + dy^2 , que te dará la distancia al cuadrado de cada elemento, que es igual de útil.

Si no tiene una estructura de datos que complete esta lista de píxeles, deberá probarlos todos.

Si tiene cierta flexibilidad, hay un montón de buenas maneras de reducir la carga de trabajo. Cree un Quadtree o mantenga una lista ordenada de los píxeles (ordenados por x y ordenados por y) para limitar su búsqueda más rápidamente.

Otra sugerencia: la distancia siempre es mayor o igual a cada diferencia de coordenadas, y siempre menor o igual a su suma, es decir

d >= dx, d >= dy, d <= dx + dy.

Esto podría ayudarte a hacer la clasificación de manera más eficiente.

Tendré que estar de acuerdo con jk y Ewan para hacer un Diagrama Voronoi . Esto dividirá el espacio en polígonos. Cada punto en K tendrá un polígono que describe todos los puntos que están más cerca de él. Ahora, cuando obtiene una consulta de un punto, necesita encontrar en qué polígono se encuentra. Este problema se llama ubicación de punto y se puede resolver mediante la construcción de un mapa trapezoidal .

jk ya está vinculado a la creación del Diagrama Voronoi usando el algoritmo de Fortune que toma O (n log n) pasos computacionales y cuesta espacio O (n). Este sitio web le muestra cómo hacer un mapa trapezoidal y cómo consultarlo. También puede encontrar algunos límites allí:
Tiempo de creación esperado: O (n log n)
Espacio esperado complejidad: O (n)

Pero lo más importante, el tiempo de consulta esperado: O (log n). Esto es (teóricamente) mejor que O (√n) del árbol kD.

Mi fuente (aparte de los enlaces anteriores) es: Geometría computacional: algoritmos y aplicaciones , capítulos seis y siete.

Allí encontrará información detallada sobre las dos estructuras de datos (incluidas las pruebas detalladas). La versión de Google books solo tiene una parte de lo que necesita, pero los otros enlaces deben ser suficientes para su propósito. Simplemente compre el libro si está interesado en ese tipo de cosas (es un buen libro).