Triangulació de Delaunay
Una triangulació de Delaunay (pronunciat /dəlo'ne/, a voltes escrit fonèticament «Deloné»), és una ret de triànguls conexa i convexa que complix la condició de Delaunay. Esta condició diu que la circumferència circumscrita de cada triàngul de la ret no deu contindre cap vèrtiç d'un atre triàngul. Les triangulacions de Delaunay tenen important rellevància en el camp de la geometria computacional, especialment en gràfics 3D per computadora.
Se li denomina aixina pel matemàtic rus Borís Nikolaevich Delone qui ho va idear en 1934;[1] el mateix Delone va usar la forma francesa del seu llinage, «Delaunay», com a apreciació als seus antecessors francesos.
Condició de Delaunay
[editar | editar còdic]
La condició de Delaunay d'un triàngul establix que la circumferència circumscrita del mateix no deu contindre cap atre vèrtiç de la triangulació en el seu interior, encara que sí s'admeten vèrtiços situats sobre la circumferència.
Es diu que una ret de triànguls és una triangulació de Delaunay si tots els triànguls de la mateixa complixen la condició de Delaunay. És dir, que cada circumferència circumscrita de cada triàngul no conté vèrtiços de la triangulació en el seu interior. Esta definició original para espais bidimensionales es pot ampliar a espais tridimensionals o inclús dimensions superiors, usant l'esfera circumscrita en lloc de la circumferència circumscrita.
Propietats de la triangulació de Delaunay
[editar | editar còdic]
Les triangulació de Delaunay d'un conjunt de punts complix les següents propietats:
- La frontera externa de triangulació forma l'envolvente convexa del conjunt de punts.
- L'àngul mínim dins de tots els triànguls està maximizar, és dir, s'evita obtindre resultats en ànguls massa aguts.
- Com a conseqüència de lo anterior, els triànguls generats en una triangulació de Delaunay tendixen a ser lo més equiláteros possible. Açò es deu a que tot triàngul no equilátero sempre té algun àngul menor que 60°.
- La triangulació de Delaunay és unívoca llevat en casos a on els vèrtiços presenten una alliniació perfecta. Per eixemple, en cas dels vèrtiços estiguen situats en una reixeta equidistant, o siguen vèrtiços d'un polígon regular. En estos casos, apareixeran circumferències circumscrita en més que tres vèrtiços i serà necessari decidir entre vàries possibles decisions.
- El grafo de Gabriel és un subgrafo de les arestes de la triangulació de Delaunay. És dir, totes les arestes del grafo de Gabriel pertanyen a algun triàngul de la triangulació.
- El grafo del veí més propenc és un subgrafo de les arestes de la triangulació de Delaunay. És dir, totes les arestes del grafo del veí més propenc pertanyen a algun triàngul de la triangulació.
- Com a conseqüència de lo anterior, cada punt del conjunt d'entrada tindrà una aresta que ho unix en el seu punt més propenc.
- La triangulació de Delaunay i el diagrama de Voronoi d'una série de punts són grafos duals, per lo que la construcció d'un és trivial a partir de l'atre. En este sentit, els circumcentres dels triànguls de Delaunay coincidixen en els vèrtiços de les regions del diagrama de Voronoi. Dos vèrtiços del diagrama de Voronoi estaran conectats si els seus triànguls de Delaunay corresponents són veïns entre sí.
- En un grafo construït a partir de les arestes de la triangulació de Delaunay, el camí més curt entre dos punts mai serà major que voltes la distància euclídea entre ells.
La propietat de la triangulació de Delaunay d'maximizar els ànguls interiors dels triànguls és especialment pràctica en geometria computacional perque evita errors de grosseig que poden aparéixer en realisar càlculs en triangulacions arbitràries a on poden aparéixer ànguls massa menuts.
Referències
[editar | editar còdic]- ↑ B. Delaunay: Sur la sphere vide. A la mémoire de Georges Voronoi. Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk (Bulletin of Academy of Sciences of the USSR), 7, págs. 793-800, 1934
- Este artícul conté una traducció derivada de «Triangulación de Delaunay» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.