Algoritmo para encontrar el segmento más cercano a un punto entre muchos segmentos (Geocodificación inversa)

Tengo un conjunto de segmentos definidos por dos puntos. Dado un punto, ¿cómo puedo descubrir el segmento más cercano a tal punto?Algoritmo para encontrar el segmento más cercano a un punto entre muchos segmentos (Geocodificación inversa)

Ya he escrito un algoritmo que calcula la distancia entre un punto y un segmento. De todos modos, calcular dicha distancia para cada segmento y luego elegir el segmento con la distancia más baja no es realmente eficiente :(

Dado que los segmentos representan calles esto es en realidad un problema de GeoCoding Inverso, así que espero que haya soluciones bien conocidas para este problema ...

muchas gracias!

Fuente

2010-08-06 Giorgio

¿El conjunto de segmentos está ordenado de alguna forma? –

¿Los segmentos se superponen? ¿Te refieres a segmentos en una línea, o p. segmentos de spherig? Si es este último, ¿cómo definen tus dos puntos el segmento? (diferentes definiciones son posibles) ---- De todos modos, ordenar los segmentos por algunos criterios generalmente ayuda. – peterchen

@Giorgio: ¿Encontraste el algoritmo? ¿Podría compartir o darme un enlace a ese algoritmo? ¡Gracias de antemano! –

utilizar una cuadrícula, kd-árbol, árbol cuádruple o método de particionado similar espacio binario. Luego, a partir de la célula árbol que su punto radica en, comenzar a explorar los segmentos hasta que el la distancia desde el punto hasta la celda que contiene el segmento es mayor que la distancia más pequeña encontrada hasta ahora.

http://en.wikipedia.org/wiki/Binary_space_partitioning

(Esto es, por supuesto, asumiendo que los segmentos/calles cambian muy pocas veces, pero hay una gran cantidad de puntos para localizar).

Fuente

2010-08-06 12:57:03

No hay forma de saber si un segmento dado se cruza con una partición determinada sin realizar un cálculo (al menos) igualmente caro (en comparación con la distancia del segmento de punto), por lo que cualquier enfoque de partición sería potencialmente más rápido si el conjunto de segmentos cumple con ciertas condiciones (como la máxima longitud de segmento << dimensiones de partición, por ejemplo). – MusiGenesis

@MusiGenesis: la clave es hacer que cada segmento sea parte de todas las hojas que cruza cuando se construye el árbol. De esta forma, si una de las hojas está lo suficientemente cerca de los puntos, el segmento será probado, y si ninguna de las hojas está lo suficientemente cerca, entonces el segmento nunca se probará. Como el árbol solo se construye una vez, el costo de hacerlo se divide en todas las solicitudes posteriores. –

de acuerdo. Asumía que hay un conjunto diferente de segmentos cada vez. – MusiGenesis

Algoritmo para encontrar el segmento más cercano a un punto entre muchos segmentos (Geocodificación inversa)

Respuesta

Cuestiones relacionadas