El Algoritmo de Triangulación Voraz es un método para calcular una triangulación de un polígono o de una nube de puntos mediante un método voraz, que consiste en añadir aristas a la solución de una en una uniendo el par de vértices más próximos entre sí, con la condición de que una nueva arista no puede cortar a otra previamente añadida al resultado. [1][2]
Algoritmo de Triangulación Voraz
Triangulación del interior de un polígono paso a paso mediante el algoritmo voraz que escoge la diagonal más corta.
Las triangulaciones calculadas mediante el algoritmo de triangulación voraz tienen las siguientes propiedades:
Son una buena aproximación de la triangulación de peso mínimo de un polígono o nube de puntos, aunque no siempre coinciden.
Frecuentemente, aunque no siempre, suelen coincidir con la triangulación de Delaunay de los mismos datos de entrada.
Si la entrada es una nube de puntos, todas las aristas del cierre convexo pertenecen a la triangulación voraz.
Si la entrada es un polígono, las aristas de la triangulación son un subconjunto de las diagonales internas del polígono.
La implementación por fuerza bruta del algoritmo es de orden para un conjunto de entrada de puntos.[3]
Existen implementaciones capaces de calcular la triangulación voraz en tiempo empleando estructuras adicionales para comprobar los cruces entre aristas.[2]
La triangulación voraz puede calcularse a partir de la triangulación de Delaunay añadiendo una cantidad de tiempo lineal.[4]
Pseudoalgoritmo
Existen varias posibles estrategias para implementar el algoritmo de triangulación voraz. Tal vez, la más sencilla de todas sea la siguiente:
Algoritmo triangulación voraz
1 Crear un solución inicial con las aristas del polígono de entrada (o vacía, en caso de nubes de puntos)
2 Crear una lista de aristas candidatas, combinando todos los vértices de entrada dos a dos.
3 Ordenar la lista de candidatas anterior de menor a mayor longitud de arista.
4 Mientras la lista de candidatas no sea vacía.
4.1 Obtener la primera arista de la lista (la más corta) y borrarla de la lista de candidatas.
4.2 Si la arista candidata no se cruza con ninguna otra de la triangulación, insertarla en la triangulación.
Sin embargo, existen soluciones alternativas que pueden acelerar mucho la construcción en caso de que la entrada tenga un tamaño considerable.[2] Especialmente si el número de vértices en la entrada es grande, se debería evitar la comparación de todos los vértices de entrada dos a dos, ya que es un problema de orden . Para ello debería emplearse alguna versión eficiente del Problema del par de puntos más cercanos (que puede resolverse en tiempo ),[5][6] o bien emplear una triangulación de Delaunay como paso intermedio.[4]
Referencias
Loera, Jesús A.; Rambau, Joerg; Santos, Francisco (2010). Triangulations: Structures and Algorithms.(en inglés). Springer Science & Business Media. pp. 103. ISBN9783642129711. Consultado el 21 de febrero de 2017. (requiere registro).
↑ Dickerson, Matthew T. (1997). «Fast greedy triangulation algorithms». Computational Geometry (Elsevier) 8 (2): 67-86. Consultado el 21 de febrero de 2017.
Debido a que existen aristas candidatas iniciales, que deben ser comprobadas.
↑ Levcopoulos, Christos (1999). «The greedy triangulation can be computed from the Delaunay triangulation in linear time». Computational Geometry (Elsevier) 14 (4): 197-220. Consultado el 21 de febrero de 2017.
algoritmo, triangulación, voraz, algoritmo, triangulación, voraz, método, para, calcular, triangulación, polígono, nube, puntos, mediante, método, voraz, consiste, añadir, aristas, solución, uniendo, vértices, más, próximos, entre, condición, nueva, arista, pu. El Algoritmo de Triangulacion Voraz es un metodo para calcular una triangulacion de un poligono o de una nube de puntos mediante un metodo voraz que consiste en anadir aristas a la solucion de una en una uniendo el par de vertices mas proximos entre si con la condicion de que una nueva arista no puede cortar a otra previamente anadida al resultado 1 2 Algoritmo de Triangulacion VorazTriangulacion del interior de un poligono paso a paso mediante el algoritmo voraz que escoge la diagonal mas corta TipoAlgoritmo vorazProblema que resuelveTriangulacion de un poligonoEstructura de datosCola de prioridadesClase de complejidadPTiempo de ejecucionPeor casoO n log n displaystyle O n cdot log n Mejor casoO n displaystyle O n editar datos en Wikidata Propiedades EditarLas triangulaciones calculadas mediante el algoritmo de triangulacion voraz tienen las siguientes propiedades Son una buena aproximacion de la triangulacion de peso minimo de un poligono o nube de puntos aunque no siempre coinciden Frecuentemente aunque no siempre suelen coincidir con la triangulacion de Delaunay de los mismos datos de entrada Si la entrada es una nube de puntos todas las aristas del cierre convexo pertenecen a la triangulacion voraz Si la entrada es un poligono las aristas de la triangulacion son un subconjunto de las diagonales internas del poligono La implementacion por fuerza bruta del algoritmo es de orden O N 2 displaystyle O N 2 para un conjunto de entrada de N displaystyle N puntos 3 Existen implementaciones capaces de calcular la triangulacion voraz en tiempo O n log n displaystyle O n cdot log n empleando estructuras adicionales para comprobar los cruces entre aristas 2 La triangulacion voraz puede calcularse a partir de la triangulacion de Delaunay anadiendo una cantidad de tiempo lineal 4 Pseudoalgoritmo EditarExisten varias posibles estrategias para implementar el algoritmo de triangulacion voraz Tal vez la mas sencilla de todas sea la siguiente Algoritmo triangulacion voraz1 Crear un solucion inicial con las aristas del poligono de entrada o vacia en caso de nubes de puntos 2 Crear una lista de aristas candidatas combinando todos los vertices de entrada dos a dos 3 Ordenar la lista de candidatas anterior de menor a mayor longitud de arista 4 Mientras la lista de candidatas no sea vacia 4 1 Obtener la primera arista de la lista la mas corta y borrarla de la lista de candidatas 4 2 Si la arista candidata no se cruza con ninguna otra de la triangulacion insertarla en la triangulacion dd Sin embargo existen soluciones alternativas que pueden acelerar mucho la construccion en caso de que la entrada tenga un tamano considerable 2 Especialmente si el numero de vertices en la entrada es grande se deberia evitar la comparacion de todos los vertices de entrada dos a dos ya que es un problema de orden n 2 displaystyle n 2 Para ello deberia emplearse alguna version eficiente del Problema del par de puntos mas cercanos que puede resolverse en tiempo n log n displaystyle n cdot log n 5 6 o bien emplear una triangulacion de Delaunay como paso intermedio 4 Referencias Editar Loera Jesus A Rambau Joerg Santos Francisco 2010 Triangulations Structures and Algorithms en ingles Springer Science amp Business Media pp 103 ISBN 9783642129711 Consultado el 21 de febrero de 2017 requiere registro a b c Dickerson Matthew T 1997 Fast greedy triangulation algorithms Computational Geometry Elsevier 8 2 67 86 Consultado el 21 de febrero de 2017 Debido a que existen N N 1 2 displaystyle N N 1 over 2 aristas candidatas iniciales que deben ser comprobadas a b Levcopoulos Christos 1999 The greedy triangulation can be computed from the Delaunay triangulation in linear time Computational Geometry Elsevier 14 4 197 220 Consultado el 21 de febrero de 2017 Thomas H Cormen Charles E Leiserson Ronald L Rivest and Clifford Stein Introduction to Algorithms Second Edition MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Pages 957 961 of section 33 4 Finding the closest pair of points UCSB Lecture Notes Datos Q28811699 Multimedia Greedy TriangulationObtenido de https es wikipedia org w index php title Algoritmo de triangulacion voraz amp oldid 130012378, wikipedia, wiki, leyendo, leer, libro, biblioteca,
