Analisis y diseño de algoritmos

Trabajo Final de Análisis y Diseño de  Algoritmos II
Generador de Mallas Triangulares
Torres, Cristian Luis  y Wilgenhoff, Cristian Pedro  { christianqw, cristian.wil88 }@gmail.com

9 de junio, 2009

Sumario El   presente   trabajo   fue   desarrollado   como   Trabajo   Final   para   la   cátedra   de  Análisis y Diseño de Algoritmos II de la Facultad de Ciencias Exactas de Tandil. Se   documenta la información recolectada antes y durante el desarrollo del mismo. Se   presenta   una   herramienta   que   posibilita,   mediante   la   aplicación   de   algoritmos,   generar   mallas   que   reconstruyen   la   superficie   de   terrenos   basándose   en   puntos, En particular como dominio de prueba se utilizaron puntos batimentos con el  fin de generar los lechos acuáticos que corresponden a las muestras.

Coordinador del Proyecto: Ing. Virginia Cifuentes.

1

Índice de contenido 1  Introducción......................................................................................................................3 2  Descripción del Problema.................................................................................................42.1  Conceptos Básicos................................................................................................................4 2.1.1  Polígono convexo...........................................................................................................4 2.1.2  Cierre Convexo..............................................................................................................52.1.3  Figuras Geométricas....................................................................................................5 2.1.4  Orientación...................................................................................................................5 2.1.5  Circulo Circunscrito.....................................................................................................62.1.6  Determinante de Área Signada...................................................................................6 2.2  Descripción de la problemática...........................................................................................7 3.1  Mallas Geométricas.............................................................................................................93.2  Triangulación de una nube de Puntos..............................................................................10 4.1  Propiedades........................................................................................................................11 4.2  Algoritmos de Delaunay....................................................................................................124.2.1  Algoritmo de Fuerza Bruta........................................................................................13 4.2.2  Algoritmo de Flipping Incremental...........................................................................13 4.2.3  Algoritmo de Subdivisión del terreno. (Divide y Conquista).....................................14 4.2.4  Algoritmo Incremental de Inserción de Puntos.........................................................154.2.5  Otras Alternativas y variaciones...............................................................................15

3  Geometría Computacional...............................................................................................9

4  Triangulación Delaunay................................................................................................115  Estructuras de Almacenamiento de Datos....................................................................16
5.1  Descripción de las Estructuras Implementadas................................................................16 5.2  Estructuras Alternativas. .................................................................................................18...