La geometría computacional es una rama que extiende el diseño y análisis de algoritmos, esta se comprende del estudio sistemático de algoritmos y estructuras de datos que refieran a objetos geométricos, esta área reúne tanto problemas matemáticos como problemas de ciencias de la computación, tiene aplicación en distintos campos como lo pueden ser la robótica, los gráficos por computadora o sistemas de ubicación geográfica, para dar una breve introducción veremos un algoritmo perteneciente a un problema estático que proviene de esta rama siendo un algoritmo para encontrar el cierre convexo dada una nube de puntos.
Veamos entonces el algoritmo para encontrar el cierre convexo (convex haull), este se refiere al polígono convexo que tenga en su interior todos los puntos, al ser un polígono convexo esto indica que todos los ángulos interiores son menores o iguales a 180 grados, dicho algoritmo es conocido como el algoritmo de graham (scan de graham), partimos encontrando el punto que tiene la coordenada mas pequeña en el eje Y, lo llamaremos p, tenemos ahora un angulo polar entre p y el resto de puntos, ordenamos dichos puntos de acuerdo al angulo polar que forman con p, una vez ordenados lo que haremos sera inicializar una pila en la que meteremos los primeros 2 puntos de nuestro ordenamiento, nos fijamos en la orientación que toma el angulo del punto en la pila con respecto al tercer punto en el ordenamiento si la orientación es de acuerdo al sentido contrario a las manecillas del reloj entonces lo metemos a la pila, si la orientación respecto al siguiente punto ordenado no es de acuerdo al sentido contrario a las manecillas del reloj entonces significa que ese punto no debería estar ahí por lo que quitamos el punto de la pila y comparamos la orientación con el punto actual de la pila y el siguiente punto ordenado, hacemos esto hasta que el punto que tengamos que meter sea igual a nuestro p inicial, lo que indica que habremos acabado y los puntos que están en la pila son los que forman nuestro cierre convexo, este algoritmo tiene una complejidad O(nlogn) por el tiempo que nos toma ordenar los puntos. A continuación se anexa un video de la mano del canal de youtube Inside code que explica el algoritmo y también muestra como seria una ejecución,(el video esta en ingles pero es posible activar subtítulos en español para una mayor comprensión):
No hay comentarios:
Publicar un comentario