Triangulação de polígono - Polygon triangulation
Na geometria computacional , polígono triangulação é a decomposição de uma área poligonal ( simples polígono ) P em um conjunto de triângulos , isto é, encontrar um conjunto de triângulos com interiores aos pares que não se cruzam, cuja união é P .
As triangulações podem ser vistas como casos especiais de gráficos de linhas retas planas . Quando não há buracos ou pontos adicionados, as triangulações formam gráficos planares externos máximos .
Triangulação de polígono sem vértices extras
Com o tempo, vários algoritmos foram propostos para triangular um polígono.
Casos especiais
É trivial triangular qualquer polígono convexo no tempo linear em uma triangulação em leque , adicionando diagonais de um vértice a todos os outros vértices.
O número total de maneiras de triangular um n -gon convexo por diagonais sem interseção é o ( n −2) nd número catalão , que é igual
- ,
uma fórmula encontrada por Leonhard Euler .
Um polígono monótono pode ser triangulado em tempo linear com o algoritmo de A. Fournier e DY Montuno ou o algoritmo de Godfried Toussaint .
Método de corte de orelha
Uma maneira de triangular um polígono simples é baseada no teorema das duas orelhas , como o fato de que qualquer polígono simples com pelo menos 4 vértices sem buracos tem pelo menos duas ' orelhas ', que são triângulos com dois lados sendo as arestas do polígono e o terceiro completamente dentro dele. O algoritmo, então, consiste em encontrar essa orelha, removê-la do polígono (o que resulta em um novo polígono que ainda atende às condições) e repetir até que reste apenas um triângulo.
Este algoritmo é fácil de implementar, mas mais lento do que alguns outros algoritmos e só funciona em polígonos sem buracos. Uma implementação que mantém listas separadas de vértices convexos e côncavos será executada em tempo O ( n 2 ) . Este método é conhecido como corte da orelha e, às vezes, corte da orelha . Um algoritmo eficiente para cortar orelhas foi descoberto por Hossam ElGindy, Hazel Everett e Godfried Toussaint .
Triangulação poligonal monótona
Um polígono simples é monótono em relação a uma linha L , se qualquer linha ortogonal a L cruzar o polígono no máximo duas vezes. Um polígono monótono pode ser dividido em duas cadeias monótonas . Um polígono monótono em relação ao eixo y é denominado monótono y . Um polígono monótono com n vértices pode ser triangulado em tempo O ( n ) . Assumindo que um determinado polígono é y-monótono, o algoritmo ganancioso começa caminhando em uma cadeia do polígono de cima para baixo enquanto adiciona diagonais sempre que possível. É fácil ver que o algoritmo pode ser aplicado a qualquer polígono monótono.
Triangular um polígono não monótono
Se um polígono não for monótono, ele pode ser particionado em subpolígonos monótonos em tempo O ( n log n ) usando uma abordagem de linha de varredura . O algoritmo não exige que o polígono seja simples, portanto, pode ser aplicado a polígonos com orifícios. Geralmente, este algoritmo pode triangular uma subdivisão plana com n vértices em tempo O ( n log n ) usando espaço O ( n ) .
Gráfico duplo de uma triangulação
Um gráfico útil frequentemente associado a uma triangulação de um polígono P é o gráfico dual . Dada uma triangulação T P de P , define-se o grafo G ( T P ) como o grafo cujo conjunto de vértices são os triângulos de T P , sendo dois vértices (triângulos) adjacentes se e somente se compartilham uma diagonal. É fácil observar que G ( T P ) é uma árvore com grau máximo 3.
Complexidade computacional
Até 1988, se um polígono simples pode ser triangulado mais rápido do que o tempo O ( n log n ) era um problema em aberto na geometria computacional. Em seguida, Tarjan & Van Wyk (1988) descobriram um algoritmo de tempo O ( n log log n ) para triangulação, posteriormente simplificado por Kirkpatrick, Klawe & Tarjan (1992) . Seguiram-se vários métodos aprimorados com complexidade O ( n log * n ) (na prática, indistinguível do tempo linear ).
Bernard Chazelle mostrou em 1991 que qualquer polígono simples pode ser triangulado em tempo linear, embora o algoritmo proposto seja muito complexo. Um algoritmo aleatório mais simples com tempo linear esperado também é conhecido.
O algoritmo de decomposição de Seidel e o método de triangulação de Chazelle são discutidos em detalhes em Li & Klette (2011) .
A complexidade de tempo da triangulação de um polígono de n- vértices com buracos tem um limite inferior Ω ( n log n ) , em modelos de árvore de computação algébrica de computação. É possível calcular o número de triangulações distintas de um polígono simples em tempo polinomial usando programação dinâmica e (com base neste algoritmo de contagem) para gerar triangulações uniformemente aleatórias em tempo polinomial. No entanto, contar as triangulações de um polígono com buracos é # P-completo , tornando improvável que possa ser feito em tempo polinomial.
Objetos e problemas relacionados
- Ambos os problemas de triangulação são um caso especial de triangulação (geometria) e um caso especial de partição poligonal .
- A triangulação de peso mínimo é uma triangulação em que o objetivo é minimizar o comprimento total da borda.
- Uma triangulação por conjunto de pontos é uma triangulação poligonal do casco convexo de um conjunto de pontos. Uma triangulação de Delaunay é outra maneira de criar uma triangulação com base em um conjunto de pontos.
- O Associahedron é um politopo cujos vértices correspondem às triangulações de um polígono convexo.
- Cobertura de triângulo poligonal , na qual os triângulos podem se sobrepor.
- Ladrilhos por polígonos , onde o objetivo é cobrir todo o plano com polígonos de formas pré-especificadas.
Veja também
Referências
links externos
- Demonstração como Flash swf , um algoritmo de linha de varredura.
- Explicação de Song Ho sobre o tesselator OpenGL GLU