Newsgroup: it.scienza.informatica
Titolo: Algoritmo collisione poligoni

Salve,
mi servirebbe un algoritmo per verificare se due poligoni (di qualsiasi 
tipo, concavi o convessi) hanno punti in comune, cioè se si intersecano. 
Successivamente, a verifica positiva, dovrei fondere i due poligoni in un 
unico poligono.
Ho pensato a fare un scanline dei due poligoni su una matrice per risolvere 
il problema della collisione, ma poi per ottenere il nuovo poligono devo 
rivettorizzare e quindi mi sembra poco efficiente.
Qualcuno che mi sappia indicare la via su cui procedere?
Grazie 1000!
Fabrizio

 unico poligono.
Qui bisogna ragionare un po' di più...
--
Xelloss 

 Ho pensato a fare un scanline dei due poligoni ...
Cattiva idea. Raramente e' meglio converire in algoritmo raster un 
algoritmo vettoriale, se il risultato finale deve essere vettoriale.
E' come risolvere numericamente un problema analitico quando vogliamo 
una soluzione analitica.
Ci sono quattro possibilita':
1) Il primo e' contenuto nel secondo.
2) Il secondo e' contenuto nel primo.
3) Almeno un lato del primo (primo estremo compreso e secondo estremo 
escluso) interseca almeno un lato del secondo (primo estremo compreso e 
secondo estremo escluso).
4) L'intersezione e' vuota.
Io prima cercherei se gli ingombri dei poligoni si intersecano. In caso 
negativo, l'intersezione e' vuota (caso 4).
Poi cercherei tutte le intersezioni tra i lati del primo poligono e 
quelli del secondo. La complessita' e' O(m x n), dove m e n sono i 
numeri di lati dei due poligoni.
Se c'e' qualche intersezione, allora sono nel caso 3, e mi rimane il 
compito di ritagliare e incollare i perimetri nei punti di intersezione, 
in modo da ottenere il poligono intersezione.
Se non ci sono intersezioni, prendo un punto qualunque del primo 
poligono e determino se e' contenuto nel secondo. In caso affermativo, 
sono nel caso 1, e il poligono intersezione e' il primo poligono stesso. 
In caso negativo, prendo un punto qualunque del secondo poligono e 
determino se e' contenuto nel primo. In caso affermativo, sono nel caso 
2, e il poligono intersezione e' il primo poligono stesso. In caso 
negativo sono nel caso 4.
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

P51D wrote:
 > mi servirebbe un algoritmo per verificare se due poligoni (di
 > qualsiasi tipo, concavi o convessi) hanno punti in comune, cioè se si
 > intersecano. Successivamente, a verifica positiva, dovrei fondere i
 > due poligoni in un unico poligono.
 >



Evita di rasterizzare, se rappresenti i poligoni come un'unica lista di
vertici (e quindi puoi avere autointersecazioni ma non buchi), puoi usare
l'algoritmo di Greiner-Hormann: 
http://portal.acm.org/citation.cfm?id=274364
Se invece ti serve gestire i buchi puoi pensare all'algoritmo di
Weiler-Atherton: 
http://portal.acm.org/citation.cfm?id=56389
ma ci sono anche approcci piu' moderni ad operazioni booleane fra poligoni,
vedi qui per esempio il metodo di Peng (ed altri):
http://cgcad.thss.tsinghua.edu.cn/~pengyu/papers/boolpoly.pdf
Puoi infine dare una occhiata ai software opensource che implementano metodi
di clipping:
http://clippoly.sourceforge.net/
http://www.cs.man.ac.uk/~toby/alan/software/gpc.html
ma anche cercando su google code search:
http://www.google.com/codesearch
Comunque come ti diceva qualcun altro il primo passo e' trovare l'intersezione
fra i lati dei poligoni, nel caso volessi pensare ad un algoritmo tutto tuo.
Ciao ciao,
   AO.