Algoritmo de Jarvis para la Cerradura Convexa

En esta oportunidad vamos a ver el funcionamiento del algoritmo de Jarvis para la cerradura convexa. Veamos de qué trata el algoritmo:

Bueno, el seudocódigo está bastante claro, pero vamos a ver cómo funcionaría con un pequeño conjunto de puntos. Supongamos que tenemos el siguiente conjunto de puntos:

Primero seleccionamos el punto de menor coordenada y lo llamamos p.

Luego escogemos el punto que forma el menor ángulo con la horizontal, al que llamaremos q y agregamos p a la pila que guardará los puntos que forman la cerradura convexa.

Ingresamos al bucle y vamos a empezar a encontrar los puntos que forman la cerradura convexa teniendo como condición que este deberá formar el menor ángulo con la recta que forma los puntos p y q.

En la primera iteración pasaría esto:

El punto 3 es el que forma el menor ángulo por lo que pasará a formar parte de la cerradura convexa. Vayamos a la siguiente iteración.

El siguiente punto ahora es el punto 2. El punto 3 ya pasó a formar parte de la cerradura convexa. Ahora veamos la siguiente iteración.

Vemos que el punto con menor ángulo es el punto de inicio, además la condición de parada nos dice que q!=inicio. Y la siguiente iteración no se ejecutará ya que nos quedará algo como esto:

El bucle se termina y graficamos la cerradura convexa con los puntos almacenados en nuestra pila, quedándonos así:

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

/**
 *
 * @author Rolando
 */
public static List<Point2D> jarvis(List<Point2D> nube) {
    List<Point2D> cerradura = new ArrayList<Point2D>();
    double min = 0,ang = 0;
    //O(n)
    Point2D p = new Point2D.Double();
    Point2D q = new Point2D.Double();
    Point2D pInicio = new Point2D.Double();
    Point2D posMin = new Point2D.Double();
    p = menorCoordenadaY(nube);
    pInicio = p;
    q = calcularMenorAngulo(nube, p);
    cerradura.add(p);
    while(q!=pInicio) {
        cerradura.add(q);
        min=180;
        for(Point2D aux:nube) {
            if(aux!=q) {
                ang=angulo(q,p,aux);
                if(ang<min) {
                    posMin=aux;
                    min=ang;
                }
            }
        }
        p=q;
        q=posMin;
    }
    return cerradura;
}

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

Bueno, espero que les sea de utilidad. Muy pronto postearé el algoritmo de QuickHull. No se olviden de dejar sus comentarios y críticas.

Quizás te pueda interesar también esos posts:
http://rolandopalermo.blogspot.com/2010/09/algoritmo-de-graham-para-la-cerradura.html
http://rolandopalermo.blogspot.com/2010/11/quickhull-java-convex-hull.html