Os problemas de geometria computacional são dos problemas comuns dos concursos de programação.
Este e os próximos tutoriais vão apresentar um conjunto de algoritmos para resolver problemas geométricos típicos a duas dimensões.
Por vezes dividem-se estes problemas em puramente geométricos, ie, aqueles que se poderiam resolver com régua e compasso (eg, encontrar o bisector), e a geometria computacional, ie, aqueles que precisam de um computador (eg, calcular o convex hull). Aqui não faremos essa distinção por não ser muito relevante no contexto.
Os problemas geométricos lidam normalmente com doubles, o que requer alguma atenção com a manipulação numérica. Convém dar uma leitura prévia ao guião dos floats e doubles, se ainda não o fizeram.
O objectivo destes tutoriais é dar um conjunto de ferramentas para que possam resolver, com maior facilidade, problemas geométricos específicos. No total vamos ter muitas linhas de código mas para resolver um dado problema, apenas precisaremos de uma parte deste todo.
O código apresentado baseia-se no capítulo 7 do livro do Halim, mas inclui algumas implementações diferentes e funções extra que não surgem no livro.
A editora Springer disponibiliza acesso a um livro deste tema, para quem estiver interessado.