• Posts recientes

    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

    Related Posts Plugin for WordPress, Blogger...

    Post Top Ad