problema di geometria

non mi viene in mente un posto migliore dove porre il quesito, quindi lo pongo qui (in fin dei conti, una volta risolto il problema teorico, dovrei ricavarne una routine in vb).

dato un poligono chiuso di cui conosciamo le coordinate dei vertici e il loro ordine (e quindi tutto il conoscibile) e dato un punto (sempre di coordinate note), come determinare se il punto si trova all'interno del poligono oppure no?

dopo averci pensato un po', sono giunto alla seguenti conclusioni:
supponiamo per un attimo che il poligono sia convesso; in tal caso, il punto è interno se la somma degli angoli centrati su esso e che puntano su due vertici consecutivi è pari a 360°, è esterno se la somma è minore di 360° (la dimostrazione è ovvia, un punto esterno "vede" il poligono sotto un angolo che è minore di 180°, quindi la somma di questi angoli, pari al doppio, è sicuramente minore di 360°).

e se il poligono invece non è convesso?
mi vien da pensare che la cosa sia analoga, purchè si prendano gli angoli col segno (ovvero, fissato un verso di percorrenza del poligono, per esempio antiorario, gli angoli che "vanno" in quel verso sono positivi, quelli in verso contrario negativi).
se il punto è interno, sicuramente la somma fa ancora 360°; se esso è esterno, la somma questa volta fa 0° (e lo stesso nel caso precedente, con queste "nuove regole").
ammettendo che sia corretto (vi sembra corretto?), come costruire una funzione che mi restituisca il "segno" dell'angolo?

(PS: ricavare il valore dell'angolo è facile, basta calcolare il coefficiente angolare delle due rette e ricordarsi che esso è pari all'arcotangente dell'angolo sotteso)

Oppure vi viene in mente qualche altro metodo più semplice?

mah,
se non ho capito male, si tratta proprio di un solo passaggio e posso anche tirare a caso quanto riguarda la semiretta.
le soluzioni sono
a) semiretta non incontra lati poligono = punto esterno
b) semiretta incontra lati poligono (n° pari di intersezioni) = punto ancora esterno
c) semiretta incontra lati poligono (n° dispari di intersezioni) = punto interno

quindi,
determino se il punto sta sulla frontiera, così mi calcolo anche i coefficienti dei lati del poligono,
se no allora invento una semiretta a caso, posso anche prendere sempre la stessa e sicuramente sto dentro ad uno dei tre casi sopracitati.

mah,
se non ho capito male, si tratta proprio di un solo passaggio e posso anche tirare a caso quanto riguarda la semiretta.
le soluzioni sono
a) semiretta non incontra lati poligono = punto esterno
b) semiretta incontra lati poligono (n° pari di intersezioni) = punto ancora esterno
c) semiretta incontra lati poligono (n° dispari di intersezioni) = punto interno

quindi,
determino se il punto sta sulla frontiera, così mi calcolo anche i coefficienti dei lati del poligono,
se no allora invento una semiretta a caso, posso anche prendere sempre la stessa e sicuramente sto dentro ad uno dei tre casi sopracitati.

non conviene, ci ho pensato su ieri, grazie a un "provvidenziale" (grrr) ritardo ferroviario.

supponiamo di aver risolto in qualche modo la questione del segno dell'angolo, e confrontiamo il metodo A (angoli) con il metodo I (intersezioni); per applicare il metodo I devo prima calcolare tutti i coefficienti angolari dei lati del poligono: trascuriamo questa fase, visto che la devo fare solo una volta, per tutti i punti di cui devo verificare la posizione.
fatto questo, devo scegliere la semiretta: trascuriamo per ora anche il tempo necessario a svolgere questa fase.

scelta la semiretta, devo verificare la presenza di intersezioni con i lati: come si svolge questa operazione? A me sembra che l'unica maniera sia calcolare l'intersezione con la retta che contiene il segmento, e verificare che il punto di intersezione stia tra i due vertici del lato: tale operazione è di complessità computazionale superiore a quella di calcolarmi l'angolo con il metodo A, e quindi possiamo supporre che sia equivalente a quella di calcolarmi pure il segno (supposizione da verificare, ovviamente).

A questo punto i due metodi sarebbero equivalenti come tempo, ma c'è un ma: come effettuo la scelta della semiretta?
è ovvio che posso fare un primo tentativo "semplice", orizzontale o verticale, e poi magari se non va bene affinarlo con il metodo da me proposto (pigliare un vertice, e poi spostarmi di un poco).
Però, qualsiasi sia la scelta che faccio, essa impone una verifica che sia stata corretta, che si traduce in verificare che l'intersezione che calcolo sia diversa dagli estremi del lato, e quindi aumenta il numero di operazioni da compiere.

Mi si impone anche la scelta di una strategia di "recupero": ovvero se la semiretta non è andata bene, come eseguo un nuovo tentativo?

Ma soprattutto, all'aumentare del numero dei lati del poligono, diventa sempre più probabile "incocciare" in un vertice (notate che quando la matematica viene tradotta in programmazione, le intersezioni "esatte" non esistono, e si deve quindi introdurre delle tolleranze), il che mi rende (con poligoni di molti lati) conveniente impostare una strategia di eliminazione, fin da prima del primo tentativo, di tutte le angolazioni da evitare: tale strategia consiste nel calcolare gli angoli con tutti i vertici, e dunque ha una complessità computazione equivalente a quella dell'INTERO metodo A!

Tutto questo è valido se supponiamo (come nel mio caso) di voler classificare come interni i punti sulla frontiera (il metodo A infatti non distingue, la somma degli angoli per un punto sulla frontiera fa ancora 360°), viceversa il metodo I potrebbe recuperare terreno (ma non molto: per escludere il caso sarebbe sufficiente controllare i singoli angoli, e verificare che non ce ne sia uno da 180°).

Quindi resto dell'idea che il metodo A sarebbe più efficiente, oltre che più "pulito" come stesura del codice.
Resta aperta però la questione teorica della determinazione del segno...

La semiretta con origine in P la possiamo fissare fissando il passaggio di essa per un secondo punto che chiamiamo Q.

[b]Vedremo poi quale strategia adottare per fissare convenietemente Q [/b], intanto note le coordinate di P(x,y), di Q(Xo,Yo) e degli estremi i e j del segmento che costituisce il generico lato del poligono, e' facile determinare le coordinate di intersezione tra la retta PQ e la retta IJ (lo si potrebbe anche fare per via matriciale dato che si tratta di risolvere un sistema a due equazioni e due incognite) e noto il punto di intersezione che chiamo Z e' facile verificare con unica condizione logica se esso si trova dal lato Q nella semiretta PQ e internamente agli estremi IJ.

La condizione che la semiretta non deve passare per nessuno dei vertici nasce dal fatto che esiste una possibilità, con punto P esterno, di indeterminazione della posizione di P rispetto al poligono. Nel caso generale, pertanto, il passaggio della semiretta per uno dei vertici del poligono costituisce una normale intersezione alla stessa stregua delle altre.

(IMG:http://img216.imageshack.us/img216/2734/aa4hu.th.jpg)

Se riuscissimo a filtrare a monte, mediante opportuna scelta di Q, la circostanza evidenziata nella figura sopra, quella segnata in rosso, che ci porta alla indeterminazione, allora potremmo trattare il passaggio per un vertice alla stessa stregua di una normale intersezione.

Intanto che ci ragiono noto :
- nel caso in cui il punto fosse interno, il passaggio della semiretta per un vertice costituisce normale intersezione
- nel caso di punto esterno, il passaggio per un vertice costituisce "anomalia solo quando la semiretta risulta essere tangente al poligono. Ovviamente ho esteso il concetto di tangenza confidando nella vostra comprensione (non mi veine termine adatto al caso)
- in questo ultimo caso noto che i vertici adiacenti a quello intersecato si trovano entrambi nello stesso semispazio rispetto alla semiretta.

I casi pero' possono essere i piu' vari al crescere della complessità del poligono, potendo avere un vertice intercettato e successivamente due lati tagliati o ancora piu vertici intercettati in serie. Risulta pertanto fondamentale riuscire a filtrare all'inizio con opportuna scelta del punto Q i casi possibili.

Anticipo adesso il fatto che posso gia individuare quattro rette che chiamerei Xmax, Xmin, Ymax Ymin che sarebbero poi i lati del rettangolo che circoscrive il poligono. Si puo fin da subito verificare se il punto si trova internamente o esternamente a tale rettangolo.
Poi posso individuare altre due rette che chiamerei Xg e Yg passanti per il punto medio tra i vertici.
Queste due rette dividono in 4 l'intero piano e sarebbe possibile vedere in quale dei quattro quadranti si trova il punto di cui si vuol conoscere la posizione relativa rispetto al poligono.
Queste rette ausiliari ci potranno essere utili per la scelta del secondo punto Q della semiretta.

La condizione che la semiretta non deve passare per nessuno dei vertici nasce dal fatto che esiste una possibilità, con punto P esterno, di indeterminazione della posizione di P rispetto al poligono.

caxxo gio, però è un bel casino computazionale l'ultima verifica...(=da pensarci su un po')

eh, se così fosse tutto questo ambaradan non sarebbe necessario, prenderei come secondo punto per la semiretta il punto medio del primo lato e così mi assicuro che la semiretta non sarà mai tangente.

in realtà possono esserci casi di sfiga assai peggiori, tipo quello di figura (punto interno con un numero pari di intersezioni).

la soluzione potrebbe essere la seguente:
considerare il vertice i-1 e i+1 rispetto a quello intersecato: se essi finiscono tutti e due sopra o sotto la semiretta, è una "tangenza" e dunque conta per 2, viceversa è un'intersezione vera e propria, e conta per 1. Questo mi consentirebbe di semplificare radicalmente il metodo, scegliendo sempre la semiretta orizzontale.

ribadisco infatti che si vuole un metodo soprattutto ottimizzato per la velocità senza tante complicazioni (quadrato inscritto, rette ausiliarie, e così via: tutto tempo computazionale che non vorrei consumare)


ODIO QUANDO MI CANCELLA IL MESSAGGIO!!!

stavo dicendo, pare che siamo arrivati contemporaneamente alla stessa conclusione. La verifica di appartenenza allo stesso semispazio è banale, se la semiretta è di equazione
ax+by+c=0
per un punto che sta "sopra" vale ax+by+c>0, per uno che sta sotto <0

meglio ancora, scelgo sempre la semiretta verticale, così elimino il caso "singolare" della più compatta notazione y=mx+q; un lato verticale non verrà mai intersecato, e può quindi essere ignorato: anche se il punto si trovasse proprio sul prolungamento di questo lato, e quindi avesse infinite intersezioni, basta ignorarlo e il pari-dispari funziona ancora)