Búscalo aquí:

Algoritmo QuickHull para la Cerradura Convexa [código]

El quickhull es otro algoritmo usado para resolver el problema de la cerradura convexa de manera óptima y su modo de operar es distinto (como es de suponer) que el de Jarvis y Graham para la cerradura convexa. El quickhull necesita de una nube de puntos sobre la que calculará la envolvente o cerradura convexa y de una arista que forme parte de dicha cerradura convexa, de esta manera, el 3º punto que forme un triángulo de área máxima con dicha arista será un punto extremo (parte de la cerradura convexa). Si dicha área no es única el punto será el que maximice el ángulo del triángulo. De esta manera el quickhull tiene una complejidad de O(n log n) en el mejor caso y cuadrática O(n2) en el peor caso.


Para la implementación del quickhull en Java se hizo uso del paquete geom para aprovechar los métodos que provee la clase Line2D.

El código fuente en Java del algoritmo quickhull para la cerradura convexa se presenta a continuación.

  1. import java.awt.geom.*;
  2. /**
  3. @author: Jorge Valverde Rebaza
  4. */
  5. public static ListaEnlazada quickHull(ListaEnlazada S){
  6. int i=0,left=0,right=0;
  7. //1º encontramos los puntos mas extremos en X
  8. for(i=1; i<s.getSize(); i++){
  9. if(S.getCoordX(i) < s.getCoordX(left))
  10. left = i;
  11. else
  12. if(S.getCoordX(i) > S.getCoordX(right))
  13. right = i;
  14. }
  15. //2º creamos una linea entre los puntos extremos
  16. Line2D lineaAB = new Line2D.Double(S.getCoordX(left),S.getCoordY(left),
  17. S.getCoordX(right),S.getCoordY(right));
  18. //3º colocaremos los puntos que estan por encima o por debajo de la linea
  19. ListaEnlazada Arriba = new ListaEnlazada();
  20. ListaEnlazada Abajo = new ListaEnlazada();
  21. for(i=0; i<s.getSize();i++){
  22. if(lineaAB.relativeCCW(S.getCoordX(i),S.getCoordY(i))>=0 )
  23. Arriba.insertar(S.getPunto(i));
  24. else
  25. Abajo.insertar(S.getPunto(i));
  26. }
  27. //4º ahora las llamadas recursivas
  28. ListaEnlazada CH = new ListaEnlazada();
  29. CH.insertar(new Punto2D((int)lineaAB.getP2().getX(),
  30. (int)lineaAB.getP2().getY()));
  31. CH.union(llamadaQuick(lineaAB,Arriba));
  32. CH.insertar(new Punto2D((int)lineaAB.getP1().getX(),
  33. (int)lineaAB.getP1().getY()));
  34. CH.union(llamadaQuick(new Line2D.Double(lineaAB.getP2(),
  35. lineaAB.getP1()),Abajo));
  36. return CH;
  37. }
  38. private static ListaEnlazada llamadaQuick(Line2D lineaAB,
  39. ListaEnlazada S){
  40. ListaEnlazada resul = new ListaEnlazada();
  41. //caso base, cuando hay un solo punto
  42. if(S.getSize()==1 )
  43. resul.insertar(S.getPunto(0));
  44. else{
  45. Punto2D pLejano = buscarPuntoMasLejano(lineaAB,S);
  46. if(pLejano != null ){
  47. //desde la linea BC
  48. Line2D lineaBC = new Line2D.Double(pLejano.getX(),
  49. pLejano.getY(),(int)lineaAB.getP2().getX(),
  50. (int)lineaAB.getP2().getY());
  51. ListaEnlazada pBC = selectPuntoSobreLinea(lineaBC,S);
  52. resul.union(llamadaQuick(lineaBC,pBC));
  53. resul.insertar(pLejano);
  54. //desde la linea AC
  55. Line2D lineaAC = new Line2D.Double((int)lineaAB.getP1().getX(),
  56. (int)lineaAB.getP1().getY(),pLejano.getX(), pLejano.getY());
  57. ListaEnlazada pAC = selectPuntoSobreLinea(lineaAC,S);
  58. resul.union(llamadaQuick(lineaAC,pAC));
  59. }
  60. }
  61. return resul;
  62. }
  63. private static Punto2D buscarPuntoMasLejano(Line2D lineaAB,
  64. ListaEnlazada S){
  65. int farthest = -1;
  66. double farthest_dst = Double.MIN_VALUE;
  67. for (int i = 0; i < S.getSize(); i++) {
  68. if(lineaAB.relativeCCW(S.getCoordX(i),
  69. S.getCoordY(i)) > 0){
  70. if(lineaAB.ptLineDist(S.getCoordX(i),
  71. S.getCoordY(i)) > farthest_dst){
  72. farthest = i;
  73. farthest_dst = lineaAB.ptLineDist(S.getCoordX(i),
  74. S.getCoordY(i));
  75. }
  76. }
  77. }
  78. Punto2D point = null;
  79. if (farthest > -1)
  80. point = S.getPunto(farthest);
  81. return point;
  82. }
  83. private static ListaEnlazada selectPuntoSobreLinea(Line2D lineaAB,
  84. ListaEnlazada S){
  85. ListaEnlazada result = new ListaEnlazada();
  86. for(int i=0; i<S.getSize(); i++){
  87. if(lineaAB.relativeCCW(S.getCoordX(i),
  88. S.getCoordY(i))>0)
  89. result.insertar(S.getPunto(i));
  90. }
  91. return result;
  92. }

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

Espero les sea de utilidad, saludos




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

1 comentario:

  1. interesante blog, te felicito que compartas tus conocimientos, yo tbn estudio en la unt informatica y m sirve de mucho tu blog gracias!!

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