Aspectos Generales

Antes de empezar a utilizar los algoritmos propuestos en el applet se deben introducir los puntos sobre los que se desea trabajar.

Existen tres opciones:

• Podemos ir metiendo uno a uno todos los puntos en la ventana del applet. El órden en el que se introduzcan no tiene relevancia ya que antes de ejecutar los algoritmos se ordenarán convenientemente. Los puntos se introducen haciendo click con el botón izquierdo del ratón sobre la propia ventana del applet. Se ha implementado la opción de poder meter puntos alineados automáticamente. Esta acción se realiza con el botón derecho del ratón. Al pulsar el botón se pone un nuevo punto en pantalla alineado con el último punto puesto. Está diseñado para que según la posición del ratón, alinee este nuevo punto vertcalmente u horizontalmente.
  
  
• La segunda opción es generar los puntos aleatoriamente. Para conseguir esto debemos introducir en primer lugar la cantidad de puntos que queremos meter como banco de pruebas en la cajita de texto.En segundo lugar se debe pulsar en el botón "Puntos Aleatorios". Con esto se consigue generar una nube de puntos que en principio no tiene límites de tamaño, aunque si es demasiado grande lo resultados no serán de mucha utilidad. Hay que destacar que cada vez que metemos nuevos puntos aleatorios se borran todos los anteriores y se genera un nuevo conjuntos de puntos aleatorios.
  
  
• La tercera y ultima opción consiste en ir creando puntos según se va moviendo el ratón sobre la ventana sin pulsar ningún botón. Para conseguir esto primero se debe seleccionar el checkbox que dice "Seguimiento". Tras esto debemos seleccionar la densidad que queremos que tenga la curva de puntos con la barra de desplazamiento "Densidad". Cuanto más a la derecha está la barra de desplazamiento, más puntos se pondrán según movemos el ratón.
  Tras esto, se puede dibujar la curva. Para indicar donde se quiere que empiece la curva haremos un sólo click sobre la ventana. A continuación se puede mover libremente el ratón, mientras se van dibujando puntos por donde éste pasa, según la densidad seleccionada. Para indicar que queremos terminar de dibujar la curva, haremos click nuevamente sobre la ventana.

Triangulación de Graham

Esta triangulación se basa en el algoritmo del Cierre Convexo de Grham. Se trata de un algoritmo lineal que, con una pequeña modificación permite sacar una triangulación de puntos en complejidad O(n). La triangulación ordena en primer lugar todos los puntos angularmente, respecto al punto que esté más abajo y más a la derecha. Desde ahí empieza la triangulación.

Dada la baja complejidad de este algoritmo se puede probar con un alto número de puntos para comprobar que es muy ligero. Sin embargo, la triangulación resultante es muy poco representativa de los datos, exceptuando el área, perímetro o cierre convexo. A pesar de esto, se ha usado esta triangulación, ya que gracias a ella se puede llegar a la triangulación de Delaunay, flipando aristas. Es entonces una herramienta muy ligera de apoyo para otros algoritmos más complejos como son los que más abajo se explican.

Triangulación de Delaunay

Delaunay parte de la Triangulación de Graham. Sobre esta, se recorre todas las aristas comprobando si se pueden flipar. Dada un arista que separa dos triangulos, fliparla, consiste en cambiar sus puntos por los otros dos que estuviesen libres.

• No siempre se puede realizar esta acción. En los casos en los que las aristas no comunes de los dos triángulos no formen un polígono convexo, no se podrá flipar su arista común.
  
  
• Además, no siempre se debe flipar una arista que se pueda flipar. Se debe comprobar que mejore el vector de ángulos de la triangulación, consiguiendo así unos triángulos más homogéneos.

Diagrama de Voronoi

El Diagrama de Voronoi es el Grafo Dual de la Triangulación de Delaunay y representa las áreas en las que se está más cerca de un punto. Esto se consigue uniendo los circuncentros de los triángulos de Delaunay. Para los triángulos que contengan una arista del cierre convexo, se traza una recta que una su circuncentro con el punto medio de dicha arista y se prolonga hasta el infinito.

Crust - Reconstrucción de Curvas -

El algoritmo de Crust trata de resolver la reconstrucción de curvas definidas por un conjunto de puntos.

• En primer lugar, se obtiene la triangulación de Delaunay asociada a los puntos dados.
  
• A ese conjunto de puntos se le añaden todos los circuncentros de la triangulación de Delaunay.
  
• Se calcula una nueva triangulación de Delaunay sobre este conjunto de puntos.
  
• Las aristas finales del algortmo de Crust serán aquellas que no tengan ningún punto de los que fueron añadidos al calcular los circuncentros.

AntiCrust - Esqueleto -

AntiCrust, al igual que pasaba entre Voronoi y Delaunay, es el grafo dual de Crust, y representa el esqueleto de la "figura" o "curva". Si por ejemplo la nube de puntos representase una hoja, el anticrust sería en gran medida el esqueleto de esa hoja.

El AntiCrust se calcula basándose en Crust y en el Diagrama de Voronoi. El esqueleto son todas aquellas aristas que pertenezcan al Diagrama de Voronoi y que no corten a ninguna arista de Crust.
Si se dispone de Crust y del Diagrama de Voronoi, el cálculo del AntiCrust es directo.

Aspectos generales de los Algoritmos

En el applet, hay que destacar la relación que mantienen los distintos algoritmos, ya que es la base a la hora de optimizar trabajo. En todos los casos, a la hora de ejecutar cualquier algoritmo, se utilizará todo lo que previemente se hubiese calculado. Es decir, que si primero calculamos el Crust de los puntos dados, la Triangulación de Graham y la de Delaunay ya estarán calculadas, con lo que si más tarde se quiere ver la Triangulación de Delaunay, no hay que volver a calcularla. Así ocurre entre todos los algoritmos.
El caso más extremo es que calculemos en primer lugar AntiCrust. Si esto ocurre, ha sido necesario calcular las Triangulaciones de Graham, de Delaunay, el diagrama de Voronoi y Crust. Con esto, si más tarde queremos ver cualquiera de estos algoritmos no hay que calcularlos.