Google
 

sábado, 20 de septiembre de 2008

Kirkpatrick-Seidel’s

Este algoritmo lo implemente en el curso de Geometria Computacional como trabajo de investigacion de la primera Unidad, la idea del algoritmo la explicare a continuacion pero lo que si se debe tener en cuenta es que la complejidad despues de implementarlo debe ser T(n, h) = O(n lg h) si esto no es asi entonces de nada servira pues para ello existen otros algoritmos mas sencillos pero con mayor complejidad que se implementaron en el laboratorio de este curso ( Graham Scam, Gift wrapping, Algoritmo Incremental, QuikHull, Algoritmo Divide y Venceras) .


  1. INTRODUCTION Figure 1: Casco alto y casco bajo
    El algoritmo de Kirkpatrick Seidel se nombra de esa manera por sus inventores, David G. Kirkpatrick y Raimund Seidel. La idea basica de este algoritmo es utilizar la tecnica de dividir y conquistarasi como una poda para hallar la cerradura convexa la cual es tratada como dos algoritmos (algoritmo para el casco alto y algoritmo para el casco bajo) en dos dimensiones vendria a ser la separacion por la vertical del x minimo y el x maximo ( g.1). En realidad los dos algoritmos son muy parecidos por ello se hablara de uno de ellos el algoritmo del casco alto, para este algoritmo se debe hallar la mediana (m) de los puntos P y dividir en dos grupos L y R y hallar un segmento pq donde p pertenece a L y q pertenece a R ( g.2) despues de esto se eliminaran de L los puntos mayores a x(p) y de R los menores a x(q) para volver a calcular el casco alto de cada uno de los grupos restantes L' y R'.
    Figure 2: Puente superior y mediana Figure 2: Puente superior y mediana

  2. ALGORITMO
    Es un algoritmo recursivo aqui se presenta el algoritmo para el Casco Alto de igual forma para hallar el Casco Bajo se seguira el mismo algoritmo solo que se utilizaran solo los puntos con menor Y.
  3. ENCONTRAR EL PUENTE SUPERIOR
    Para hallar el puente superior debemos escoger del grupo de puntos L un p y del grupo de puntos R un q tal que el y de la interseccion con la mediana sea el mayor de todos ( g.3).
    Sea: p=(x1, y1) y q=(x2, y2) dos puntos donde p 2 L y q 2 R. Entonces: la ecuacion de la
    recta pq seria:
    y-y1= (y2-y1/x2-x1)*(x-x1)
    Tambien sabemos que el punto de la ecuacion de la recta de la mediana que se intercepta
    con pq es: (xm, ym) pero sabemos que xm = m , ademas sabemos que el punto (xm, ym)
    pertenece ala recta pq por ello para hallar el maximo y se obtendria de la siguiente manera:
    y-y1= (y2-y1/x2-x1)*(x-x1)
    y-y1= (y2-y1/x2-x1)*(xm-x1)
    y= (y2-y1/x2-x1)*(xm-x1) +y1

Figure 3: Puentes superiores posibles
La idea no termina aqui pues la primera idea seria comparar punto por punto lo que seria O(n^2) pero este paso se debe hacer en O(n) y fue en O(n) que pude implementar este paso.

  • EJECUTABLE
    Se desarrollo en java, se pueden ingresar los puntos mediante eventos del mouse asi como cargando los puntos desde un archivo tambien se podra visulisar el tiempo que demora la ejecucion del algoritmo. En los archivos hay 1000 , 10 000 , 100 000, 500 000, 1 000 000 puntos respectivamente. Com 1 000 000 se daran cuenta que se optiene un buen tiempo al ejecutar el algoritmo O(n lg h) .

Descargar Kirkpatrick-Seidel’s parte1

3 comentarios:

Unknown dijo...

Bien ahi Api
stas n el mismo Nivel q yo (Y)

Jorge Valverde-Rebaza dijo...

Osciest (Y) bien ahi con el algoritmo de kirkpatrick & Seidel para la cerradura convexa (Y) congratulations

Mrcds dijo...

hola! he visto tu blog y me parece q esta muy bien. Ahora mismo estoy desarrollando un proyecto fin de carrera sobre envolventes conexas. Seria posible que me mandases el proyecto en java del algoritmo q has implementado de kirkpatrick-seidel? si es asi te estaria enormemente agradecida. mi correo es mer_roa@hotmail.com. Gracias!