[algoritmo] verificare la sovrapposizione di 2 poligoni irregolari

[nik600]

sorry...l'immagine!

[daniele_dll]

Originariamente inviato da nik600
scusa eh...

guarda l'immagine

io ho tutti i punti di A e tutti i punti di B e tutti i punti di C (precisi al pixel)

B contiene C
B non contiene A

il controllo che dici te funzionerebbe sono se si avessero tutti i punti dell'area (l'intera superficie) non solo il contorno

e quindi il problema è come ottengo tutti i punti che compongono una superficie, avendo solo i punti che la delimitano?

il controllo, in generale, va bene, ma qui è un caso estremo

cmq...avendo il contorno puoi facilmente calcolare tutta la superfice

cmq tu hai dei dati "vettoriali" quindi puoi usare algorittimi già pronti da studiare

vedi se trovi qualcosa di utile qui
http://homepages.borland.com/efg2lab...Processing.htm
http://www.geometryalgorithms.com/
http://www.geometryalgorithms.com/algorithm_archive.htm

[nik600]

ciao

mi e venuta un idea su come calcolare l-area

prendo tutti i punti che hanno coordinata x,

se ho solo 1 punto significa che quello fa parte di un bordo

se ho 2 punti tutti i punti da x1 a x2 fanno parte dell-area

se ho 3 punti area su x = da x1 a x2 piu x3

se ho 4 punti area su x = da x1 a x2 piu da x3 a x4


e avanti cosi....

questo per tutte le x dovrebbe darmi tutti i punti del poligono e quindi l-area

poi posso fare il controllo che dicevi tu e cioe prendere un punto qualsiasi del contorno di un poligono e vedere se [ presente nell-area dell-altro

non l-ho ancora implementata....ciao

[edriv]

Non credo sarebbe sempre valido, come nel seguente caso:
ho due punti (x1 e x2), ma entrambi sono dei vertici , il poligono è concavo e quindi non c'è nessun punto compreso nell'area tra x1 e x2...

Comunque per ora a me non viene in mente nessuna soluzione...

[Andrea1979]

spulciando fra tutti i link di Lele, questo ti è di sicuro interesse:

http://www.geometryalgorithms.com/Ar...rithm_0103.htm

Se lo testi contro tutti i vertici di un poligono trovi se ha intersezioni oppure no. Non risolve il caso della completa inclusione (dovresti testarlo contro tutti i punti del bordo di un poligono...)

Puoi certamente fare delle assunzioni preliminari, onde evitarti test inutili (tipo all'algoritmo 8 del link). In sostanza se un poligono ha la massima y inferiore alla minima y dell'altro, sicuramente saranno disgiunti etc...

[nik600]

cavolo è vero...

:master:

[nik600]

ho letto i link che mi avete dato, in particolare questo:

http://www.geometryalgorithms.com/Ar...rithm_0103.htm



vorrei chiedervi se secondo voi l'ho interpretato in modo corretto,

in sostanza io ho 2 poligoni, A e B

prendo un punto a caso di B e conto quanti punti ho in A con:

stessa x del punto scelto in B
y > del punto scelto il B

se il totale dei punti che ottengo è dispari, allora il punto (e quindi il poligono ) è contenuto, altrimenti è pari

cosa ne dite? ho capito correttamente?

[Andrea1979]

sì, tranne che con due poligoni convessi il fatto che tutti i vertici di uno siano contenuti nell'altro implica che il primo contiene il secondo. Se almeno uno dei poligoni è concavo invece il discorso non regge (e devi testare tutti i punti del bordo).