polignos convexos

acosta78

Power Member
algoritmos sobre intersecção de polígonos convexos
alguma coisa...por ai...
Espi43.gif

obrigado a todos
 
Na net tens várias páginas:

http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE191.HTM

http://citeseer.ist.psu.edu/cache/p...convex.intersection.pdf/toussaint85simple.pdf

se procurares no google irás descobrir ainda mais. Dos vários algorítmos, muitos diferem no tempo de execução, normalmente indexado ao número de vértices de ambos os polígnos (normalmente representados por n e m).

Se tudo isto é complicado para ti e não tens necessáriamente uma preocupação com o tempo de execução, até porque poderás usar algorítmos simples, podes dividir o problema em dois mais simples:

Se um poligono intersecta outro então tens duas hipóteses:


  • Dois ou mais lados dos polígonos intersectam-se (intersecção de linhas)

  • Um ou mais vértices de um polígono está no interior do outro.

Se fizeres estas duas verificações podes determinar se um polígono se intersecta com outro, contudo não terás a intersecção deles (o polígono resultante).
 
Back
Topo