Selezione di un punto all'interno di un poligono non convesso

Question

Selezione di un punto all'interno di un poligono non convesso

#1 da (1 voti)
#2 da (1 voti)
#3 da (1 voti)
#4 da (0 voti)
#5 da (0 voti)

2

Ci sono molti algoritmi che ti diranno se un dato punto si trova o meno all'interno di un poligono.

Sto cercando di scrivere un algoritmo che, dato un poligono non convesso, restituirà un punto che si trova all'interno del poligono.

Non ho bisogno che il punto si trovi in una specifica posizione all'interno del poligono, ma preferisco ricevere un punto che non è molto vicino a un bordo, ma non è un rompicapo. È lì solo per contrassegnare il grafico rettilineo planare (PSLG) di un poligono come una forma interna da utilizzare con il triangolo libreria per alcune complicate triangolazioni di Delaunay vincolate.

Il mio pensiero iniziale è:

Calcola il riquadro di delimitazione
Trasmetti un raggio da un angolo nella direzione dell'angolo opposto o dal centro del bordo del riquadro di delimitazione al centro del bordo opposto.
Quindi, verrà posizionato esattamente un punto tra la prima e la seconda intersezione essere all'interno del poligono.

C'è un approccio migliore?

geometry

posta Rob Perkins 03.02.2014 - 19:23

fonte

5 risposte

Leggi altre domande sui tag geometry

Ottenere lista di oggetti della stessa classe Accesso a un sistema distribuito

score 1 · Answer 1

Il tuo approccio iniziale sembra fare ciò che ti serve, ma a seconda di quanto tempo potresti spendere per trovare un punto "buono" (non troppo vicino a un bordo), potresti raccogliere diversi campioni in vari modi:

Lascia che il raggio intersecante colpisca l'altro lato del riquadro di delimitazione e cerchi coppie di intersezioni (1 & 2, 3 e 4, ecc.) più distanti tra loro.
Trasmetti 2 o 4 raggi: da un angolo all'altro, dal lato al lato opposto.

score 1 · Answer 2

Se crei un cerchio di delimitazione invece di un riquadro di delimitazione, puoi selezionare un punto casuale sul cerchio e proiettare raggi ad ogni X ° sul cerchio (cioè, come un accordo, creando un ventaglio di raggi) a trova i punti Quindi, utilizzando le preferenze che hai per la selezione dei punti, puoi selezionare il miglior punto fuori dai punti trovati.

Tuttavia, ti consiglio di provare prima quello che ti è venuto in mente, perché potrebbe essere sufficiente per le tue esigenze.

score 1 · Answer 3

1

Dato un poligono (P1, P2, ... Pn), costruisci triangoli dai punti adiacenti a ciascun vertice (P1 P2 P3), (P2 P3 P4), ... (Pn P1 P2), e controlla se il centro del triangolo si trova all'interno del poligono.

risposta data 03.02.2014 - 20:38

fonte

score 0 · Answer 4

Il seguente algoritmo funzionerà bene:

p = randpoint();
while(!IsInsidePolygon(p, poly)) {
  p = randpoint();
}

Il grosso problema è scegliere randpoint () in modo che l'intera area del poligono sia coperta, ma l'area non può essere troppo grande o il ciclo while richiede troppo tempo.

score 0 · Answer 5

Trovare il punto in un triangolo che è più lontano dal suo confine è solo trovare l'incentre. Se triangoli il poligono (non il tempo lineare, ma non molto lontano), puoi quindi cercare un triangolo "bello" (ad esempio quello con il lato più corto più corto) e prendere il suo incentre.