Loading AI tools
Da Wikipédia, a enciclopédia livre
Em matemática, uma Triangulação de Delaunay para um conjunto de pontos P no plano é uma triangulação DT(P) onde nenhum ponto em P está dentro da circunferência formada por qualquer triângulo na DT(P). A Triangulação de Delaunay maximiza o menor ângulo de todos os triângulos na triangulação; esta tende a evitar triângulos com ângulos internos muito pequenos.
A triangulação foi inventada por Boris Delaunay em 1934.[1] Para um conjunto de pontos em uma mesma linha, não existe Triangulação de Delaunay (o conceito de triangulação é desfeito para este caso). Para quatro ou mais pontos em um mesmo círculo (isto é, os pontos são cocirculares) a Triangulação de Delaunay não é única: cada uma das duas possibilidades de triangulação que divide o quadrilátero em dois triângulos satisfaz a “condição Delaunay”, isto é, que as circunferências de todos os triângulos tenham interiores vazios. Considerando que as circunferências são esferas, a noção de Triangulação de Delaunay estende-se a três dimensões. Generalizações são possíveis para métricas diferentes das Euclidianas. Entretanto, nestes casos não se pode garantir a existência ou a unicidade da Triangulação de Delaunay.
A triangulação de um conjunto discreto de pontos P corresponde ao grafo dual do Diagrama de Voronoi para P. Casos especiais incluem a existência de três pontos colineares e quatro pontos cocirculares.
Para um conjunto P de pontos no (d-dimensional) espaço Euclidiano, a Triangulação de Delaunay é uma triangulação DT(P) onde nenhum ponto em P está contido dentro do circum-hiperesfera de um simplexo em DT(P). Sabe-se [2] que existe uma única triangulação de Delaunay para P, se P é um conjunto de pontos em posição geral; Isto é, não existe k-flat contendo k + 2 pontos nem uma k-esfera contendo k + 3 pontos, para 1 ≤ k ≤ d − 1 (isto é, para um conjunto de pontos no ℝ3 não há três pontos em uma reta, nem quatro em um plano ou círculo, e não há cinco pontos em uma esfera). O problema de encontrar a triangulação de Delaunay de um conjunto de pontos no espaço Euclidiano d-dimensional pode ser convertido para o problema de fecho convexo e um conjunto de pontos em um espaço (d + 1)-dimensional, pela adição de uma coordenada extra a cada ponto p igual a |p|2, pegando-se o lado mais baixo do fecho convexo, e mapeando-o de volta para o espaço d-dimensional pela remoção da última coordenada. Assim como o fecho convexo a triangulação também é única, assumindo-se que todas as faces do fecho convexo são simplexos. Faces não simpliciais ocorrem somente quando d + 2 dos pontos originais incidem em uma mesma d-hiperesfera, isto é, se os pontos não estão em posição geral.
Suponha que n seja o número de pontos e d o número de dimensões:
Observando-se as propriedades acima, um importante ponto surge: olhando para os dois triângulos ABD e BCD com a aresta BD em comum (veja as figuras), se a soma dos ângulos α e γ for menor ou igual a 180°, os triângulos satisfazem a condição de Delaunay. Esta é uma importante propriedade, pois permite o uso da técnica de flipping. Se dois triângulos não satisfazem a condição de Delaunay, trocando-se a aresta comum BD pela aresta comum AC produz-se dois triângulos que satisfazem a condição Delaunay:
Muitos algoritmos para computar triangulações de Delaunay apoiam-se em operações rápidas para detectar quando um ponto está contido em uma circunferência de algum triângulo e uma eficiente estrutura de dados para armazenamento de triângulos e arestas. Em duas dimensões, uma forma de detectar se um ponto D incide na circunferência de A, B, C é calcular o determinante:[4]
Quando A, B and C estão ordenados em sentido anti-horário, essa determinante é positiva se e somente se apenas D estiver contido na circunferência.
Como mencionado acima, se um triângulo é não-Delaunay, podemos rodar uma de suas arestas. Isso nos conduz a um algoritmo simples: construir qualquer triangulação dos pontos, e depois rodar arestas até que nenhum triângulo seja não-Delaunay. Infelizmente, isto pode levar tempo O(n2), e não se estende para 3 ou mais dimensões.[2]
A forma mais simples e eficiente de computar a triangulação de Delaunay é adicionar um vértice de cada vez, triangulando novamente as partes afetadas do grafo a cada adição. Quando um vértice v é adicionado, dividimos em três o triângulo que o contém, então aplicamos o algoritmo flip. Isso irá levar um tempo da ordem de O(n): procuramos por todos os triângulos para encontrar um que contenha v, então fazemos o flip de cada triângulo. Então o tempo final é da ordem de O(n2).
Se inserirmos vértices em uma ordem aleatória, verifica-se (por uma prova um pouco complicada) que cada inserção irá rodar, em média, apenas O(1) triângulos – embora em alguns casos irá rodar muitas vezes mais.[5] Podemos guardar o histórico das divisões e das rotações realizadas: cada triângulo armazena um ponteiro para os dois ou três triângulos que o substituíram. Para encontrar o triângulo que contém v, começamos por um triângulo raiz, e seguimos o ponteiro que aponta para o triângulo que contém v, até encontrarmos um triângulo que ainda não foi substituído. Em média, isso também levará tempo na ordem de O(n log n).[2] Para dimensões maiores (provado por Edelsbrunner e Shah[6]), o tempo de execução pode ser exponencial na ordem da dimensão, mesmo se a triangulação de Delaunay final for pequena.
O algoritmo Bowyer-Watson provê uma outra aproximação para construção incremental. Isso proporciona uma alternativa a rotação de arestas para computar triângulos de Delaunay contendo um novo vértice inserido.
Um algoritmo de divisão e conquista para triangulações em duas dimensões é um dual de Lee e Schachter que foi aprimorado por Guibas e Stolfi[7] e, mais tarde, por Dwyer. Nesse algoritmo, uma recursão desenha uma linha para separar os vértices em dois conjuntos. A Triangulação de Delaunay é computada para cada conjunto, e depois os dois conjuntos são unidos ao longo da linha separadora. Utilizando-se alguns truques, a operação de junção pode ser feita em tempo O(n), então o total de tempo gasto em execução é da ordem de O(n log n).[8]
Para certos tipos de conjuntos de pontos, como uma distribuição aleatória uniforme, pode-se escolher de forma inteligente as linhas separadoras reduzindo o tempo para até O(n log log n) mantendo o pior caso.
Um paradigma de divisão e conquista para triangulação em d dimensões é apresentado em "DeWall: Um rápido algoritmo de divisão e conquista para Triangulação de Delaunay em Ed" por P. Cignoni, C. Montani, R. Scopigno.[9]
A técnica de divisão e conquista tem se mostrado a mais rápida para a geração de DT.[10][11]
O algoritmo de Fortune utiliza uma técnica de linha de varredura para alcançar complexidade de tempo de O(n log n) em casos planares.
Sweephull[12] é uma rápida técnica híbrida para Triangulações de Delaunay 2D que utiliza uma propagação radial sweep-hull (sequencialmente criado a partir da ordenação radial do conjunto de pontos 2D, gerando uma triangulação sem sobreposição), pareado com o triângulo da última rodada. Resultados empíricos indicam que o algoritmo roda em aproximadamente metade do tempo do Qhull, e implementações gratuitas podem ser encontradas nas linguagens C++ e C#.[13]
A árvore geradora mínima euclidiana de um conjunto de pontos é um subconjunto de triangulações de Delaunay dos mesmos pontos, podendo assim ser explorado para computá-la de forma eficiente. Para modelar terrenos ou outros objetos a partir de uma amostra de pontos, a Triangulação de Delaunay nos dá um bom conjunto de triângulos para utilizar como polígonos no modelo. Em particular, a Triangulação de Delaunay evita triângulos magros (possuem circunferências grandes em comparação com suas áreas). Veja Rede Irregular Triangulada.
Triangulações de Delaunay podem ser utilizadas para determinar a densidade ou a intensidade de amostragens de pontos por meio da DTFE.
Triangulações de Delaunay também são muitas vezes utilizadas para construir diagramas para os espaços discretos, como o método dos elementos finitos e o método do volume finito de simulação de física, razão pela qual os algoritmos de triangulação rápida têm sido desenvolvidos. Normalmente, o domínio a ser transformado em diagramas é especificado como um complexo simplicial e grosso; para o diagrama ser numericamente estável, deve ser refinado utilizando-se o algoritmo de Ruppert algorithm.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.