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.
- 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 AlgorithmEsta 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 HullEsta 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 10Esta 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
http://mathworld.wolfram.com/ConvexHull.htmlhttp://www.dr-mikes-maths.com/DP-convex-hull-java-code.html