Determinare se esiste una coordinata all'interno di un poligono

Question

Sto lavorando su un'applicazione software di monitoraggio e geofence open source e ho un po' di difficoltà nel capire i calcoli per il geofencing.

Devo determinare se esiste o meno una coordinata all'interno di un poligono.Tuttavia, la parte difficile è che il poligono non ha un numero prestabilito di lati.Devo essere in grado di calcolare per cinquanta lati o per cinque lati.

La mia ricerca dice che il modo più semplice è prendere il mio punto (che chiamerò x) e un punto esterno al poligono (chiamiarlo y) e determinare se la linea ((xx, xy), (yx, yy)) si interseca con i confini del poligono.Se si interseca un numero dispari di volte, il punto x deve trovarsi all'interno del poligono.

Sapendo questo, tuttavia, non riesco a capire come esprimerlo in un algoritmo..Ovviamente dovrò scorrere le varie linee che compongono il poligono ma il controllo che faccio mi sfugge.Qualcuno può essere d'aiuto?Tieni presente che non sto chiedendo necessariamente la soluzione.Tutto ciò che mi aiuta a capire la risposta è di enorme aiuto.

Molto apprezzato.

Answer 1

Vedere Qui

Fondamentalmente esiste un approccio (penso sia il teorema della curva di Jordan) che conta il numero di volte in cui un raggio interseca i segmenti di linea che compongono il poligono.Se il risultato è pari allora il punto è all'esterno del poligono altrimenti il ​​punto si trova all'interno del poligono.

HTH

MODIFICAREC'è un'altra domanda SO relativa a questa domanda che può essere trovata Qui

Answer 2

Una chiave qui è quello di rendersi conto che si è liberi di scegliere qualsiasi punto Y che ti piace. Una scelta davvero bella è il punto (xx, -infinito). In altre parole, il punto direttamente verso il basso dal punto in questione e infinitamente lontano. Ora la domanda diventa: quanti dei bordi del poligono lungo il tuo X-coordinata al di sotto del punto in questione. Quindi solo i segmenti di linea che si situano la coordinata x necessità di essere presa in considerazione.

Se il punto è P = (x, y), e punti finali segmento sono P1 = (x1, y1) e P2 = (x2, y2) la coordinata y del segmento dove attraversa x è data da sy = (x-x1) * (y2-Y1) / (x2-x1) + y1

Controlla se sy

Ci sono problemi sottili con questo quando uno dei verticies del poligono è esattamente la stessa posizione y come il punto in questione. Dovrete stare attenti a quel caso.

Answer 3

Justin,

Potrebbe anche essere necessario per meglio definire "al di fuori del poligono" per la costruzione di un segmento.

Prendere il min & max di tutte le x e y coordinate e costruire un rettangolo (Xmin, Ymin), (Xmax, Ymin), (Xmax, Ymax), (Xmin, Ymax). Qualsiasi punto all'esterno del rettangolo sarebbe sicuramente fuori del poligono - poi proseguire come altri hanno mostrato sopra. Ogni segmento poligono e la retta costruita è definita dall'equazione y = ax + b e, per ogni segmento, una gamma xlo e XHI. La vostra linea costruita o attraversa un segmento nel campo o meno. Cioè, la soluzione delle due equazioni simultanee nell'intervallo segmento esiste o meno. Basta contare il numero di soluzioni che esistono per ottenere il numero di intersezioni.

Answer 4

darò per scontato che sei in un piano (2D).

• calcolare le pendenze delle ciascun lato (in qualche sistema di coordinate) e la pendenza della linea dal punto X al punto Y (XY).
• Per tutti i lati in cui la pendenza non è uguale alla pendenza XY, calcolare il punto di intersezione.
• Per ogni punto, determinare se il punto di intersezione è il segmento di linea XY e il segmento di linea che definisce il lato. Se lo è, è attraversato quel lato. (Vedi le coordinate del punto di intersezione e vedere se entrambe le componenti X e Y sono inclusi nella gamma di valori per ciascun segmento di linea.)
• Contare il numero di attraversamenti, e avete la vostra risposta.

Answer 5

Calcola il avvolgimento numero del poligono e il punto.

Answer 6

Prova questo,

public static bool PointinPolygon( Point[] points, Point p )
    {
        bool result = false;

        for( int i = 0; i < points.Length - 1; i++ )
        {
            if( ( ( ( points[ i + 1 ].Y <= p.Y ) && ( p.Y < points[ i ].Y ) ) || ( ( points[ i ].Y <= p.Y ) && ( p.Y < points[ i + 1 ].Y ) ) ) && ( p.X < ( points[ i ].X - points[ i + 1 ].X ) * ( p.Y - points[ i + 1 ].Y ) / ( points[ i ].Y - points[ i + 1 ].Y ) + points[ i + 1 ].X ) )
            {
                result = !result;
            }
        }
        return result;
    }