Algoritmo per trovare il segmento più vicino a un punto tra molti segmenti (Geocoding inverso)

Ho un insieme di segmenti definiti da due punti. Dato un punto, come posso scoprire il segmento più vicino a questo punto?Algoritmo per trovare il segmento più vicino a un punto tra molti segmenti (Geocoding inverso)

Ho già scritto un algoritmo che calcola la distanza tra un punto e un segmento. Calcolare tale distanza per ogni segmento e quindi scegliere il segmento con la distanza più bassa non è davvero efficiente :(

Poiché i segmenti rappresentano le strade questo è in realtà un problema di GeoCoding inverso quindi spero ci siano soluzioni note a questo problema ...

Thanks a lot!

fonte

2010-08-06 Giorgio

L'insieme di segmenti è ordinato in alcun modo? –

I segmenti si sovrappongono? Intendi segmenti su una linea, ad es. segmenti di spherig? Se quest'ultimo, come i tuoi due punti definiscono il segmento? (sono possibili diverse definizioni) ---- In ogni caso, l'ordinamento dei segmenti secondo alcuni criteri di solito aiuta. – peterchen

@Giorgio: hai trovato l'algoritmo? Potresti per favore condividere o darmi un link a quell'algoritmo. Grazie in anticipo! –

Utilizzare una griglia, kd-tree, quadtree o simile metodo di partizione binaria dello spazio. Poi, a partire dalla cellula albero che il punto si trova a, iniziare ad esplorare i segmenti fino al la distanza dal punto della cella che contiene il segmento è maggiore della distanza minima trovata finora.

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

(Questo è, naturalmente, assumendo che i segmenti/strade cambiano solo molto raramente, ma avete un sacco di punti da individuare).

fonte

2010-08-06 12:57:03

Non c'è modo di sapere se un determinato segmento si interseca con una determinata partizione senza eseguire un calcolo (almeno) altrettanto costoso (rispetto alla distanza del punto), quindi qualsiasi approccio di partizionamento sarebbe potenzialmente più veloce se l'insieme di segmenti soddisfa determinate condizioni (come la lunghezza massima del segmento << dimensioni della partizione, ad esempio). – MusiGenesis

@MusiGenesis: la chiave è rendere ogni parte del segmento di tutte le foglie che interseca quando viene costruito l'albero. In questo modo, se una delle foglie è abbastanza vicina ai punti, il segmento verrà testato e se nessuna delle foglie è abbastanza vicina, il segmento non verrà mai testato. Poiché l'albero viene costruito una sola volta, il costo di tale operazione è ripartito su tutte le richieste che si verificano successivamente. –

concordato. Supponevo che ci fosse un diverso insieme di segmenti ogni volta. – MusiGenesis

Algoritmo per trovare il segmento più vicino a un punto tra molti segmenti (Geocoding inverso)

risposta

Problemi correlati