Developer: Laboratorio 3. Convex Hull

Para este post lo que hice fue implementar un algoritmo de convex hull, esto es dibujar una región convexa sobre una figura.

Para realizar esto es necesario tener implementado el algoritmo de bfs, encontrar los bordes y tener binarizada la imagen.

El algoritmo de bfs es necesario ya ahora en vez de encontrar los pixeles negros en la imagen binarizada ahora se deben encontrar los puntos blancos que son los bordes de la imagen.

Una vez teniendo las coordenadas de los bordes lo que hice fue recorrer este arreglo de coordenadas implementando el algoritmo Gift wrapping o también conocido como Jarvis Match; este algoritmo lo que hace es que toma el punto que se encuentra más a la izquierda, después recorre las coordenadas en busca de un punto que se encuentre más a la izquierda que él.

Para determinar cual punto se encuentra más a la izquierda utilicé el producto cruzado de tres puntos el cual utilize la siguiente fórmula

(p2[0] - p1[0])*(p3[1] - p1[1]) - (p3[0] - p1[0])*(p2[1] - p1[1]

donde p1 es la coordenada del borde que se esta analizando, p2 es el arreglo de puntos del convex hull y p3 es el punto que hasta el momento se está considerando más a la izquierda, es decir el candidato.

Bueno este es el código que utilicé:

Y aquí algunas pruebas:

Imagen original en binaria