Punto apparteente ad un poligono

[cavay]

Salve a tutti,

sto implementando un prodotto scritto in c++ e mi servirebbe conoscere l'appartenenza di un punto ad un poligono.
Mi spiego meglio: dato un poligono P2D e dato un punto Pnto di coordinate (X,Y) mi interessa conoscere se tale punto cade nel poligono.
Sono riuscito a farlo solo per i poligoni convessi (ogni angolo interno è < 180 gradi), ma proprio non riesco per quelli concavi.(http://www.itportal.it/developer/vb/collisioni/default.asp)

Qualcuno saprebbe aiutarmi?

[mad_hhatter]

ciao, mi sono trovato ad affrontare lo stesso problema, ma ci ho solo pensato, niente implementazioni... l'idea è di tipo brute-force, quindi non so quanto sia efficiente. Però ogni lato del poligono induce una disequazione del tipo ax + by + c >= 0 (oppure <=), dove l'uguale lo metti solo se la frontiera del poligono fa parte del poligono stesso. il segno della disuguaglianza dipende dal particolare lato (credo). ora, per vedere se un punto qualsiasi appartiene al poligono, le sue coordinate devono verificare TUTTE le disuguaglianze indotte dai lati del poligono.

spero di esserti stato utile.

mad_hhatter

[cavay]

Scusami ma non mi è chiaro, forse avro posto male il problema.
Allora, semplifichiamo le cose e pensiamo ad un quadrato ABCD, dove:
A(0,0), B(5,0), C(5,5), D(0,5) e prendiamo in cosiderazione il pnto E(3,3) che appartiene al poligono e il punto F(6,6) che non appartiene. Come applicheresti il tuo algoritmo?



P.S.
Stiamo parlando di poligoni di 50 punti e non di 4.

[mad_hhatter]

supponi di avere una rappresentazione ordinata dei vertici del poligono, in modo che se la lista è A,B,C,D allora percorrendo i punti in tale ordine percorro il poligono in senso orario o antiorario (è indifferente). Se invece hai solo un elenco disordinato la cosa si fa problematica. Cmq, posto di avere tale ordinamento, puoi prendere i punti a 2 a 2 e ottenere l'equazione della retta di ciascun lato. ora una retta ha equazione ax+by+c = 0. se tu prendi la diseguaglianza ax+by +c >= 0 descrivi il semipiano generato dalla retta ax+by+c=0. Ora, l'intersezione dei semipiani associati a tutti i lati dà la porzione di spazio che definisce il poligono stesso. l'unica cosa è che bisogna vedere come definire il segno della disuguaglianza per considerare il semipiano giusto.

scrivendo le disuguaglianze per tutti i lati ottieni un sistema di N disuguaglianze. se un punto le verifica tutte, allora sei certo che cadenel poligono.

[mad_hhatter]

no, lascia perdere tutto, con i poligoni concavi non funziona!!! sono un idiota, mi dispiace.

perchè allora non suddividere un poligono concavo in sottopoligoni convessi(al peggio triangoli) e verificare se il punto appartiene a uno di essi? in questo modo puoi sfruttare l'algoritmo che hai già perchè lavoreresti con poligoni convessi

[PGI-Bis]

FruGOOGLa per "Jordan Curve Theorem". Dato un punto crei un raggio in una direzione arbitraria e conti il numero di intersezioni tra quel raggio e i lati del poligono. Se il totale è dispari, il punto si trova nel poligono. Se è pari, il punto è fuori dal poligono.

[mad_hhatter]

geniale, sei un mito

[PGI-Bis]

Ma che geniale, io non so manco perchè funziona :D L'ho solo letto su un libro.

[mad_hhatter]

beh funziona perchè un poligono è una linea chiusa e se parti dall'esterno, ogni volta che fai un attraversamento in uscita devi per forza averne fatto uno in entrata, mentre se parti dall'interno hai un attraversamento in uscita più 0 o più coppie di attraversamenti uscita-entrata, uno per ciascuna concavità che incontri...

è un metodo geniale nella sua semplicità

[wingman87]

Xò se il raggio creato è tangente al poligono non funziona

[cavay]

FruGOOGLa per "Jordan Curve Theorem". Dato un punto crei un raggio in una direzione arbitraria e conti il numero di intersezioni tra quel raggio e i lati del poligono. Se il totale è dispari, il punto si trova nel poligono. Se è pari, il punto è fuori dal poligono.

Il Teorema lo conosco ma non funziona se il raggio interseca un lato del poligono in un vertice.
Per adesso è cosi' che l'ho implementato, aggiungendo dei controlli in +, ma computazionalmente non è leggero.

[mad_hhatter]

beh, quel metodo credo non possa essere alleggerito piu di tanto: tu cerchi le intersezioni con TUTTI i lati del poligono?

perche' se interseca in un vertice non funziona?

[wingman87]

Non funziona se il raggio è tangente al poligono in qualche suo punto perchè invece di contare 1 x l'entrata e 1 x l'uscita conta solo 1

[cionci]

Credo che sia sufficiente prendere come raggio la distanza fra il punto ed il vertice più lontano aumentata di uno ;) Che tra l'altro è anche una cosa che si fa abbastanza facilmente...

[Slide]

Ricerca operativa.. che incubo di esame è stato per noi :( Un prof. che a lezione ci insultava solamente senza spiegare poi molto. :doh:

Se vi vedete per ripassare, chiamatemi! :D

[mad_hhatter]

Credo che sia sufficiente prendere come raggio la distanza fra il punto ed il vertice più lontano aumentata di uno ;) Che tra l'altro è anche una cosa che si fa abbastanza facilmente...

perche' aumentata di uno?

il fatto e', cmq, che per qualsiasi vertice io possa prendere mi viene in mente un controesempio: una forma particolare del poligono per cui l'algoritmo PUO' fallire... forse bisognerebbe provare piu' vertici... oppure prendere 2 vertici consecutivi e prendere il raggio passante per un punto appartenente al lato da essi individuato. e se per caso tale lato risulta parallelo al raggio (nel caso in cui i 2 punti siano allineati con il punto da testare), cambio uno dei due vertici