Triangulació en palmito
En Geometria computacional, la Triangulació en palmito (en anglés, Fan triangulation) és un método senzill per a calcular una triangulació d'un polígon que consistix en elegir un vèrtiç del polígon i traçar totes les diagonals en orige en eixe vèrtiç. No tots els polígons poden ser triangulados per este método, per lo que generalment només és amprat en polígons convexos.[1]
Propietats
[editar | editar còdic]Ademés de les propietats de tota triangulació, les triangulacions en palmito tenen les següents propietats:
- No tots els polígons admeten una triangulació en palmito, encara que és notable que els polígons convexos sempre l'admeten.
- Els polígons en un únic vèrtiç cóncau també l'admeten, sempre que l'únic vèrtiç entrante siga elegit com a orige de les diagonals.
- Per a saber si un polígon genèric admet una triangulació en palmito, és necessari resoldre el Problema de la galeria d'art i verificar que existix a lo manco un vèrtiç que proporcione visibilitat a tot el polígon.
- La triangulació d'un polígon en vèrtiços usa diagonals, i genera triànguls.[2]
- La generació de la llista de triànguls és trivial si es dispon de la llista ordenada dels vèrtiços del polígon, i pot calcular-se en temps llineal. Esta propietat fa que no siga necessari almagasenar de forma explícita la llista de triànguls, per lo que vàries llibreries gràfiques implementen primitives per a representar polígons basats en esta triangulació. En este sentit, OpenGL va introduir la primitiva GL_TRIANGLE_FAN[3] i Direct3D la primitiva D3DPT_TRIANGLEFAN (encara que es va declarar obsoleta a partir de Direct3D 10).[4] Estes primitives són especialment aptes per a pintar elipses i círculs.
- Encara que esta triangulació és apta per a resoldre alguns problemes, com rasterización de polígons o detecció de colisions, pugues no ser-ho para unes atres degut a que el vèrtiç orige acumula una valència (número de veïns) molt alta i els ànguls interns de la triangulació es distribuïxen de forma poc equitativa.
Pseudoalgoritmo
[editar | editar còdic]Per a generar la llista de triànguls d'un polígon de vèrtiços, suponent que l'orige siga el vèrtiç 0, es pot usar el pseudo-algoritme:
Referències i enllaços externs
[editar | editar còdic]- ↑ Loera, Jesús A.; Rambau, {{{nom2}}} (2010). Triangulations: Structures and Algorithms. (en anglés), Springer Science & Business Mija, pp. 103. ISBN 9783642129711.
- ↑ Computational Geometry in C, 2 edició, Cambridge University Press. ISBN 9780521649766.
- ↑ «The OpenGL Graphics System: A Specification». Consultat el 2 de març de 2017.
- ↑ «Deprecated Features (Direct3D 10)». Programming Guide for Direct3D 10. Consultat el 2 de març de 2017.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Triangulación en abanico» 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.