Convex Hull

Convex Hull (envoltorio convexo), consiste en buscar el menor polígono convexo H por lo que cada punto X1, X2, Xn, está a un lado del polígono H o en su interior.

Existen muchas implementaciones de este sistema, pero se utiliza mucho en el reconocimiento de patrones, procesamiento de imágenes, estadística, sistemas de información geográfica, etc.

• Diferentes implementaciones:

Podemos encontrar en la red, diversas implementaciones de los algoritmos más conocidos del Convex Hull, en diversos lenguajes de programación, Delphi, Java, C/C++, Matlab, etc. Aquí os dejo varios proyectos abiertos que intentan resolver el Convex Hull en 2D y alguno en 3D.

FastGeo 5.01

FastGeo, es una librería desarrollada en Delphi por Arash Partow. Contiene una amplia gama de algoritmos optimizados de geometría computacional y diversas rutinas para diferentes tipos de operaciones geométricas como primitivas, cálculos hull, triangulación, rotaciones, etc.
FastGeo ofrece una interfície para primitivas geométricas y rutinas complejas usando Object Pascal.

Su instalación es muy simple. Primero tenemos que descargar la librería desde este enlace: FastGeo Library Source Code, y también descargamos FastGeo Graphical Interface y FastGeo Convex Hull Demonstration. Una vez descargados, tenemos que crear un package e incluir los ficheros de la librería y de la interfície gráfica. Una vez instalado el Package, abrimos el convex Hull demonstration, y lo iniciamos. Luego podremos ver la aplicación, iniciar un test y calcular el convex Hull:


Fast Convex Hull Algorithm
Esta implementación creada en matlab, nos muestra un algoritmo muy rápido y eficiente capaz de calcular el envoltorio convexo en 2D. Esta implementación la podemos encontrar en Matlab Central de la mano de Luigi Giaccari. Podéis descargar el algoritmo directamente desde este enlace: ConvHull2D.m.

Java Convex Hull
Esta implementación sale de la Universidad de Lethbridge (Canada), de las manos del Dr. Stephen Wismath. Está hecha en un applet, y podemos crear los puntos manualmente y ver la ejecución paso a paso del algoritmo, ya sea por fuerza bruta (analizando todos los puntos) o mediante soluciones complejas de algoritmos Hull. Aquí os dejo el código fuente en descarga directa (ConvexHull.java) , echarle un vistazo ya que es muy interesante.



Algorithm 10
Esta implementación en C++ de SoftSurfer, nos provee de un cálculo sencillo mediante la entrada de unos puntos, nos devuelve la lista de puntos conectados. Este ejemplo utiliza el Andrew's monotone chain algorithm.

• Demostraciones interactivas on-line:

http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

• Enlaces de interés:

http://mathworld.wolfram.com/ConvexHull.html
http://www.dr-mikes-maths.com/DP-convex-hull-java-code.html