Alla ricerca di un algoritmo efficiente trovare rapidamente la linea più vicina (definita dalla distanza perpendicolare) a un punto arbitrario

Question

Ho una grande serie di linee in 2D con un punto di inizio noto e un punto finale, e vorrebbe trovare il più vicino (definito dalla distanza perpendicolare) di tali bordi (o l'estensione di tali bordi oltre i loro punti di partenza e fine) a un punto arbitrario.

Il meglio che ho fatto finora è quello di generare un insieme di punti campione lungo ogni linea e utilizzare un KD-Tree per risolvere il problema del vicino più vicino per i punti - I.e. Trova il punto di campionamento della linea più vicino al punto di query.Ma questo è impreciso e ha bisogno di un gran numero di campioni per lunghe linee.

Ho visto questo: Algoritmo per il bordo più vicinoRilevamento rispetto a un punto (in tutte le direzioni)

Ma si è basato su un metodo di swing e un piccolo numero di linee di lunghezza finita.

Answer 1

Tutte le tue linee definiscono una sottodivisione di planare , dove ciascun poligonale regione è delimitata da un numero finito di segmenti di linea o raggi. Quindi, all'inizio è necessario trovare una regione (probabilmente infinita), contenente un punto di query, e quindi potrai selezionare la sua linea di confine con una distanza minima da questo punto.

Ci sono molti modi per preliminare una suddivisione planari per risolvere il Punto di posizione PROBLEMA con complessità del tempo logaritmico. Alcune strutture dati gerarchiche sono tipicamente concepite, che possono essere attraversate per qualsiasi punto di query, ed è dimostrato che la lunghezza del percorso traverse è limitato da $ o (log (n)) $ , dove $ N $ è il numero di regioni. Come @Pseidonyony menzionato nei commenti, puoi anche usare partizionamento di spazio binario (BSP) per costruire a BSP Tree - È anche una struttura dati gerarchica (albero binario), che ti consentirà di trovare in modo efficiente una regione, contenente un punto di query. Sembra che il tuo problema si adatta bene per questo approccio BSP.

Scusa per dire, puoi ottenere regioni con $ o (n) $ segmenti di confine / raggi del contorno, dove $ n $ è il numero di linee. Per superare questa difficoltà è possibile suddividere ulteriormente ogni regione in Voronoi Diagram , generalizzato per i suoi segmenti di confine e raggi. È facile vedere che il numero totale di regioni così raffinate sarà limitato da $ o (n ^ 2) $ , che ti offre ancora la complessità del tempo logaritmico per la linea più vicina ricerca. Tuttavia, nel caso medio queste regioni con molti segmenti / raggi di confine costituiranno una piccola frazione di tutte le regioni - così in media sarai comunque in grado di selezionare rapidamente il segmento / raggio di confine più vicino semplicemente looping sul limite della regione.

---

.

Se vuoi saperne di più sulle proprietà generali della struttura geometrica con cui stai lavorando - ha senso leggere Questa pagina wiki.

Answer 2

Potrei avere frainteso il tuo obiettivo: presumi che i bordi continuano in entrambe le direzioni anche se sono definiti da 2 punti specifici.Presumo così perché dici che la distanza è definita dalla distanza perpendicolare.Nel qual caso su questo -
1. Per ogni segmento di linea, calcola l'angolo.
2. Disegna una linea immaginaria che attraversa il tuo punto arbitrario a un angolo che è perpendicolare al segmento della linea.
3. Trova il punto di intersezione tra il segmento di linea e la nuova linea immaginaria, trova la distanza tra quel punto e il tuo punto arbitrario.Mantenere la distanza più bassa.
Se le linee non sono infinitamente lunghe, quando si controlla la distanza, controllare il min (distanza dal punto di avvio, dalla distanza dal punto finale).