¿Cómo funciona el espacio algoritmo de partición para la búsqueda de los vecinos más cercanos funcionan?

Question

Para encontrar el vecino más cercano, espacio Partición es uno de los algoritmos. ¿Cómo funciona?

Supongamos que tengo un conjunto 2D de puntos (coordenadas x e y), y estoy dado un punto (a, b). ¿Cómo sería este algoritmo averiguar el vecino más cercano?

Answer 1

Spacial partición es en realidad una familia de algoritmos estrechamente relacionados que el espacio de partición para que las aplicaciones puedan procesar los puntos o polígonos más fácil.

Creo que hay muchas maneras de resolver su problema. No sé lo complejo que está dispuesto a construir su solución. Una forma sencilla sería probablemente para construir un árbol binario de corte en el espacio 2. Todos los puntos repartidos entre un plano medio. Construir su árbol mediante la subdivisión recursiva hasta que se quede sin puntos.

En busca del vecino más cercano luego será optimizado, ya que cada recorrido del árbol se estrecha el área de búsqueda.

En alguna literatura, esto lo llaman un kd árbol

Answer 2

Estos dos vídeos deben ayudar:

• Al explicar cómo un árbol de KD se construye: http://www.youtube.com/watch?v=T9h2KKJ_Pl8
• Al explicar cómo llevar a cabo más cercana la búsqueda del vecino: http://www.youtube.com/watch?v=2SbVSxWGtpI