Búscalo aquí:

Algoritmo del Par más Próximo [código]


En Geometria Computacional, uno de los algoritmos de gran uso y aplicación es el algoritmo del par más proximo, es decir, dada una nube de puntos dispersos, se debe encontrar la menor distancia de separación entre un par de ellos, por supuesto que el algoritmo debe ser óptimo y tener una complejidad es 'n logarítmica' (O(n log n) ), puesto que de no ser así, ante una cantidad grande puntos podemos encontrar grandes complicaciones durante el procesamiento.


El código en Java de la implementación del algoritmo del par más proximo (closest pair), es el siguiente:



  1. public static double parProximo(ListaEnlazada S, int i, int j)

  2. {

  3. P = S;

  4. return parMasProximo(i,j);

  5. }

  6. private static double parMasProximo(int i, int j)

  7. {

  8. double delta = 0;

  9. if((j-i)<=2) //si a lo más existen únicamente 2 o 3 puntos

  10. {

  11. //calcular la distancia minima entre cada par de puntos

  12. if((j-i)==1) //si existen 2 puntos

  13. delta = Auxiliar.distancia(P.getPunto(i), P.getPunto(j));

  14. else if((j-i)==2)//si existen 3 puntos

  15. delta = Auxiliar.distancia(P.getPunto(i),
    P.getPunto(i+1), P.getPunto(j));

  16. Auxiliar.ordenarPorY(P,i,j);

  17. return delta;

  18. }

  19. //sea l una recta que pasa por un punto con indice k

  20. int k = (int) Math.floor((i+j)/2);

  21. int lx = P.getCoordX(k);//coordenada X del punto ke pasa por la posicion n/2

  22. //Dividir en dos subconjuntos

  23. double delta_i = parMasProximo(i,k);

  24. double delta_d = parMasProximo(k+1,j);

  25. //obtenemos el delta minimo

  26. delta = Auxiliar.minimo(delta_i,delta_d);

  27. if(delta==0) //ya no habra minimo mas minimo pz

  28. return delta;

  29. //mezclamos

  30. Auxiliar.mezclar(P,i,k,j);

  31. //Sea V un conjunto de puntos

  32. ListaEnlazada V = new ListaEnlazada();

  33. for(int m=i; m<=j; m++)

  34. {

  35. if((P.getCoordX(m) > (lx-delta)) && (P.getCoordX(m) < (lx+delta)))

  36. V.insertar(P.getPunto(m));

  37. }

  38. double distaux;

  39. for(int m=0; m<V.getSize(); m++)

  40. {

  41. for(int n=m+1; n<Auxiliar.minimo(V.getSize()-1,m+7); n++)

  42. {

  43. distaux =Auxiliar.distancia(V.getPunto(m),
    V.getPunto(n));

  44. if(distaux < delta)

  45. delta = distaux;

  46. }

  47. }

  48. V = null;

  49. return delta;

  50. }

En el archivo Auxiliar.java se encuentran funciones como:



  1. //distancia entre dos puntos

  2. public static double distancia(Punto2D p1, Punto2D p2)

  3. {

  4. double v1 = (Math.pow((p2.getX()-p1.getX()),2));

  5. double v2 = (Math.pow((p2.getY()-p1.getY()),2));

  6. return Math.sqrt(v2+v1);

  7. }


  8. //distancia minima entre 3 puntos

  9. public static double distancia(Punto2D p1, Punto2D p2, Punto2D p3)

  10. {

  11. double distancia = 0;

  12. double [] d = new double[3];

  13. d[0] = Auxiliar.distancia(p1, p2);

  14. d[1] = Auxiliar.distancia(p1,p3);

  15. d[2] = Auxiliar.distancia(p2,p3)

  16. if(d[0] < d[1])

  17. distancia = d[0];

  18. else

  19. distancia = d[1];

  20. if(distancia>d[2])

  21. distancia = d[2];

  22. return distancia;

  23. }


  24. public static void ordenarPorY(ListaEnlazada P,int i,int j)

  25. {

  26. A = P;

  27. B = new ListaEnlazada(A.getSize());

  28. mergeSortY(i,j);

  29. }


  30. public static void mergeSortY(int lo,int hi)

  31. {

  32. if(lo <hi)

  33. {

  34. int m = (lo+hi)/2;

  35. mergeSortY(lo,m);

  36. mergeSortY((m+1),hi);

  37. mezclarY(lo,m,hi);

  38. }

  39. }

  40. //Bitonic variant

  41. private static void mezclarY(int lo, int m, int hi)

  42. {

  43. int i=lo, j=hi, k=lo;

  44. //copiamos la primera mitad en el array auxiliar B

  45. while(i<=m)

  46. B.insertar((Punto2D)A.getPunto(i++),k++);

  47. //copiamos la segunda mitad al array auxiliar B, pero en orden inverso

  48. while(j>m)

  49. B.insertar((Punto2D)A.getPunto(j--),k++);

  50. i=lo; j=hi; k=lo;

  51. //ordenamos

  52. while(i<=j)

  53. {

  54. if(B.getCoordY(i)getCoordY(j)) //si es menor

  55. A.insertar((Punto2D)B.getPunto(i++),k++);

  56. else

  57. {

  58. if(B.getCoordY(i)==B.getCoordY(j))

  59. {

  60. if(B.getCoordX(i)getCoordX(j))

  61. A.insertar((Punto2D)B.getPunto(i++),k++);

  62. else

  63. A.insertar((Punto2D)B.getPunto(j--),k++);

  64. }

  65. else//si es mayor

  66. A.insertar((Punto2D)B.getPunto(j--),k++);

  67. }

  68. }

  69. }


  70. //minimo de dos numeros

  71. public static double minimo(double a, double b)

  72. {

  73. if(a < b)

  74. return a;

  75. return b;

  76. }



  77. //función mezcla, similar a la del merge. Se tiene en cuenta la coordenada Y de

  78. //los puntos,

  79. public static void mezclar(ListaEnlazada A, int p, int q, int r)

  80. {

  81. int n1 = q-p+1;

  82. int n2 = r-q;

  83. ListaEnlazada L = new ListaEnlazada();

  84. ListaEnlazada R = new ListaEnlazada();

  85. int i=0,j=0,k=0;

  86. for(i=0; i<n1; i++ )

  87. L.insertar((Punto2D)A.getPunto(p+i));

  88. for(j=0; j<n2; j++)

  89. R.insertar((Punto2D)A.getPunto(q+j+1));

  90. Punto2D poin = new Punto2D(Integer.MAX_VALUE, Integer.MAX_VALUE);

  91. R.insertar(poin);

  92. L.insertar(poin);

  93. poin = null;

  94. i=0;j=0;

  95. for(k=p; k<=r; k++)

  96. {

  97. if(L.getCoordY(i)<=R.getCoordY(j))

  98. A.insertar((Punto2D)L.getPunto(i++),k);

  99. else

  100. A.insertar((Punto2D)R.getPunto(j++),k);

  101. }

  102. R = null;

  103. L = null;

  104. }

La estructura ListaEnlazada mantiene una lista de elementos Punto2D los cuales a su vez tienen como atributos principales coordenas X y Y pues representan a un punto en el espacio bidimensional.

Espero les sirva, saludos :D
Quieres leer más post como éste???...suscribete aquí!!!

3 comentarios:

  1. Hay muchas cosas incompletas en ese c{odigo

    ResponderEliminar
  2. A mi me parece que cumple con el objetivo y no me ha dado ningun problema

    ResponderEliminar
  3. El paquete A donde se inicializa? Punto2D y ListaEnlazada no definidos e.e

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