Implementação do plano projetivo orientado na biblioteca CGAL

CGAL (Computational Geometry Algorithms Library) e uma biblioteca de estruturas de dados e algoritmos geometricos confiaveis que vem sendo desenvolvida de forma cooperativa por um consorcio formado por instituicoes na Europa e em Israel. Os algoritmos de CGAL estao implementados sobre a geometria Euclidiana, onde, geralmente, e necessario tratar muitos casos especiais. A geometria projetiva orientada engloba a geometria Euclidiana e em ambas, existe a nocao de convexidade e de orientacao [St091]. Como mencionado em [St091], algoritmos desenvolvidos sobre a geometria projetiva orientada sao mais simples e sucintos e, alem disso, o uso de coordenadas homogeneas simplifica as formulas e evita operacoes de divisao, as quais, muitas vezes, podem gerar imprecisao nos resultados dos algoritmos. Sendo assim, o objetivo deste trabalho foi estender para o plano projetivo orientado (PPO), varios algoritmos da biblioteca CGAL implementados em R2 e comprovar a reducao do numero de casos tratados. Dentre os algoritmos desenvolvidos, verificou-se que varios deles apresentaram solucoes mais homogeneas no PPO, enquanto outros, em razao de caracteristicas deste espaco, requerem o tratamento de alguns casos especiais. Observou-se que uma das grandes vantagens do PPO e poder representar pontos no infinito e distâncias infinitas, assim como compara-las relativamente. Verificou-se ainda que, no PPO, e mais dificil projetar algoritmos por varredura do que em R2, pois, como mostrado no capitulo 5, e necessario ter um certo cuidado com a identificacao do ponto de parada. Desta forma, podemos concluir que alguns algoritmos sao mais propicios ao PPO, enquanto outros podem apresentar a necessidade de tratamento de casos especiais. Sendo assim, recomenda-se um estudo minucioso do algoritmo antes de optar por implementa-lo em R2 ou estende-lo para o PPO. Abstract