Header Ads

ad728
  • Posts recientes

    Algoritmo Jarvis March para la Cerradura Convexa [código]

    El problema del cálculo eficiente de la cerradura convexa ha traído a lo largo de la historia grandes investigaciones en las que s ehan propuesto diversidad de algoritmos que, han resultado ser muy utilizados y difundidos por sus diversas características y bondades propias. En éste post se tratará sobre el Jarvis March Algorithm o algoritmo de Jarvis para la cerradura Convexa, el cual fúe propuesto por R. A. Jarvis en 1973, y que, a pesar de ser uno de los más sencillos cuenta con una complejidad computacional de O(nh).


    Como mencionaba el algoritmo de Jarvis también es llamado como gift wrapping algorithm puesto que a partir de un punto vértice (que formará parte de la envoltura) se procede a "envolver" como si de un regalo se tratáse a todos los puntos contenidos en la nube de puntos. De esta manera el algoritmo se torna sencillo, siendo el verdadero trabajo encontrar dicho primer punto a partir del cual extenderemos la cerradura convexa. Sin embargo, este cáluclo es que puede llevar a que éste algoritmo llegue a una complejidad cuadrática de O(n2) en el peor caso.

    El código fuente en Java del algoritmo de Jarvis es presentado a continuación. El parámetro de entrada de la funcion jarvisMarch() es una lista de puntos desordenados en el plano, y se obtendrá una lista de puntos correspondientes a la cerradura convexa.

    1. private static double anguloJm = 0;
    2. public static ListaEnlazada jarvisMarch(ListaEnlazada S){
    3. P = S;
    4. ListaEnlazada CH = new ListaEnlazada();
    5. int indexmenor = P.indiceMenorX();
    6. CH.insertar((Punto2D)P.getPunto(indexmenor));
    7. for(int p=getSiguientePunto(indexmenor);
    8. p!=indexmenor; p=getSiguientePunto(p))
    9. CH.insertar((Punto2D)P.getPunto(p));
    10. return CH;
    11. }
    12. //devuelve el punto con menor angulo respecto al
    13. //punto de indice index
    14. public static int getSiguientePunto(int index){
    15. double minangulo = 4;
    16. int minp = index;
    17. for(int i=0; i<p.getSize();i++){
    18. if(i!=index){
    19. double angle = Auxiliar.pseudoAngulo(
    20. P.getCoordX(i)-P.getCoordX(index),
    21. P.getCoordY(i)-P.getCoordY(index));
    22. if(angle >= anguloJm && angle <= minangulo){
    23. minp = i;
    24. minangulo = angle;
    25. }
    26. }
    27. }
    28. anguloJm = minangulo;
    29. return minp;
    30. }

    En un post anterior, en la que se trató acerca del algoritmo de Graham: Graham Scan algorithm compartí con ustedes el código fuente en Java de dicho algoritmo y el entorno de trabajo gráfico para su desarrollo y visualización. Para la implementación y funcionamiento del algoritmo de Jarvis necesitaremos de dicho entorno, así que favor de descargarlo previamente.

    Una vez descargado el entorno de trabajo, abrir el archivo GeoComp.java y agregar el código de la función jarvisMarch() y getSiguientePunto() presentados. Así mismo, abrir el archivo Auxiliar.java y colocar el código de las siguientes funciones necesarias para el cálculo del cuadrante del ángulo de giro del punto.

    1. public static double pseudoAngulo(double dx, double dy){
    2. if(dx >= 0 && dy >= 0)
    3. return ponerEnCuadrante(dx, dy);
    4. if (dx >= 0 && dy < 0)
    5. return 1 + ponerEnCuadrante(Math.abs(dy), dx);
    6. if (dx < 0 && dy < 0)
    7. return 2 + ponerEnCuadrante(Math.abs(dx), Math.abs(dy));
    8. if (dx < 0 && dy >= 0)
    9. return 3 + ponerEnCuadrante(dy, Math.abs(dx));
    10. throw new Error("Impossible");
    11. }
    12. public static double ponerEnCuadrante(double dx, double dy) {
    13. return dx / (dy + dx);
    14. }



    Espero les sea de utilidad, saludos.

    Quieres leer más post como éste???...suscribete aquí!!!

    1 comentario:

    1. Hola jorge viendo tu codigo de jarvis march en esta linea,de la funcion getsiguientepunto tengo un problema:
      p.getSize()
      me entrega un error por el p.getSize.
      si me puedes ayudar seria fantastico
      saludos

      ResponderEliminar

    Bienvenido a jcGeorge's Blog!!!

    Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

    Gracias por leer este blog!!!

    Related Posts Plugin for WordPress, Blogger...

    Post Top Ad

    Post Bottom Ad

    ad728