Punto más cercano a un punto dado

Question

Tengo un conjunto K de píxeles seleccionados al azar en una imagen 2D. Para cada otro píxel de la imagen, necesito saber qué píxel en el conjunto K está más cerca de é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 por la fuerza bruta contra cada píxel en el conjunto, pero prefiero evitar esto ya que no es eficiente. ¿Alguna otra buena sugerencia?

Saludos.

Answer 1

No olvide que no necesita molestarse con la raíz cuadrada.

Si solo quiere encontrar la más cercana (y no su distancia real) simplemente use dx^2 + dy^2, que le dará la distancia al cuadrado de cada elemento, que es igual de útil.

Si no tiene una estructura de datos que envuelva esta lista de píxeles, tendrá que probar contra todos ellos.

Si tiene cierta flexibilidad, hay muchas maneras de reducir la carga de trabajo. Haga un Quadtree, o mantenga la lista ordenada de los píxeles (ordenados por x y ordenados por y) para restringir su búsqueda más rápidamente.

Answer 2

Esto se denomina búsqueda de vecinos más cercanos. Donald Knuth lo llamó el problema de la oficina de correos.

Existen varias soluciones: búsqueda lineal, hashing sensible a la localidad, archivos de aproximación de vectores y partición del espacio.

Google debe ser de ayuda.

Answer 3

Dependiendo de qué tan densamente este gráfico esté lleno de píxeles, es mejor que solo busque hacia afuera desde su píxel de origen.

He programado algo como esto para una emulación de terminal gráfica. Lo que terminé haciendo fue la programación de un patrón de búsqueda en forma de espiral de lados cuadrados que crecía desde el punto central, y lo dejé crecer hasta que golpeó algo. Eso fue lo suficientemente rápido para este propósito, incluso en una CPU vieja.

Answer 4

Otra pista: La distancia es siempre 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 ayudarle a hacer la clasificación de manera más eficiente.

Answer 5

lo que usted está tratando de hacer es construir un voronoi diagram esto se puede hacer en O (n log n) usando un plane sweep

Answer 6

La construcción de Voronoi Diagrams es una rama de Computational Geometry. La construcción de Delaunay Triangulations implica consideraciones similares. Es posible que pueda adaptar uno de los siguientes Delaunay algorithms a sus necesidades.

• algoritmos de Flip
• incremental
• divide y vencerás
• Sweepline

Answer 7

poner los puntos en un árbol KD, después de esto que es muy rápido para encontrar el vecino más cercano.Ver el artículo this en wikipedia para más detalles.

Answer 8

Tendré que estar de acuerdo con jk y Ewan en hacer un Voronoi Diagram. Esto dividirá el espacio en polígonos. Cada punto en K tendrá un polígono que describa 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 Point Location y se puede resolver construyendo un Trapezoidal Map.

jk ya vinculado a la creación del Voronoi Diagram usando Fortune's algorithm que toma O (n log n) pasos computacionales y cuesta O (n) espacio. This website le muestra cómo hacer un mapa trapezoidal y cómo consultarlo. También puede encontrar algunos límites allí:
hora de creación esperado: O (n log n)
esperado complejidad espacial: O (n)

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

Mi fuente (que no sean los enlaces de arriba) es: Computational Geometry: algorithms and applications, capítulos seis y siete.

Allí encontrará información detallada acerca de las dos estructuras de datos (incluidas las pruebas detalladas). La versión de libros de Google solo tiene una parte de lo que necesita, pero los otros enlaces deberían ser suficientes para su propósito. Solo compre el libro si le interesa ese tipo de cosas (es un buen libro).