Notas al Proyecto: Anchura mínima de una nube de puntos

Proyecto: Anchura de una nube de puntos
Autor: Javier Cáceres (940080)
Asignatura: Geometría Computacional. Optativa 4º
Tutor: Gregorio Hernández Peñalver
Descripción: Applet para el cálculo de la anchura y diámetro de una nube de puntos

Sinopsis:
El siguiente Applet calcula la anchura mínima de una nube de puntos. Por anchura mínima entendemos la distancia mínima entre rectas paralelas que son soporte del polígono que forma la envolvente convexa (cierre convexo), de una nube de puntos. Sabiendo que la distancia mínima se hallará en puntos del cierre convexo, que los puntos por los cuales las rectas paralelas de distancia mínima pasarán son antípodas y que necesariamente, una de las rectas paralelas se "apoya" en uno de los lados del polígono del cierre convexo, la forma de proceder es bastante clara. Primero hallamos el cierre convexo de una nube de puntos. Luego elegimos los puntos mínimo y máximo según el eje de abscisas (podría ser igualmente el de ordenadas). Una vez tengamos xmin y xmax (puntos mínimo y máximo respecto del eje X del cierre convexo), procedemos a trazar virtualmente dos rectas paralelas que vamos girando en sentido positivo. El ángulo que hemos de girar las bandas, y por tanto el nuevo punto a considerar, vendrá determinado por el punto de entre los dos siguientes (en las respectivas bandas) forma un ángulo menor con respecto a las recta paralela más próxima. Una vez decidido el nuevo punto de estudio, se calcula la distancia entre el punto que no ha avanzado, y el segmento formado por el nuevo punto de estudio y su anterior. Esa distancia se almacena en una variable, de forma que se acabe devolviendo la menor de las distancias estudiadas. Calculamos igualmente el diámetro de la nube de puntos de forma similar, con una variable de control que va comprobando las sucesivas diagonales que van a pareciendo. El algoritmo finaliza cuando una de las bandas alcanza el punto con el que comenzó la otra.

El Cierre convexo se puede hallar en un tiempo O(nlogn), mientras que la anchura sobre ese cierre convexo se puede hallar en un tiempo lineal O(n). Por tanto, el tiempo total del algoritmo es el mayor de los dos, esto es: O(nlogn).

El algoritmo podría formalizarse de la siguiente manera:

Entrada: Nube de puntos en forma de lista S sin orden alguno.
Salida: A, valor de la anchura de S.

Paso 1: Calcular cierre convexo de S, devolver lista cíclica P con los n vértices del polígono convexo en orientación positiva. Emplear p.ej. Scan de Graham.
Paso 2: Inicializar A:=infinito
Paso 3: Localizar en P los ptos mínimo y máximo con orden lexicográfico: xmin, xmax.
Paso 4: Hacer p:=xmin y q:= xmax
Paso 5: Mientras p<>xmin y q<>xmax, hacer:

                1) x:= p + SIG(q) - q
                2) Si Area_Signada(p, SIG(p), x) < 0
                    2.1) Hallar A' := 2*(|Area_Signada(p, SIG(p),q)|)/Distancia(p, SIG(p))
                    2.2) Hacer A:= min(A, A') y p:= SIG(p)
                3) Si Area_Signada(p, SIG(p), x) > 0
                    3.1) Hallar A' := 2*(|Area_Signada(q, SIG(q),p)|)/Distancia(q, SIG(q))
                    3.2) Hacer A:= min(A, A') y q:= SIG(q)
                4) Si Area_Signada(p, SIG(p), x) = 0
                    4.1) Hallar A' := 2*(|Area_Signada(q, SIG(q),p)|)/Distancia(q, SIG(q))
                    4.2) Hacer A:= min(A, A'), p:=SIG(p), y q:= SIG(q)

Paso 6: Devolver A

El Applet está desarrollado lógicamente en Java. Para compilarlo precisará de una versión del JDK 1.1 o superior. El código fuente es autoexplicativo, se incluyen comentarios a todas las variables y funciones. Pinche aquí para ver el código del Applet.

Modo de empleo:
    El modo de empleo es sencillo. La interfaz presenta dos menus desplegables, dos botones, un área de texto y un área de dibujo. Situando el ratón sobre el área blanca de dibujo y presionando cualquiera de los botones, aparecerá un punto en esa posición. Si quisiéramos eliminar algún punto, sólo hemos de situarnos sobre le punto a borrar y hacer click sobre él mientras mantenemos presionada la tecla SHIFT o MAYÚSCULAS.
    El primer menu selecciona el color de fondo de la pizarra, mientras que el segundo menu desplegable nos servirá para seleccionar la pausa que el programa hará en cada uno de sus pasos o iteraciones. De seleccionar el modo paso a paso, una vez pulsado el botón EJECUTAR ALGORITMO, habremos de ir pulsando reiteradamente una tecla para ir ejecutando secuencialmente los pasos del algoritmo. Si quisiéramos llegar rápidamente hasta un punto avanzado del algoritmo, manteniendo pulsada la tecla, se ejecutará el algoritmo rápidamente hasta que la soltemos. El botón LIMPIAR, como su nombre indica, limpia, elimina todo lo presente en el area de dibujo en ese momento.
    El botón EJECUTAR ALGORITMO iniciará la secuencia de algoritmos que acabarán con darnos la anchura mínima de la nube de puntos dada. Primero se calculará el algoritmo de Graham, que dibujará paso a paso el cierre convexo de la nube de puntos con un borde azúl. Una vez tenemos el cierre convexo, se ejecuta el siguiente algoritmo que se encarga de encontrar la anchura propiamente dicha. Dado que estudiamos de 3 en 3 puntos, en rojo, el Applet representará el triángulo que forman los mismos.
    El área de texto situada bajo los dos botones muestra siempre información pertinente a todo lo que estamos haciendo o lo que está calculando el algoritmo.
    El Applet gestiona la animación de los algoritmos y la entrada del usuario en multitarea. Una vez pulsado el botón de EJECUTAR ALGORITMO, podemos parar el proceso en cualquier momento presionando cualquiera de los botones, incluyendo o eliminando alguno de los puntos.