Triangulação de polígono - Polygon triangulation

Triangulação poligonal

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

As 42 triangulações possíveis para um heptágono convexo (polígono convexo de 7 lados). Este número é dado pelo 5º número catalão .

É 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 orelha de polígono

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

Quebrando um polígono em polígonos monótonos

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

Veja também

Referências

links externos