Geometria Computacional
Prof. Walter Mascarenhas
Segundo semestre de 2004
Aula 5
Triangulação em O(n logn)
1- Ordene os pontos pela coordenada y O(n logn)
2- Decomponha o polígono em trapézios usando
uma scanline O(n logn)
3- Usando os trapézios, quebre o polígono em
partes monótonas através da eliminação das
cúspides internas O(n)
4- Triangule as partes monótonas O(n)
Vértices reversos e cúspides internas
Um vértice v de um polígono P é reverso se o seu ângulo interno é
estritamente maior que pi. Um vértice reverso r é uma cúspide interna
de P com relação à reta r se seus dois vizinhos estão contidos no
mesmo semi-plano fechado definido pela paralela a r que passa por v.
Partição em trapézios
Um polígono particionado em trapézios (triângulos são trapézios
degenerados.) Note que o lado inferior de cada trapézio contém
exatamente um vértice e o superior também
Método da scanline
Algoritmo:
1- Entrada: Polígono
2- Saída: lista de trapezóides, onde
struct Trapezoide
{
int ladoDireito;
int ladoEsquerdo;
int verticeInferior;
int verticeSuperior;
};
Algoritmo:
1- Usar estrutura de dados que permita busca,
inserção e remoção em O(log n) comparações para
armazenar os lados cortados pela scanline
2- Armazenar os vértices em um vetor ordenado
pela coordenada y.
3- For( i = 0; i < nVertices; i++)
trateVertice(i)
A estrutura de dados que mantém os
lados é ordenada assim:
int compare(lado1, lado2)
{
x1 = xDoCorte(lado1,scanline);
x2 = xDoCorte(lado2,scanline);
if( x1 < x2 )
return -1;
if( x1 > x2 )
return 1;
return compareInclinacoes(lado1,lado2);
}
Importante: esta comparação não se altera quando
a scanline move. Se dois lados estão na estrutura de dados em dois
momentos diferentes, então o resultado da comparação será o mesmo
nos dois instantes.
Trate vértice: 6 casos
1- Dois lados acima da scanline
1.1 Vértice reverso
1.2 Vértice convexo
2- Dois lados abaixo da scanline
2.1 Vértice reverso
2.2 Vértice convexo
3- Lados em lados opostos
3.1 Polígono à esquerda
3.2 Polígono à direita
1- Dois lados acima da scanline
1.1 Vértice reverso: completar o trapézio ativo e inserir os dois
lados. Atualizar o vértice inferior dos lados adjacentes
1.2 Vértice convexo: inserir os lados.
2- Dois lados abaixo da scanline
2.1 Vértice reverso. Completar os dois trapézios, remover os lados
adjacentes e atualizar os vértices inferiores dos lados vizinhos
2.2 Vértice convexo. Completar o trapézio e remover os lados
3- Lados em lados opostos da scanline
3.1 Polígono à esquerda: Completar o trapézio, usando o lado adjacente
esquerdo. Remover lado de baixo, inserir lado de cima, atualizar vértice
de baixo do lado adjacente esquerdo.
3.2 Polígono à direita. Completar o trapézio, usando o lado adjacente
direito. Remover lado de baixo, inserir lado de cima, atualizar vértice de
baixo do lado adjacente direito.
O que fazer com y’s repetidos?
1- Rotacionar a scanline, escolher outra direção
2- Rotacionar o polígono
3- Simular uma rotação muito pequena
Efeitos colaterais
1- Rotacionar a scanline, escolher outra direção:
Calcular interseções com retas inclinadas é mais
caro do que com retas horizontais. Além disso,
como escolher uma “boa” direção?
2- Rotacionar o polígono: As coordenadas dos
vértices deixam de ser inteiras. Como achar um
bom ângulo de rotação?
3- Simular uma rotação muito pequena. Como?
Rotação simulada
Rotacione os vértices por um ângulo minúsculo.
Qual ângulo?
Se for minúsculo, não importa!
Rotação simulada
Rotação simulada
E as interseções com a scanline?
Para cada lado horizontal no polígono original, a interseção
com a scanline será o primeiro vértice quando ele entra na
estrutura de dados e o segundo vértice logo em seguida,
quando ele sairá.