Triangulação de Polígonos

Estou esperando uma reunião com meu orientador para dar continuidade à implementação do meu algoritmo aproximado. Neste meio tempo tenho tentado colocar em prática alguns planos arquivados durante o semestre. O primeiro deles é o desenvolvimento de mais applets de geometria computacional para colocar na minha página pessoal. Escolhi o algoritmo de triangulação de polígonos.

A geometria computacional é uma subárea da teoria, e é uma das que eu mais gosto, talvez porque seja mais ‘visual’ do que as outras (talvez por isso gosto de computação gráfica e quem sabe venha a gostar de processamento de imagens). Diferentemente do que eu estudo em algoritmos aproximados, ou MC548, os algoritmos de geometria computacional estudados são geralmente polinomiais. Claro que temos os NP-difíceis, e a prova de complexidade geralmente é muito bonita, pois geralmente se reduz um problema ‘visual’ a um abstrato. Enfim, o estudo que se faz em cima desses algoritmos é no sentido de reduzir a complexidade de O(n^2) por exemplo para O(n).

Voltando ao problema da triangularização, existe um algoritmo O(n^3) ‘trivial’, foram desenvolvidos algoritmos O(n^2), O(n logn), O(n log ( log n)) e até o melhor possível (estado da arte), um algoritmo O(n). Este último, desenvolvido por Chazelle [1], é tão complexo que ainda existem estudos em cima deste problema procurando um algoritmo linear mais simples. Versões probabilísticas também atingem essa complexidade linear.

Eu decidi implementar a versão quadrática, que ainda é bem simples. Ele é baseado em remoção de ‘orelhas’ do polígono, que são nada mais que triângulos formados por três vértices adjacentes. Este algoritmo também é conhecido como Van Gogh [3], hehehe. O algoritmo pode ser conferido na minha página pessoal [4].

Referências:
[1] Chazelle, B. “Triangulating a Simple Polygon in Linear Time.” Disc. Comput. Geom. 6, 485-524, 1991.
[2] Triangulation — from Wolfram MathWorld
[3] Wikipedia – Vincent van Gogh
[4] Triangulação de Polígonos

Os comentários estão fechados.

%d bloggers like this: