fbpx
Wikipedia

Triangulación de un polígono

En geometría, la triangulación de un polígono o área poligonal es una partición de dicha área en un conjunto de triángulos por un conjunto máximal de diagonales que no se cruzan.[1]

Una triangulación genérica de un polígono cóncavo

Definición

De manera más precisa, una triangulación es una división del área en un conjunto de triángulos que cumplen las siguientes condiciones:

  • La unión de todos los triángulos es igual al polígono original.
  • Los vértices de los triángulos son vértices del polígono original.
  • Cualquier pareja de triángulos es disjunta o comparte únicamente un vértice o un lado.

La definición anterior es la estándar en geometría computacional aunque en ciertos contextos, al hablar de triangulaciones, se puede hacer caso omiso del segundo requisito. En tal caso, no se requiere que los vértices de los triángulos sean vértices del polígono y para referirse a las triangulaciones que sí satisfacen el requisito se habla de triangulaciones completas.[2][3]

La partición de una superficie en triángulos se denomina también malla triangular en trigonometría y en geometría elemental. Y desde el punto de vista de la teoría de grafos, las triangulaciones son «grafos no orientados sin aristas múltiples», cuyos subgrafos son "círculos de tres nodos" (y correspondientemente tres aristas). Una generalización de las mallas triangulares son las mallas poligonales.

Propiedades de las triangulaciones de un polígono

 
Las 42 posibles triangulaciones para un heptágono. Este número viene dado por el número de Catalan.

A continuación se muestran propiedades de la triangulación de un polígono simple:

  • Todo polígono simple admite siempre al menos una triangulación.
  • Toda triangulación de un polígono simple con   vértices consiste en exactamente   triángulos.[1][4]
  • Cada triangulación de un polígono simple de   vértices usa   diagonales.[1][4]
  • Todo polígono convexo de   vértices puede ser triangulado en abanico en   triángulos, escogiendo un vértice y trazando todas las diagonales a vértices no vecinos.
  • De forma similar, todo polígono con un único vértice cóncavo puede ser triangulado en abanico en   triángulos, escogiendo como origen el único vértice cóncavo y trazando las diagonales al resto de vértices.
  • La cantidad total de triangulaciones posibles de un polígono convexo de   vértices es igual al ( )-ésimo número de Catalan, es decir:  , la demostración fue encontrada por Leonhard Euler.[5][6]

Triangulaciones especiales

 
Ejemplos de triangulación de un polígono. 1. Abanico. 2. Mínimo peso 3. Delaunay
 
Triangulación voraz de un polígono ejecutada paso a paso.

Con frecuencia interesa calcular una triangulación que presente alguna propiedad especial, como por ejemplo evitar que algún triángulo tenga un área mayor de un umbral dado.

  • La Triangulación de Delaunay que, entre otras propiedades, maximiza el ángulo mínimo de los triángulos (evitando que aparezcan ángulos demasiado agudos).
  • La Triangulación voraz, que trata de emparejar los vértices más cercanos entre sí.
  • La Triangulación de peso mínimo (Minimum-weight Triangulation), que minimiza la suma total de longitudes de las aristas de los triángulos.
  • La Triangulación en abanico de un polígono convexo, eligiendo un vértice y trazando diagonales a los vértices no vecinos. Esta triangulación puede ser rápidamente calculada en tiempo lineal.

Un polígono monótono puede ser triangulado en tiempo lineal mediante alguno de los algoritmos siguientes:

Aplicaciones

Existen muchas aplicaciones que utilizan la triangulación de un polígono como uno de los pasos para la solución del problema. Por ejemplo:

  • Desde la antigüedad se ha utilizado para calcular el área de parcelas de terreno de forma irregular. El método más habitual es dividir la parcela en triángulos, cuyo cálculo de área es trivial conociendo la longitud de los lados, y sumar las áreas de los mismos. Posteriormente se desarrolló la llamada fórmula del agrimensor, para calcular áreas de terrenos y polígonos en general.
  • El problema de la galería de arte donde se resuelve el problema de visibilidad desde el mínimo número de puntos posible.
  • La deformación de superficies (especialmente tejidos) mediante el método de elementos finitos.

Generalización a dimensiones superiores

 
Descomposición de un cubo en 6 tetraedros, el simplejo de  

La definición de triangulación puede ser fácilmente adaptada para elementos de dimensiones superiores. Así, se define una triangulación de un politopo en un espacio   como un complejo simplicial formado por una colección de simplejos de  tales que:

  • La unión de todos los simplejos es igual al politopo.
  • Los vértices de los simplejos son vértices del polítopo original.
  • Cualquier par de simplejos es disjunto o su intersección es exactamente alguna cara común.

Por ejemplo, en caso del espacio  cualquier volumen encerrado en el interior de una superficie discreta cerrada, puede ser descompuesto en una serie de tetraedros (que es el simplejo de  ). Esto tiene aplicaciones importantes como el cálculo de volúmenes de objetos complejos, o la deformación mediante el método de elementos finitos.

Referencias

  1. de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark. Computational Geometry (3 edición). Springer. ISBN 978-3-540-77973-5. 
  2. Trias Pairó, Joan (2003). «3.9 Triangulación de polígonos simples». Geometría para la informática gráfica y CAD. Vol. 129 de Politext: Matemática y Estadística (1ª edición). Barcelona: Edicions UPC. p. 151. ISBN 9788483017029. Consultado el 25 de noviembre de 2011. 
  3. Hernández Cifre, María Ángeles y José Antonio Pastor González. «6.2.1 Triangulaciones. La característica de Euler-Poincaré». Un curso de geometría diferencial: teoría, problemas, soluciones y prácticas con ordenador. Vol. 47 de Textos universitarios, Consejo Superior de Investigaciones Científicas (España). España: CSIC, Ediciones Doce Calles. p. 232. ISBN 9788400091545. Consultado el 25 de noviembre de 2011. 
  4. O'Rourke, Joseph. Computational Geometry in C (2 edición). Cambridge University Press. ISBN 9780521649766. 
  5. Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
  6. Jesús D. Loera; Jörg Rambau; Francisco Santos (2010). Triangulations:Structures for Algorithms and Applicaciones. Algorithms and Computation in Mathematics (en inglés) 25. Springer. ISBN 9783642129704. 
  7. Fournier, A.; Montuno, D. Y. (1984), «Triangulating simple polygons and equivalent problems», ACM Transactions on Graphics 3 (2): 153-174, ISSN 0730-0301, doi:10.1145/357337.357341 .
  8. Toussaint, Godfried T. (1984). «A new linear algorithm for triangulating monotone polygons». Pattern Recognition Letters 2 (3): 155-158. doi:10.1016/0167-8655(84)90039-4. 
  •   Datos: Q3045660
  •   Multimedia: Polygon triangulation

triangulación, polígono, para, otros, usos, este, término, véase, triangulación, desambiguación, geometría, triangulación, polígono, área, poligonal, partición, dicha, área, conjunto, triángulos, conjunto, máximal, diagonales, cruzan, triangulación, genérica, . Para otros usos de este termino vease Triangulacion desambiguacion En geometria la triangulacion de un poligono o area poligonal es una particion de dicha area en un conjunto de triangulos por un conjunto maximal de diagonales que no se cruzan 1 Una triangulacion generica de un poligono concavo Indice 1 Definicion 2 Propiedades de las triangulaciones de un poligono 3 Triangulaciones especiales 4 Aplicaciones 5 Generalizacion a dimensiones superiores 6 ReferenciasDefinicion EditarDe manera mas precisa una triangulacion es una division del area en un conjunto de triangulos que cumplen las siguientes condiciones La union de todos los triangulos es igual al poligono original Los vertices de los triangulos son vertices del poligono original Cualquier pareja de triangulos es disjunta o comparte unicamente un vertice o un lado La definicion anterior es la estandar en geometria computacional aunque en ciertos contextos al hablar de triangulaciones se puede hacer caso omiso del segundo requisito En tal caso no se requiere que los vertices de los triangulos sean vertices del poligono y para referirse a las triangulaciones que si satisfacen el requisito se habla de triangulaciones completas 2 3 La particion de una superficie en triangulos se denomina tambien malla triangular en trigonometria y en geometria elemental Y desde el punto de vista de la teoria de grafos las triangulaciones son grafos no orientados sin aristas multiples cuyos subgrafos son circulos de tres nodos y correspondientemente tres aristas Una generalizacion de las mallas triangulares son las mallas poligonales Propiedades de las triangulaciones de un poligono Editar Las 42 posibles triangulaciones para un heptagono Este numero viene dado por el numero de Catalan A continuacion se muestran propiedades de la triangulacion de un poligono simple Todo poligono simple admite siempre al menos una triangulacion Toda triangulacion de un poligono simple con n displaystyle n vertices consiste en exactamente n 2 displaystyle n 2 triangulos 1 4 Cada triangulacion de un poligono simple de n displaystyle n vertices usa n 3 displaystyle n 3 diagonales 1 4 Todo poligono convexo de n displaystyle n vertices puede ser triangulado en abanico en n 2 displaystyle n 2 triangulos escogiendo un vertice y trazando todas las diagonales a vertices no vecinos De forma similar todo poligono con un unico vertice concavo puede ser triangulado en abanico en n 2 displaystyle n 2 triangulos escogiendo como origen el unico vertice concavo y trazando las diagonales al resto de vertices La cantidad total de triangulaciones posibles de un poligono convexo de n displaystyle n vertices es igual al n 2 displaystyle n 2 esimo numero de Catalan es decir t n C n 2 1 n 1 2 n 4 n 2 displaystyle t n C n 2 frac 1 n 1 binom 2n 4 n 2 la demostracion fue encontrada por Leonhard Euler 5 6 Triangulaciones especiales Editar Ejemplos de triangulacion de un poligono 1 Abanico 2 Minimo peso 3 Delaunay Triangulacion voraz de un poligono ejecutada paso a paso Con frecuencia interesa calcular una triangulacion que presente alguna propiedad especial como por ejemplo evitar que algun triangulo tenga un area mayor de un umbral dado La Triangulacion de Delaunay que entre otras propiedades maximiza el angulo minimo de los triangulos evitando que aparezcan angulos demasiado agudos La Triangulacion voraz que trata de emparejar los vertices mas cercanos entre si La Triangulacion de peso minimo Minimum weight Triangulation que minimiza la suma total de longitudes de las aristas de los triangulos La Triangulacion en abanico de un poligono convexo eligiendo un vertice y trazando diagonales a los vertices no vecinos Esta triangulacion puede ser rapidamente calculada en tiempo lineal Un poligono monotono puede ser triangulado en tiempo lineal mediante alguno de los algoritmos siguientes Algoritmo de Alain Fournier y D Y Montuno 7 Algoritmo de Godfried Toussaint 8 Aplicaciones EditarExisten muchas aplicaciones que utilizan la triangulacion de un poligono como uno de los pasos para la solucion del problema Por ejemplo Desde la antiguedad se ha utilizado para calcular el area de parcelas de terreno de forma irregular El metodo mas habitual es dividir la parcela en triangulos cuyo calculo de area es trivial conociendo la longitud de los lados y sumar las areas de los mismos Posteriormente se desarrollo la llamada formula del agrimensor para calcular areas de terrenos y poligonos en general El problema de la galeria de arte donde se resuelve el problema de visibilidad desde el minimo numero de puntos posible La deformacion de superficies especialmente tejidos mediante el metodo de elementos finitos Generalizacion a dimensiones superiores Editar Descomposicion de un cubo en 6 tetraedros el simplejo de R 3 displaystyle mathbb R 3 La definicion de triangulacion puede ser facilmente adaptada para elementos de dimensiones superiores Asi se define una triangulacion de un politopo en un espacio R n displaystyle mathbb R n como un complejo simplicial formado por una coleccion de simplejos de R n displaystyle mathbb R n tales que La union de todos los simplejos es igual al politopo Los vertices de los simplejos son vertices del politopo original Cualquier par de simplejos es disjunto o su interseccion es exactamente alguna cara comun Por ejemplo en caso del espacio R 3 displaystyle mathbb R 3 cualquier volumen encerrado en el interior de una superficie discreta cerrada puede ser descompuesto en una serie de tetraedros que es el simplejo de R 3 displaystyle mathbb R 3 Esto tiene aplicaciones importantes como el calculo de volumenes de objetos complejos o la deformacion mediante el metodo de elementos finitos Referencias Editar a b c de Berg Mark Cheong Otfried van Kreveld Marc Overmars Mark Computational Geometry 3 edicion Springer ISBN 978 3 540 77973 5 Trias Pairo Joan 2003 3 9 Triangulacion de poligonos simples Geometria para la informatica grafica y CAD Vol 129 de Politext Matematica y Estadistica 1ª edicion Barcelona Edicions UPC p 151 ISBN 9788483017029 Consultado el 25 de noviembre de 2011 Hernandez Cifre Maria Angeles y Jose Antonio Pastor Gonzalez 6 2 1 Triangulaciones La caracteristica de Euler Poincare Un curso de geometria diferencial teoria problemas soluciones y practicas con ordenador Vol 47 de Textos universitarios Consejo Superior de Investigaciones Cientificas Espana Espana CSIC Ediciones Doce Calles p 232 ISBN 9788400091545 Consultado el 25 de noviembre de 2011 a b O Rourke Joseph Computational Geometry in C 2 edicion Cambridge University Press ISBN 9780521649766 Pickover Clifford A The Math Book Sterling 2009 p 184 Jesus D Loera Jorg Rambau Francisco Santos 2010 Triangulations Structures for Algorithms and Applicaciones Algorithms and Computation in Mathematics en ingles 25 Springer ISBN 9783642129704 Fournier A Montuno D Y 1984 Triangulating simple polygons and equivalent problems ACM Transactions on Graphics 3 2 153 174 ISSN 0730 0301 doi 10 1145 357337 357341 Toussaint Godfried T 1984 A new linear algorithm for triangulating monotone polygons Pattern Recognition Letters 2 3 155 158 doi 10 1016 0167 8655 84 90039 4 fechaacceso requiere url ayuda Datos Q3045660 Multimedia Polygon triangulationObtenido de https es wikipedia org w index php title Triangulacion de un poligono amp oldid 126577089, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos