Distanza da un punto a un poligono

Question

Sto provando a determinare la distanza da un punto a un poligono nello spazio 2D. Il punto può essere all'interno o all'esterno del poligono; Il poligono può essere convesso o concavo.

Se il punto si trova all'interno del poligono o all'esterno del poligono con una distanza inferiore a una costante definita dall'utente d, la procedura deve restituire True; False altrimenti.

Ho trovato una domanda simile: Distance from a point to a polyhedron or to a polygon. Tuttavia, lo spazio è 2D nel mio caso e il poligono può essere concavo, quindi è in qualche modo diverso da quello.

Suppongo che ci dovrebbe essere un metodo più semplice che compensare il poligono di d e determinarlo all'interno o all'esterno del poligono.

Qualsiasi algoritmo, codice o suggerimenti per me per google in giro sarebbe apprezzato.

Answer 1

La soluzione migliore è iterare su tutte le linee e trovare la distanza minima da un punto a un segmento di linea.

per trovare la distanza da un punto ad un segmento di linea, per la prima volta la distanza esatta da un punto ad una linea con la scelta di punti arbitrari P1 e P2 sulla linea (potrebbe essere saggio di utilizzare gli endpoint). Quindi prendi il vettore da P1 al punto P0 e trova (P2-P1) . (P0 - P1) dove . è il prodotto punto. Dividere questo valore per ||P0-P1||^2 e ottenere un valore r.

Ora, se hai scelto P1 e P2 come i punti, si può semplicemente controllare se r è compreso tra 0 e 1. Se r è maggiore di 1, quindi P2 è il punto più vicino, quindi la distanza è ||P0-P2||. Se r è minore di 0, quindi P1 è il punto più vicino, quindi la distanza è ||P0-P1||.

Se 0<r<1, quindi la distanza è sqrt(||P0-P1||^2 - r * ||P2-P1||^2)

Lo pseudocodice è la seguente:

for p1, p2 in vertices: 

    var r = dotProduct(vector(p2 - p1), vector(x - p1)) 
    //x is the point you're looking for 

    r /= magnitude(vector(x - p1)) 

    if r < 0: 
    var dist = magnitude(vector(x - p1)) 
    else if r > 1: 
    dist = magnitude(vector(p2 - x)) 
    else: 
    dist = sqrt(magnitude(vector(x - p1))^2 - r * magnitude(vector(p2-p1))^2) 

    minDist = min(dist,minDist) 

Answer 2

Se si dispone di un punto di lavoro per la funzione di distanza del segmento di linea, è possibile utilizzarlo per calcolare la distanza dal punto a ciascuno dei bordi del poligono. Ovviamente, devi prima controllare se il punto è all'interno del poligono.

Answer 3

Avete bisogno veloce o semplice?
Deve essere sempre assolutamente corretto nei casi limite o sarà abbastanza buono per la maggior parte del tempo essere OK?

soluzione Tipici sono per trovare la distanza di ciascun vertice e trovare la coppia con i valori minimi (si noti che per un punto esterno di un poligono convesso questi potrebbero non essere adiacenti) e quindi controllare scegliere linea intersezioni per ogni segmento.

Per forme complesse di grandi dimensioni è anche possibile memorizzare circa caselle di delimitazione del poligono (rettangolari o esagoni) e trovare il lato più vicino prima di controllare più dettagli.

Potrebbe anche essere necessario il codice per gestire il caso speciale esattamente di una linea.

Answer 4

ti posso aiutare con questo puntatori:

• La distanza può essere calcolata utilizzando Wikipedia entry, anche con uno snipped testata di codice.
• L'interno/bordo esterno può essere risolto con questa Stack Post and links

e alcune osservazioni:

• si dovrebbe verificare solo i punti più vicini, come Martin Beckett's out point risposta, dal momento che un altro segmento può "essere proiettato" molto vicino, ma in realtà non è vicino al bisogno.

Answer 5

potete fare il vostro programma di eseguire un po 'più veloce utilizzando la trigonometria e la condanna del peccato