Geometria Computacional

Prof. Walter Mascarenhas

Segundo semestre de 2004

Aula 9

Decomposição em partes convexas

Convexo = simples

Não convexo = complexo

Ser convexo é:

Ser intersecção de semiplanos

Ter ângulos internos <=

180

Ter Pontos internos ligados por segmentos

internos

Custo baixo: teórico O(n). Esperado O(n log*n) na prática.Qualidade: ruim, n - 2 partes

Primeira tentativa: triangulação.

Custo baixo: teórico O(n). Esperado O(n log*n) na prática.Qualidade: 2 r + 1 partes, r = número de ângulos reversos

Segunda tentativa: juntar triângulos (Hertel and Mehlhorn).

Hertel and Mehlhorn: juntar quais triângulos?

Analise o “V” pontilhado associado a cada vértice reverso.

1- Se o “V” contiver diagonais, escolha uma delas e pinte-a de magenta.

2- Se o “V” não contiver diagonal alguma, pinte a diagonal mais próxima do “V” de cada lado de magenta.

3- Apague as diagonais que não foram pintadas de magenta.

Número de diagonais <= 2 r implica em número

de faces <= 2 r + 1.

Neste caso é melhor: r = 4 e nFaces = 7 < 9

Poderia ser melhor?

Hertel and Mehlhorn: resultado final

Número de diagonais <= 2 r implica em número

de faces <= 2 r + 1.

Neste caso é melhor: r = 4 e nFaces = 7 < 9

Poderia ser melhor?

Hertel and Mehlhorn: resultado final

Poderia ser ainda melhor?

Pode melhorar? Sim, escolha outra triangulação:

Pode melhorar? Só com diagonais não.

Pode melhorar?

Pode melhorar? De jeito nenhum!

Prova: cada “V” pontilhado tem que conter pelo menos um lado de uma parte convexa. Como os “V”s pontilhados são disjuntos, eles devem conter pelo menos 4 lados. Isto implica em pelo menos 5 partes convexas.

Teorema: o número mínimo de faces convexas é r/2 + 1.

Prova: cada vértice reverso tem que ser “quebrado” pelo menos uma vez. Uma diagonal quebra no máximo 2 vértices. Logo pelo menos r/2 diagonais deverão permanecer. Isto dá r/2 + 1 faces.

Casos gerais

Teorema: é sempre possível obter r + 1 partes convexas.

Prova: trace as bissetrizes dos vértice reversos, uma a uma. As r bissetrizes vão levar a r + 1 partes convexas.

Corolário: O algoritmo de Hertel & Mehlhorn erra por um fator de no máximo 4 ~ (2 r + 1) / (r/2 + 1).

Exemplos: pontos internos

Hertel and Mehlhorn pode atingir o fator 4:

Hertel and Mehlhorn pode atingir o fator 4:

Uma proposta de algoritmo O(n logn) que erra no máximo um fator de 2

Uma proposta de algoritmo O(n logn) que erra no máximo um fator de 2

Estruturas de dados

1- Array de listas duplamente ligadas para representar os polígonos em construção

2- Heap para determinar a o ordem dos eventos

3- Árvore balanceada para administrar os cortes da scanline

Uma proposta de algoritmo O(n logn) que erra no máximo um fator de 2. Eventos: novo lado

Uma proposta de algoritmo O(n logn) que erra no máximo um fator de 2. Eventos: novo máximo local

Uma proposta de algoritmo O(n logn) que erra no máximo um fator de 2. Eventos: novo mínimo local

Uma proposta de algoritmo O(n logn) que erra no máximo um fator de 2. Evento: lado cruza V

Uma proposta de algoritmo O(n logn) que erra no máximo um fator de 2. Evento: V cruza V