Mostrar código-fonte de Triangulação de Delaunay

{{Reciclagem|data=novembro de 2011}}
[[Ficheiro:Delaunay_circumcircles_vectorial.svg|right|thumb|280px|Triangulação de Delaunay no plano com  as circunferências visiveis]]
Em [[matemática]], uma '''Triangulação de Delaunay''' para um conjunto de pontos '''P''' no plano é uma [[triangulação (geometria)|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.<ref name="Delaunay1934">B. Delaunay: ''Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793&ndash;800, 1934''</ref>
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.

== Relação com o Diagrama de Voronoi ==
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.
<gallery>
Image:Delaunay_circumcircles_centers.png| A Triangulação de Delaunay com todas as circunferências e seus centros (em vermelho).
Image:Delaunay_Voronoi.png| Conectando-se os centros das circunferências produz-se o Diagrama de Voronoi (em vermelho).
</gallery>

== Delaunay ''d''-dimensional ==
Para um conjunto '''P''' de pontos no (''d''-dimensional) [[espaço Euclidiano]], a '''Triangulação de Delaunay''' é uma [[Triangulação (geometria)|triangulação]] DT('''P''') onde nenhum ponto em '''P''' está contido dentro do [[circumcírculo| circum-hiperesfera]] de um [[simplexo]] em DT('''P''').  Sabe-se <ref name="deBerg"/> que existe uma única triangulação de Delaunay para '''P''', se '''P''' é um conjunto de pontos em ''[[posição geral]]''; Isto é, não existe [[flat (geometry)|''k''-flat]] contendo ''k''&nbsp;+&nbsp;2 pontos nem uma [[n-sphere|''k''-esfera]] contendo ''k''&nbsp;+&nbsp;3 pontos, para 1&nbsp;≤&nbsp;''k''&nbsp;≤&nbsp;''d''&nbsp;&minus;&nbsp;1 (isto é, para um conjunto de pontos no <big>ℝ</big><sup>3</sup> 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''&nbsp;+&nbsp;1)-dimensional, pela adição de uma coordenada extra a cada ponto ''p'' igual a |''p''|<sup>2</sup>, 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 [[simplexo]]s. Faces não simpliciais ocorrem somente quando ''d''&nbsp;+&nbsp;2 dos pontos originais incidem em uma mesma  ''d''-[[hiperesfera]], isto é, se os pontos não estão em posição geral.
==Propriedades==
Suponha que ''n'' seja o número de pontos e d o número de dimensões:
* A união de todos os simplexos da triangulação é o fecho convexo dos pontos.
*A Triangulação de Delaunay contém ''O''(''n''<sup>⌈''d''&nbsp;/&nbsp;2⌉</sup>) simplexos.<ref>{{citar periódico
  |último = Seidel
  |primeiro = R.
  |título= The upper bound theorem for polytopes: an easy proof of its asymptotic version
  |periódico= Computational Geometry
  | volume = 5
  |páginas= 115–116
  |ano= 1995
  | url = http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYS-3YVD096-C&_user=108429&_coverDate=09%2F30%2F1995&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_acct=C000059713&_version=1&_urlVersion=0&_userid=108429&md5=70a4159a39ed8ab2c6709025aa77d5de&searchtype=a
  | doi = 10.1016/0925-7721(95)00013-Y
  |número= 2 }}</ref>
*No plano (''d'' = 2), se existem ''b'' vértices fecho convexo, então qualquer triangulação dos pontos tem no máximo 2''n''&nbsp;&minus;&nbsp;2&nbsp;&minus;&nbsp;''b'' triângulos, mais uma face exterior (veja [[Características de Euler]]).
* No plano, cada vértice tem em média seis triângulos em sua volta.
* No plano, a triangulação de Delaunay maximiza o menor ângulo. Comparada com qualquer outra triangulação de pontos, o menor ângulo na triangulação de Delaunay é pelo menos maior do que o menor ângulo em qualquer outra triangulação. Contudo, a triangulação de Delaunay não necessariamente minimiza o maior ângulo.
*Um círculo circunscrevendo qualquer triângulo Delaunay não contém qualquer outro ponto (ou conjunto de pontos) em seu interior.
*Se um círculo passando entre dois pontos da entrada de pontos não contém nenhum outro deles em seu interior, então o segmento que conecta os dois pontos é uma aresta da triangulação de Delaunay, para os pontos dados.
* A triangulação de Delaunay de um conjunto de pontos em um espaço d-dimensional é a projeção dos pontos do [[fecho convexo]] em um [[parabolóide]] (''d''&nbsp;+&nbsp;1)-dimensional.
* O [[vizinho mais próximo]] ''b'' de qualquer ponto ''p'' está na aresta ''bp'' da triangulação de Delaunay desde que o [[grafo do vizinho mais próximo]] seja um subgrafo da triangulação de Delaunay.

== Definição Visual Delaunay: Flipping==
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:
<gallery>
  Image:Delaunay_geometry.png| Esta triangulação não satisfaz a condição de Delaunay (a soma de α e γ é maior que 180°).
  Image:Delaunay_before_flip.png| Esta triangulação não satisfaz a condição de Delaunay (as circunferências contém mais de 3 pontos).
 Image:Delaunay_after_flip.png|Aplicando ''Flipping'' na aresta comum produz-se uma triangulação de Delaunay para os quatro pontos.
</gallery>

==Algoritmos==
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]]:<ref>{{citar web|autor =Guibas, Lenoidas |coautor= Stolfi, Jorge |url = http://portal.acm.org/citation.cfm?id=282923 |título= Primitives for the manipulation of general subdivisions and the computation of Voronoi|publicado= ACM |página=107 |data= 1985-04-01|acessodata= 2009-08-01}}</ref>

: <math>\begin{vmatrix}
A_x & A_y, & A_x^2 + A_y^2, & 1\\[6pt]
B_x & B_y, & B_x^2 + B_y^2, & 1\\[6pt]
C_x & C_y, & C_x^2 + C_y^2, & 1\\[6pt]
D_x & D_y, & D_x^2 + D_y^2, & 1
\end{vmatrix} = \begin{vmatrix}
A_x - D_x, & A_y - D_y, & (A_x^2 - D_x^2) + (A_y^2 - D_y^2) \\[6pt]
B_x - D_x, & B_y - D_y, & (B_x^2 - D_x^2) + (B_y^2 - D_y^2) \\[6pt]
C_x - D_x, & C_y - D_y, & (C_x^2 - D_x^2) + (C_y^2 - D_y^2) \\[6pt]
\end{vmatrix} > 0
</math>

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.

===Algoritmo Flip ===
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(''n''<sup>2</sup>), e não se estende para 3 ou mais dimensões.<ref name="deBerg">{{citar livro
|último = de Berg
|primeiro = Mark
|autorlink = 
|coautor= [[Otfried Cheong]], [[Marc van Kreveld]], [[Mark Overmars]]
|título= Computational Geometry: Algorithms and Applications
|publicado= Springer-Verlag
|ano= 2008
| id = 
| url = http://www.cs.uu.nl/geobook/interpolation.pdf
| isbn = 978-3-540-77973-5
}}</ref>

===Incremental===
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(''n''<sup>2</sup>).

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  &ndash; embora em alguns casos irá rodar muitas vezes mais.<ref>{{citar periódico
  |último= Guibas
  |primeiro= L.
  |coautor= D. Knuth; M. Sharir
  |título= Randomized incremental construction of Delaunay and Voronoi diagrams
  |periódico= Algorithmica
  |volume= 7
  |páginas= 381–413
  |ano= 1992
  |url= http://www.springerlink.com/content/p8377h68j82l6860
  |doi= 10.1007/BF01758770
  }}{{Ligação inativa|data=abril de 2023 }}</ref>
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'').<ref name="deBerg"/>  Para dimensões maiores (provado por Edelsbrunner e Shah<ref>{{citar periódico
  |último= Edelsbrunner
  |primeiro= Herbert
  |autorlink= Herbert Edelsbrunner
  |coautor= Nimish Shah
  |título= Incremental Topological Flipping Works for Regular Triangulations
  |periódico= Algorithmica
  |volume= 15
  |páginas= 223–241
  |ano= 1996
  |url= http://www.springerlink.com/content/4gdja72vx1qmg44x/?p=a74909a339d9498cbff326f08b084b4c&pi=1
  |doi= 10.1007/BF01975867
  |número= 3
  }}{{Ligação inativa|data=abril de 2023 }}</ref>), 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.

===Divisão e Conquista===
Um [[algoritmo de divisão e conquista]] para triangulações em duas dimensões é um dual de Lee e Schachter que foi aprimorado por [[Leonidas J. Guibas|Guibas]] e [[Jorge Stolfi|Stolfi]]<ref>{{Citar web |url=http://www.geom.uiuc.edu/~samuelp/del_project.html |titulo=Computing Constrained Delaunay Triangulations |acessodata=2011-11-13 |arquivodata=2017-09-22 |arquivourl=https://web.archive.org/web/20170922181219/http://www.geom.uiuc.edu/~samuelp/del_project.html }}</ref> 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''&nbsp;log&nbsp;''n'').<ref name="Leach1992">G. Leach: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.2323&rep=rep1&type=pdf ''Improving Worst-Case Optimal Delaunay Triangulation Algorithms.''] June 1992</ref>

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''&nbsp;log&nbsp;log&nbsp;''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 E<sup>''d''</sup>" por P. Cignoni, C. Montani, R. Scopigno.<ref>{{citar periódico|último = Cignoni |primeiro = P. |coautor= C. Montani; R. Scopigno |ano= 1998 |título= DeWall: A fast divide and conquer Delaunay triangulation algorithm in E<sup>d</sup> |periódico= Computer-Aided Design | volume = 30 |número= 5 |páginas= 333–341 | doi = 10.1016/S0010-4485(97)00082-1 }}</ref>

A técnica de divisão e conquista tem se mostrado a mais rápida para a geração de DT.<ref>A Comparison of Sequential Delaunay Triangulation Algorithms http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf</ref><ref>http://www.cs.cmu.edu/~quake/tripaper/triangle2.html</ref>

===Linha de Varredura===
[[O algoritmo de Fortune]] utiliza uma técnica de [[linha de varredura]] para alcançar complexidade de tempo de O(''n''&nbsp;log&nbsp;''n'') em casos planares.

===Sweephull===

Sweephull<ref>[http://www.s-hull.org/paper/s_hull.pdf S-hull]</ref> é 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#.<ref>[http://www.s-hull.org/ http://www.s-hull.org/]</ref>

== Aplicações ==
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 [[Delaunay tessellation field estimator| DTFE]].
[[Imagem:Delaunay Triangulation (100 Points).svg|right|thumb|250px|Triangulação de Delaunay de um conjunto de 100 pontos aleatórios no plano.]]
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]].

== Ver também ==
* [[Esqueleto Beta]]
* [[Triangulação de Delaunay restrita]]
* [[Grafo de Gabriel]]
* [[Análise de padrões de gradientes]]
* [[Triangulação de Pitteway]]
* [[Grafo de Urquhart]]
* [[Diagrama de Voronoi]]

== Referências ==
{{reflist}}

==Ligações externas==
*Delaunay triangulation in [[CGAL]], the Computational Geometry Algorithms Library:
**{{citar web
|último = Yvinec |primeiro = Mariette
|título= 2D Triangulation
|url = http://www.cgal.org/Pkg/Triangulation2
|acessodata=1 de abril de 2010
}}
**{{citar web
|último1 = Pion |primeiro1 = Sylvain
|último2 = Teillaud |primeiro2 = Monique
|título= 3D Triangulations
|url = http://www.cgal.org/Pkg/Triangulation3
|acessodata=1 de abril de 2010
}}
**{{citar web
|último1 = Hert |primeiro = Susan
|último2 = Seel |primeiro2 = Michael
|título= dD Convex Hulls and Delaunay Triangulations
|url = http://www.cgal.org/Pkg/ConvexHullD
|acessodata=1 de abril de 2010
}}
*{{citar web
|título= Delaunay triangulation
|publicado= Wolfram MathWorld
|url = http://mathworld.wolfram.com/DelaunayTriangulation.html
|acessodata=1 de abril de 2010
}}
*{{citar web
|título= Qhull
|url = http://www.qhull.org
|acessodata=1 de abril de 2010
}} &mdash; Code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection
*{{citar web
|último = Shewchuk |primeiro = Jonathan Richard
|título= Triangle
|url = http://www.cs.cmu.edu/~quake/triangle.html
|acessodata=1 de abril de 2010
}} &ndash; A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator
*{{citar web
|último1 = Kumar |primeiro1 = Piyush
|último2 = Mohanty |primeiro2 = Somya
|título= Triangle++
|url = http://www.compgeom.com/~piyush/scripts/triangle/
}} &ndash; A C++ wrapper on Triangle
*{{citar web
|título= Poly2Tri
|url = http://code.google.com/p/poly2tri/
|publicado= Google Code
|acessodata=1 de abril de 2010
}} &ndash; A sweepline Constrained Delaunay Triangulation (CDT) library, available in ActionScript 3, C, C++, C#, Go, Java, [[JavaScript|Javascript]], Python and Ruby

{{DEFAULTSORT:Triangulacao de Delaunay}}
[[Categoria:Geometria discreta]]
[[Categoria:Algoritmos geométricos]]
[[Categoria:Triângulos|Delaunay]]
[[Categoria:Teoria dos grafos]]