domingo, 21 de noviembre de 2010

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.


Evidentemente todo esto debe ser contrastado con un modelo que permita certificar que todo lo expuesto anteriormente es cierto y bueno, aquí les dejo una simulación que, de manera interactiva, les permitirá verificar que el algoritmo funciona.



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í:

Photobucket

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

7 comentarios:

Anónimo dijo...

Me regusta, buen post amigo justo lo necesitaba :)

M4rK5 dijo...

Holas doc muy bueno tu post , pero tu forma de sacar la distancia de un punto cualquiera a la recta ab falla U_u pobre con una pequeña base de datos y es erroneo tu resultado, si lo modificas con esta forma te saldra http://www.ahristov.com/tutoriales/geometry-games/point-line-distance.html

Rolando dijo...

Gracias por la aclaración, lo tendré en cuenta. Espero el post te haya sido de utilidad.

Jorge Valverde Rebaza dijo...

Buena explicación rolando, buen post en general, saludos y felicitaciones, sigue trabajndo en el blog que cada día se pone mejor

Anónimo dijo...

Gracias rolando: un beso desde méxico me ayudaste muchísimo

Anónimo dijo...

yo tengo este algoritmo, hecho con interfaz muy bueno.si alguien lo kiere q me lo pida este es mi correo luispg2000@hotmail.com que gustoso se lo dare. nos vemos bye

Anónimo dijo...

Hola, muy interesante el tema, mismo que creo me pueden ayudar a resolver un problema que tengo: Estoy trabajando con un archivo shape de poligonos de predios, requiero de calcular el centroide de cada uno y que siempre caiga dentro del polígono, esto sin usar software comercial, he visto algunos algoritmos matemáticos pero no logro que el centroide caiga siempre dentro. Agradeceré su ayuda. Gracias

Publicar un comentario