[algoritmo] verificare la sovrapposizione di 2 poligoni irregolari

[nik600]

ciao

come è spiegato nell'oggetto sto cercando di fare un algoritmo che verifica la sovrapposizione di due poligoni irregolari, o meglio la sovrapposizione dell'area sia parziale che totale (i due poligoni hanno un'area in comune , oppure un poligono contiene l'altro)

io ho un array di punti con coordinate x,y l'insieme dei punti forma il poligono

ho gia fatto un paio di prove ma nessuna delle due funziona nel 100 % dei casi

- prima iptesi

vedere se i punti con

-min x
-max x
-min y
-max y

contengono i rispesstivi punti dell'altro poligono, questo funziona ma non sempre

poi ce n'è un'altro che per tutti i punti con x = verifica se la coordinata y maggiore e minore contiene la y del punto che sto controllando

anche questo però non va sempre bene


bah... :master: qualche idea?

[Diego75]

AL momento non ho una soluzione, ti consiglierei comunque di cambiare strada.
Non puoi ragionare su max x e min x o y infatti se il poligono è 'concavo' potrebbe avere max x > dell'altro idem per max y e non contenerlo.

[Diego75]

Potrebbe essere più promettente la seguente strada :
1 - i 2 poligoni si intersecano in almeno un punto, il punto non è un vertice --> il poligono 'piccolo' non è interamente contenuto nell'altro
2 - come sopra ... se il punto è un vertice o è incluso completamente o è completamente escluso (basta controllare un qualunque punto interno al poligono e vedere se è interno anche all'atro)
3 - non hanno punti in comune --> o è escluso o è incluso completamente (stesso controllo del punto 2)

Non è detto che sia la strada migliore ma è quella che proverei io...

[nik600]

ciao infatti io ho detto che il metodo non funzionava sempre!

giustamente tu hai capito subito dove era l'errore...per ora però è l'unica soluzione affidabile!

io ho sbagliato a fare il titolo, a dire la verità quello che devo vedere è se un poligono è contenuto nell'altro, mi sono spiegato male...

la tua soluzione potrebbe andare bene il fatto è che nel dominio che sto analizzando non è previsto che ci sia la sovrapposizione del punto di un poligono sopra il punto di un'altro

quello che devo verificare è se il poligono a è contenuto dal poligono b

...
forse con le aree?

[daniele_dll]

mmm

beh, un po di consigli, spero, utili

- fai una lista di poligoni in base alla dimensione dove, ad es, l'ultimo è il più grande, ed il primo il più piccolo (in base all'area), dopo di che inizi il confronto ... se hai 5 poligoni...confronti il 1°, 2°, 3° e 4° con il quinto...poin il 1°, 2° ed il 3° con il 4° poi il 1° ed il secondo con il 3° e cosi via

- potresti crearti in memoria una mappa delle aree, come fosse una unica grande immagine...con dentro i vari poligoni, oppure ti crei un elenco con tutti i punti che compongo il poligono, e verificare semplicmente se uno dei punti dei bordi sta all'interno dei un area (che ovviamente non sia la sua), questo funziona solo nel caso di parzialmente contenuto o nel caso vi siano due poligoni perfettamente uguali, per verificare se uno è contenuto in un altro, devi usare il primo sistema

forse un mix di questi due sistemi, che CERTAMENTE, possono essere ottimizzati, possono darti un aiuto

(non ho letto tutto il thread )

[nik600]

ciao

io ho gia per ogni poligono irregolare (che in realtà è una isoipsa) l'elnco dei punti contenuti in un array, il problema è che questo

verificare semplicmente se uno dei punti dei bordi sta all'interno dei un area (che ovviamente non sia la sua)

non credo sia molto semplice da implementare, per via del fatto che i poligoni sono irregolari...

in sostanza, come verifico se un punto è contenuto o no in un area?

[daniele_dll]

su ti ho proposto due possibili soluzioni

[nik600]

mi spiace ma non le ho capite!

nel senso, ho capito che la soluzione migliore in assoluto è questa:

verificare semplicmente se uno dei punti dei bordi sta all'interno dei un area (che ovviamente non sia la sua)

il problema è: come lo verifico?

io ho gia per ogni poligono l'elenco dei suoi punti, quindi dovrei costruire un'area prendendo i punti del poligono A, e poi verificare se il punto x,y del poligono B è nell'area A

il problema è questa cosa come la faccio?

[daniele_dll]

creati una lista linkata, o molto meglio ancora, una hash map basata su una doppia chiave...coordinata X e coordinata Y

se ti costruisci questo hash map per verificare se è contenuto da qualche parte fai un semplice if

è la soluzione che occupa più memoria...ma...è anche la più performante in termini di velocità e la più semplice da fare (credo)

[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?