T1 Extra - Preenchimento de triângulos

O trabalho extra é, com três pontos não alinhados, preencher o triângulo gerado por esses três pontos. Para fazer isso, vamos utilizar as coordenadas baricêntricas para determinar se um ponto pertence ou não a um triângulo.

Definição: De acordo com esse método, cada ponto p do plano pode ser escrito na forma p = λ1 p1 + λ2 p2 + λ3 p3 , onde λ1, λ2 e λ3 são números reais e λ1 + λ2 + λ3 = 1 . Os coeficientes λ1, λ2 e λ3 são denominados coordenadas baricêntricas de p em relação a p1, p2 e p3.

Os valores de  λ1, λ2 e λ3 podem ser obtidos pela regra de Cramer:

O método de coordenadas baricêntricas nos diz que, se λ1, λ2 e λ3 forem maior que 0, então o ponto p pertence ao triângulo formado pelos pontos p1, p2, p3.

Problematização: Mas para saber quais pontos pertencem a um triângulo teríamos que checar todos os pontos da tela.

Bom, para otimizar o algoritmo, podemos limitar quantas comparações o programa pode vir a fazer. Pegando os maiores e menores valores para as coordenadas (x,y) dos vértices dos triângulos, iremos criar um retângulo que engloba o triângulo, limitando assim o número de comparações.

Exemplo da otimização, considere o triângulo abaixo:

Ilustração de um triângulo

Sem a otimização para preencher este triângulo deveríamos checar todos os pontos da tela. Com a otimização, vamos checar apenas os pontos dentro do retângulo, como ilustra a imagem abaixo.

Exemplificação da área de comparação utilizando a otimização

A imagem abaixo exibe o resultado final:

Resultado final do exemplo

Referências Bibliográfica: Bancos de Dados Geográficos - Capítulo 2. Algoritmo geométricos e relacionamentos topológicos. Disponível em:  <http://mtc-m12.sid.inpe.br/archive.cgi/sid.inpe.br/iris@1912/2005/07.01.19.38.>
How to determinate a point in a triangle - Stackoverflow. Disponível em: <http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle>