Búscalo aquí:

Algoritmo de Graham [código]

El algoritmo de Graham es uno de los mas conocidos en lo que respecta a los algoritmos para encontrar la cerradura convexa de una nube de puntos. Fue desarrollado a finales de la década de los 60, cuando en los laboratorios Bell se necesitaba calcular la cerradura convexa de una cantidad enorme de puntos (10000 a más), y con uno de los algoritmos de por entonces, de O(N^2) resultaba demasiado lento. Entonces Graham lo solucionó con el presente algoritmo.


En este post comparto con ustedes el código fuente escrito en Java del algoritmo de Graham (Graham scan) para la cerradura convexa. Para cuestiones de pruebas se han generado archivos de puntos (con diferentes cantidades de puntos) en posiciones aleatorias. Al ejecutar el programa, debes dirigirte al menu y elegir en la esptaña Geocomp la opcion Graham, luego, en el menu Acciones, elegir la opcion Ejecutar, con esto se dibujará el cierre convexo genrado para la nube de puntos generado. En la figura de abajo se observa una nube de 10000 puntos de color rojo y su cierre convexo generado con el algoritmo de Graham (linea de color verde)



Asi mismo, si no deseas usar ningun archivo de puntos, puedes generar clickear directamente en el área de dibujo para representar los puntos en las posiciones que desees.

El código lo puedes descargar desde AQUI. Espero les sea de utilidad, saludos.


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



13 comentarios:

  1. el codigo no compila

    ResponderEliminar
  2. El codigo es correcto, tal vez te estan faltando colocar algunos detalles para cu correca compilación

    ResponderEliminar
  3. Me temo que a mi tampoco me compila... me reporta errores en lista enlazada y panel principal!! sobretodo en este último

    ResponderEliminar
  4. Hola a todos, lo que mencionan no creo que se trate de un error, mas bien se debe tratar de llamadas a funciones que no existen, tal vez deben de percatarse de cuales son para que las comenten (se me olvido hacerlo), algunas de ellas deben de ser:

    GeoComp.jarvisMarch(screen.getLista());
    GeoComp.kirkpatrickSeidel(screen.getLista());
    ...

    Las cuales, si s epercatan en la clase GeoComp no existen. por lo tanto, deben borrar o comentar estas lineas de codigo.

    Si el error se trata de otras cosas, se los agradeceria que me lo hagan saber. Saludos

    ResponderEliminar
  5. Hola Jorge Carlos, soy el anonimo del ultimo comentario. Como decias, el codigo esta bien, solo era cuestion de esas funciones ;)
    Por cierto, no tendras implementada la del incremental verdad?? te lo agradeceria infinito!!
    si pudieses, mi correo es carlosdrs@hotmail.com
    Muchas gracias!!

    ResponderEliminar
  6. Jorge tengo dos problemas con el codigo
    uno es con este metodo
    delta = GeoComp.parProximo(screen.getLista(),0,screen.getSizeLista()-1);
    le revise en la calse GeoComp y no esta
    y el otro es con
    if(!Auxiliar.isIgual(point,punto))//si son diferentes lo inserto
    que lo revise en la clase auxiliar y no esta.
    no me manejo mucho en java pero si me puedes ayudar seria genial
    Muy buen trabajo

    ResponderEliminar
  7. Hola, lo refrente al codigo fuente del algoritmo del par proximo lo puedes encontrar en el post del algoritmo del par más proximo en el cual encontrarás los métodos que te hacen falta e ir acoplandolos a tu proyecto. O en todo caso, si no los necesitas los puedes comentar y ejecutar el programa.

    Saludos

    ResponderEliminar
  8. Estimado Jorge, pude utilizar el codigo de graham y funciono, el problema o mejor dicho dudas que tengo ahora es con el del par mas proximo en las siguiente lineas:
    1. for(int m=0; mgetSize(); m++)
    pq pones mgetSize, no entendi eso
    2. for(int n=m+1; nminimo(V.getSize()-1,m+7); n++)
    pq colocas nminimo, lo cambie poe Auxiliar.minimo y no funciono
    3. if(distaux) java alega pq no hay expresion booleana, estoy utilizando netbeans.
    si me puedes orientar seria genial.

    ResponderEliminar
  9. Hola, los errores que comentas se deben a que el html confundio algunos simbolos (mayor,menor que) como inicio/fin de tags...pero ya esta solucionado dicho inconveniente, puedes verificar el codigo:

    algoritmo del par mas proximo

    ResponderEliminar
  10. Hola nuevamente, me ha servido de mucha ayuda tu codigo para ir aprendiendo mas de java.
    Quisiera saber si tienes implementado el algoritmo incremental de cierre convexo. Como esta comentado en el codigo queria saberlo y si me lo puedes enviar
    mi correo es pachacute@gmail.com
    Saludos y muchas gracias por tu ayuda

    ResponderEliminar
  11. Hola ncesito muchisimo este codigo necesito hacer unt rabajo sobre nube de puntos como trabajo final de geometria comptacional pero tengo un problema al dar click en el link, me aparece que la pagina no la encuentra, alguien podria por favor mandarme el codoigo a mi correo: escobarsa_169@hotmail.com

    ResponderEliminar
  12. Hola el código fuente en Java del algoritmo de Graham ya esta disponible para descargarlo. Exitos en tu trabajo!!

    ResponderEliminar
  13. Como compilo tus codigos fuente?
    saludos y excelente blog

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