Geometria Computacional
Prof. Walter Mascarenhas
Segundo semestre de 2004
Aula 4
Produto vetorial
Fórmulas
Encarando como transformação linear:
Mais fórmulas
Generalizações
Orientação indica esquerda/sobre/direita
esquerda/direita/sobre && interseção
Corte transversal <=>
esquerda(A,B,C) * esquerda(A,B,D) =
esquerda(C,D,A) * esquerda(C,D,B) = -1
esquerda(A,B,C) * esquerda(A,B,D) = 1
ou
esquerda(C,D,A) * esquerda(C,D,B) = 1
=> não há interseção
Restam os casos degenerados
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 trapezóides, 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 reflexos e cúspides internas
Um vértice v de um polígono P é reflexo se o seu ângulo interno é
estritamente maior que pi. Um vértice reflexo 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
Poligonais estritamente monótonas
Uma poligonal P é estritamente monótona com respeito à
uma reta r se toda perpendicular à r corta P em no máximo
um ponto
Poligonais monótonas
Uma poligonal P é monótona com respeito à uma reta r se toda
perpendicular à r corta P em no máximo uma componente conexa
Observação
Polígonos monótonos
Uma polígono é (estritamente) monótono com respeito à uma reta r se
puder ser particionado em duas poligonais que são (estritamente)
monótonas com respeito a r
Conseqüência da observação passada
Critério de não monotonicidade
Lema: Um polígono P não monótono com relação a uma reta r
contém pelo menos uma cúspide interna.
A recíproca deste lemma e versões mais fortes são falsas:
Idéia da prova do Lema
(os detalhes são muito chatos)
``Prova’’ do Lema: suponha que o polígono esboçado na figura não é
monótono. Então podemos assumir que uma paralela a r intercepta a
poligonal cyan em mais de uma componente conexa.
Isto implica que v0 está abaixo
da paralela e vn está acima.
Portanto a paralela também corta
a poligonal amarela. Ai temos
alguns casos. Por exemplo,
poderíamos conectar o ponto a
ao ponto b ou ao ponto c
Continuação da prova do Lema
De trapezóides para partes monótonas:
Basta remover as cúspides internas conectando-as da
seguinte maneira:
1- Uma cúspide interna que está no lado inferior de um
trapézio é ligada ao vértice do polígono que está no lado
superior do mesmo trapézio por uma diagonal
2- Uma cúspide interna que está no lado superior de um
trapézio é ligada ao vértice do polígono que está no lado
inferior do mesmo trapézio por uma diagonal
De trapezóides para partes monótonas:
Finalmente, triangular polígono
monótono em O(n):