JUAN CAMILO MUÑOZ CASTELBLANCO
CODIGO: 257120
ESTUDIANTE DE INGENIERIA DE SISTEMAS
DESCRIPCION DEL ALGORITMO DE CONVEXIDAD DE ANDREW PARA DOS DIMENSIONES
Explicación del algoritmo y su complejidad. http://www.ual.es/~fbeltran/envolvente/07.htm
Código del algoritmo de Convex Hull de Andrew´s para dos dimensiones. http://geometryalgorithms.com/Archive/algorithm_0109/algorithm_0109.htm#chainHull_2D()
Algoritmo de Scan de Graham (Wikipedia). http://en.wikipedia.org/wiki/Graham_scan#The_algorithm
Algoritmo de Andrew´s para dos dimensiones
Como se ha visto previamente el algoritmo como entrada recibe una nube de puntos a la cual como salida entrega el mínimo polígono convexo que contiene en su interior la nube de puntos.
Al resolver este algoritmo se tiene en cuenta que se va a resolver en sentido horario, luego se establece un orden de menor a mayor con respecto al eje y, se escoge el menor y el mayor. Entonces dividimos el problema en dos partes, resolver el casco convexo superior y resolver el casco convexo inferior. Luego unimos las soluciones para hallar el polígono convexo.
Para el casco convexo superior, cojemos del punto menor con respecto al eje y vamos hacia los mayores hasta llegar al punto del extremo derecho, teniendo en cuenta los siguientes casos los cuales se hacen iterativamente o como proceso un Scan:
En el tercer caso no importa si no hay punto n-2, ya que queda una línea la cual también es un casco convexo superior valido.
Para el casco convexo inferior, se sigue el mismo proceso, pero cojemos del punto mayor con respecto al eje y vamos hacia los menores hasta llegar al punto del extremo izquierdo, siguiendo los casos de la anterior figura simétricamente.
Complejidad
La complejidad esta dada por varios componentes elementales del código como:
Ordenar los puntos con Heap Sort: O(N.LogN)
Aplicar Scan a la nube de puntos: O(N)
Concatenar los cascos convexos: O(N)
Complejidad total del algoritmo de Andrew´s: O(N.LogN)
Prueba de tiempos:
En un computador Pentium 4, memoria RAM de 512 MB, sistema operativo Windows XP, con el compilador de java abierto (JCreator) y otras aplicaciones abiertas. Generé un conjunto aleatorio de 50.000 puntos, el cual con el timer registro un tiempo de ejecución de 9,518 segundos de lo cual pude estimar un número aproximado de operaciones en un perido de tiempo. En un segundo se pueden procesar 6.476 puntos, en un minuto 272.467 puntos, en 10 minutos 2’326.109 puntos, en una hora 12’519.317 puntos y en un día 253’743.972 puntos.
OTROS:
Lista de los politopos regulares(Wikipedia). http://en.wikipedia.org/wiki/List_of_regular_polytopes
Generación de mayas triangulares(Aplicación de algoritmos de convexidad). http://3dmeshing.tripod.com/indexs.html