Algoritmo Quickhull

[[seoane]]

Vamos a ver. En el algoritmo QuickHull, parte de una linea, y solo utilizan los que están por encima de ella (luego el proceso se repite para los que están por debajo). Ahora se busca el punto mas alejado a la linea y se forma un triángulo, se eliminan los puntos dentro del triángulo y se repite el proceso en los 2 nuevos lados del triángulo.

Pues bien, yo lo que hago es lo siguiente. Parto de la misma linea que en el caso anterior, busco el punto mas a la izquierda que este por encima de la linea, y el que esta mas a la derecha. Trazo entonces una nueva linea imaginaria entre ambos, elimino todos los puntos que quedan por debajo, y vuelvo a repetir el proceso. Los extremos de esas lineas imaginarias forman la envoltura convexa.

Y como tu dices roman solo hay una envoltura convexa, y de las 2 formas se obtiene el mismo resultado. Pero según parece el primer método es la forma mas eficiente de hacerlo. Aunque lo de calcular distancias de un punto a una recta, o saber si algo esta dentro o fuera de un triángulo se me hace complicado de calcular. Aunque también puede que ser porque aquí ya son mas de las 4 de la mañana