Per un punto in un poligono irregolare, qual è il modo più efficace per selezionare il bordo più vicino al punto?

Question

Dato un poligono irregolare e un punto all'interno di quel poligono, come faccio a determinare quale lato del poligono è più vicino al punto?

mi sarà probabilmente dovuto eseguire questo calcolo per un ampio insieme di punti all'interno del poligono (ad esempio 50-200 punti).

Answer 1

1. Calcolare punto più vicino sulla linea tangente ad ogni bordo del poligono.
2. Calcolare il punto più vicino su ciascun segmento di linea (bordo del poligono) al punto in questione.
3. Calcolare la distanza dal punto più vicino su ciascun segmento di linea al punto in questione.
4. Trova la distanza minima. Il poligonoone corrispondente con la distanza minima è la risposta.

Ogni fase di questo algoritmo è tempo lineare (O (n)).

Ecco le formule di base per ciascuna delle fasi:

Calcolare punto più vicino sulla linea tangente ad ogni bordo del poligono.

• Let quella finale di un bordo di un poligono essere p1 = {x1, y1}.
• Lascia che l'altro estremo di un bordo di un poligono sia p2 = {x2, y2}.
• Lascia che il punto nel poligono che stai analizzando sia p3 = {x3,y3}.
• Sia la percentuale della distanza tra p1 e p2, quella necessaria per trovare il punto sulla linea formata da p1 e p2, tale che p1+u(p2-p1) = il punto sulla linea più vicino a p3 (il segmento di linea tra questo punto e p3 capita anche di essere perpendicolare alla linea che passa per p1 e p2).
• u = ((x3 - x1)(x2 - x1)+(y3 - y1)(y2 - y1))/((x2 - x1)^2 + (y2 - y1)^2)
• Lasciare che il punto più vicino al p3 sulla linea formata da p1 e p2 essere conosciuto come pu = {xu, yu}
• xu = x1 + u (x2 - x1)
• yu = y1 + u (y2- y1)
• E come abbiamo detto prima pu = {xu, yu}
• Ripetere questi calcoli per ogni bordo poligono (cioè sostituto in nuovi p1s e p2s)

Calcolare il punto più vicino su ogni segmento di linea (bordo del poligono) al punto in questione.

Il punto pu è solo il punto più vicino sul segmento di linea quando 0 <= u <= 1. In caso contrario, il punto finale appropriato del segmento di linea è il punto più vicino al punto in questione.Quindi per ogni pu, p1, p2, and u calcolata nel passo sopra procedere come segue:

• Let pc = {xc, yc} essere indicato come il punto più vicino sul segmento di linea del bordo poligono al punto in questione.
• IF u<0 THEN pc = p1
• ELSE IF u>1 THEN pc = p2
• ELSE pc = pu

Calcolare la distanza dal punto più vicino su ogni segmento di linea fino al punto in questione.

• Distanza tra p3 e pc = `sqrt ((x3 - XC)^2 + (Y3 - YC)^2)
• Ripetere il calcolo per tutti i pc

Trova il distanza minima Il poligonoone corrispondente con la distanza minima è la risposta.

• Iterate attraverso tutte le distanze fino a trovare il più piccolo. Il bordo poligonale corrispondente è la risposta.

Qui è uno schema che aiuta a capire quali sono i punti e la terminologia in questo post rappresentano:

....

Answer 2

Se questo messaggio su SO ispirazione distance from point within a polygon to polygon edge o questa Shortest distance between a point and a line segment

Answer 3

La risposta giusta dipende dal-quadro più ampio struttura del problema: cosa succede quando prendi in considerazione più query? Suppongo che ogni query riguarderà un punto diverso. Ma per quanto riguarda il poligono? Ti aspetti di ricevere più query per lo stesso poligono? O ogni volta che il poligono è diverso?

Se ogni query viene applicata a un poligono diverso e imprevedibile, l'unica soluzione disponibile è essenzialmente l'ispezione totale di tutti i bordi del poligono con test della distanza punto-segmento per ciascuno. Si può essere ottimizzata in vari [euristica] (modi per annullare le prove inutili presto), ma nel peggiore dei casi non c'è modo per aggirare il test completo.

Tuttavia, se ci si aspetta una sorta di prevedibilità e stabilità sul lato poligonale del problema (un numero sufficiente di query puntuali allo stesso poligono o a un set fisso di poligoni), la situazione cambia drasticamente. L'approccio migliore in questo caso sarebbe quello di pre-costruire il diagramma Voronoi edge-based all'interno del poligono (s). Quindi è possibile risolvere il problema di punto-posizione (per la quale non sono noti algoritmi efficienti) per determinare quale regione Voronoi punto interrogazione cade. Che immediatamente vi dico quale bordo è il più vicino.

Quest'ultimo è incomparabilmente più efficiente quando si ha bisogno di gestire molte punto-query per lo stesso poligono (s), ma richiede piuttosto uno sforzo per implementare. Quindi, tutto dipende dal tipo di soluzione di cui hai bisogno.

P.S. Vedo che indicare nella sua domanda che la vostra intenzione di correre per un grande insieme di punti per un singolo poligono. Ciò rende immediatamente la soluzione basata sul diagramma di Voronoi la strada da percorrere.Ulteriori sfumature dell'algoritmo potrebbero dipendere dal fatto che quell'ampio insieme di punti sia del tutto noto in anticipo o arrivi punto per punto in modo imprevedibile.