Búscalo aquí:

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...