Algoritmo de Graham para la Cerradura Convexa

Bueno, al llegar a este post asumo que ustedes ya han leído acerca de lo que trata este problema de la geometría computacional. Esto es muy importante puesto que algunos detalles expuestos aquí no serán tratados muy profundamente. Pues bueno, vayamos al grano. El algoritmo de graham fué uno de los primero algoritmos utilizados para resolver este problema. El concepto fundamental de este algoritmo es tener en cuenta el sentido de giro que toma un vector respecto a otro de forma iterativa. Para esto Graham nos dice lo siguiente:

Evidentemente es seudocódigo pero no hay mejor forma de entender esto que mediante una prueba. A ver, empezemos. 

Supongamos que se nos da un conjunto de puntos como los que se muestra en la figura siguiente:

Y necesitamos hallar la cerradura convexa. Lo primero que nos dice Graham es que escojamos el punto de menor ordenada y luego ordenemos el resto de puntos en función a su ángulo que forman con la horizontal.

Ahora insertamos en una pila los tres primeros puntos de la nube de puntos(evidentemente ya deben estar ordenados y el punto de menor ordenada es el que ocupa la menor posición). Hecho esto inicializamos un contador en 3 y empezamos las iteraciones.

Para i=3

Los tres puntos generan una vuelta  la izquierda por lo que incrementamos el contador. Entonces nuestro contador quedaría así:

Para i=4

Vemos que forma una vuelta a la derecha por lo que el contador no se incrementará.

Para i=4

Ahora si se generó una vuelta la izquierda entonces nuestro contador se incrementa.

Para i=5

Tenemos otra vuelta a la izquierda y nuestro contador vuelve a incrementarse.

Para i=6

Una vuelta a la derecha. El contador no se incrementará.

Para i=6

Una vuelta a la izquierda, el contador se incrementará. Además estamos viendo como varia el contenido de la pila (la cual almacena los puntos que forman la cerradura convexa).

Para i =7

Una vuelta a la izquierda.

Para i=8

Vuleta a la derecha, contador sin variaciones.

Para i=8

Incrementamos el contador puesto que se generó una vuelta a la izquierda.

Para i=9

Incrementamos el contador.

Para i=10

Una vuelta a la derecha indica que el contador no se incrementará.

Para i=10

Incrementamos el contador.

Para i=11

Esta es la condición de parada por lo que los datos en la pila quedan así:

Entonces con esos puntos construimos la cerradura convexa y nos quedaría algo así:

La implementación del Algoritmo de Graham es la siguiente:

/**
 *
 * @author Rolando
 */
public static List<Point2D> graham(List<Point2D> nube) {
    Stack pila = new Stack();
    List<Point2D> cerradura = new ArrayList<Point2D>();
    List<Point2D> temp = new ArrayList<Point2D>();
    //O(n)
    pivote = nube.get(0);
    for(Point2D p:nube) {
        if(p.getY()<pivote.getY()
                || (p.getY()==pivote.getY() &&
                p.getX()>pivote.getX())) {
            pivote = p;
        }
    }
    //O(nlog n)
    temp = mergerSort(nube);
    pila.push(temp.get(0));
    pila.push(temp.get(1));
    pila.push(temp.get(2));
    int i = 3;
    while(i<(temp.size())) {
        Point2D t = (Point2D) pila.pop();
        if(isLeft((Point2D) pila.peek(), t, temp.get(i))>0) {
            pila.push(t);
            pila.push(temp.get(i));
            i++;
        }
    }
    cerradura = pila.subList(0, pila.size());
    return cerradura;
}

El código fuente completo lo pueden descargar aquí:

Bueno, espero que les sea de utilidad. Muy pronto postearé los otros algoritmos de cerradura convexa. No se olviden de dejar sus comentarios y críticas.

También podría interesarte estos post:

http://rolandopalermo.blogspot.com/2010/11/java-convex-hull-jarvis.html 

http://rolandopalermo.blogspot.com/2010/11/quickhull-java-convex-hull.html