Algoritmo de QuickHull para la cerradura convexa

Pues en este post describiré lo relacionado con el algoritmo de QuickHull para encontrar la envolvente convexa de una conjunto de puntos. Evidentemente el esquema será el mismo que se ha venido mostrando a lo largo de todos mis post relacionados con la geometría computacional. Primero que nada, debemos comprender de qué trata este algoritmo, y no hay mejor que mediante el seudocódigo y un ejemplo donde de ponga a prueba su funcionamiento. El algoritmo de QuickHull nos dice lo siguiente:

Entonces, dada una nube de puntos como la de la imágen:

El algoritmo nos dice que como primer paso debemos seleccionar el punto más a la izquierda y el punto más a la derecha, quedándonos algo así:

Luego debemos separar en dos conjuntos, los que están a la derecha del segmento formado por los dos puntos encontrados anteriormente, y los que están a la izquierda. Estos conjuntos recibirán el nombre de S1 y S2 respectivamente.

Agregamos a la cerradura el punto min, los puntos que hallaremos al procesar el conjunto S1, el punto max y por último los puntos que hallaremos al procesar el conjunto S2.

En la pila en donde se almacenan los puntos hay dos elementos que están con un color de fondo determinado, esto es así porque quiero indicar que en estas posiciones se insertarán conjuntos de puntos que serán hallados de manera recursiva, dada la naturaleza del algoritmo.

Ahora procesaremos S1. En esta parte se llamara a la función encargada de procesar el subconjunto de puntosd. Lo que se hace es escoger el punto más lejano de la recta formada por los puntos a y b, que son las entradas para este subprocedimiento. El punto más lejano es el punto 6 y este punto no tiene ningún punto, ni a la derecha ni a la izquierda, tal como indica el seudocódigo mostrado. Entonces el resultado de procesar el subconjunto S1 será el punto 6.

Ahora es el turno del subconjunto S2. El punto más lejano es el punto 2, el cuál al formar el segmento cb no tiene puntos a su derecha, pero si a su derecha (área amarrilla), pero al formar el segmento ac, presenta un punto a su derecha. Algo que rescatar aquí es que el proesamiento de S2 nos devolverá más de un punto. Entonces añadimos el resultado de procesar subconjunto A (región amarilla) a la pila y luego el punto 2.

Ahora, siguiendo el procesamiento anterior, el resultado de procesar la región amarilla nos retornará solo el punto 3 el cuál será añadido a la pila y terminará con la recursivad de este algoritmo al cumplir con la condición de finalización (if noEsVacio(s)), ya que no nos quedan más puntos por procesar.

Utilizando los puntos almacenados en la pila podemos generar la envolvente convexa de nuestra nube de puntos, finalizando con esto todo el proceso.

La implementación del Algoritmo QuickHull es la siguiente:

public static List<Point2D> quickHull(List<Point2D> nube) {
    List<Point2D> cerradura = new ArrayList<Point2D>();
    Point2D min_x = new Point2D.Double(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
    Point2D max_x = new Point2D.Double(Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY);
    for(Point2D aux:nube) {
        if(aux.getX()<min_x.getX()) {
            min_x = aux;
        }
        if(aux.getX()>max_x.getX()) {
            max_x = aux;
        }
    }
    List<Point2D> S1 = puntosLado(min_x, max_x, nube);
    List<Point2D> S2 = puntosLado(max_x, min_x, nube);
    cerradura.add(min_x);
    cerradura.addAll(findHull(min_x, max_x, S1));
    cerradura.add(max_x);
    cerradura.addAll(findHull(max_x, min_x, S2));
    return cerradura;
}

public static List<Point2D> findHull(Point2D a, Point2D b, List<Point2D> S) {
    List<Point2D> cerradura = new ArrayList<Point2D>();
    Point2D c = new Point2D.Double();
    if(!S.isEmpty()) {
        List<Point2D> A = new ArrayList<Point2D>();
        List<Point2D> B = new ArrayList<Point2D>();
        c = puntosMayorArea(a, b, S);
        A = puntosLado(a, c, S);
        B = puntosLado(c, b, S);
        cerradura.addAll(findHull(a, c, A));
        cerradura.add(c);
        cerradura.addAll(findHull(c, b, B));
    }
    return cerradura;    
}

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

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

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