Punto más cercano a un punto dado

Tengo un conjunto K de píxeles seleccionados al azar en una imagen 2D. Para cada otro píxel en la imagen necesito descubrir 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?

Aclamaciones.

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

Si solo quieres encontrar el más cercano (y no su 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 ajuste esta lista de píxeles, tendrá que realizar una prueba en contra de todos ellos.

Si tiene cierta flexibilidad, existen muchas formas de reducir la carga de trabajo. Haz un Quadtree o mantén una lista ordenada de los píxeles (ordenada por x y ordenada por y) para restringir tu búsqueda más rápidamente.

Tendré que estar de acuerdo con jk y Ewan en hacer un diagtwig de Voronoi . 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 denomina Ubicación de puntos y se puede resolver construyendo un Mapa trapezoidal .

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

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

Mi fuente (que no sean 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 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).

La construcción de los diagtwigs de Voronoi es una twig de la Geometría Computacional . La construcción de Delaunay Triangulations implica consideraciones similares. Es posible que pueda adaptar uno de los siguientes algoritmos de Delaunay para satisfacer sus necesidades.

  • Algoritmos de volteo
  • Incremental
  • Divide y conquistaras
  • Sweepline

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

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

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

Buscar en Google ésos debería ayudar.

lo que estás tratando de hacer es construir un diagtwig voronoi, esto se puede hacer en O (n log n) usando un barrido plano

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

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

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

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.

Programé algo como esto para una emulación de terminal gráfica. Lo que terminé haciendo fue la progtwigció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.