Quickhull
Quickhull es un método para calcular el cierre convexo de un conjunto finito de puntos (generalmente en el plano 2D, pero también existen versiones para dimensiones superiores). Emplea una técnica basada en divide y vencerás similar a la empleada por el algoritmo de ordenación quicksort, del que toma su nombre.

Su complejidad promedio es Θ(n * log(n)), aunque en el peor caso puede tomar O(n2) en situaciones de alta simetría o con conjuntos de puntos situados en forma de circunferencia.

Algoritmo

La versión en 2D del algoritmo Quickhull puede dividirse en los siguiente pasos:
 Buscar un par de puntos optimales, generalmente los puntos con menor y mayor coordenada X, ya que estos siempre forman parte del cierre convexo. 
 Usar la línea entre ambos puntos para dividir el conjunto en dos subconjuntos que serán procesador de forma recursiva.
 Determinar el punto situado a mayor distancia de la línea anterior. Junto a los dos puntos anteriores, formará un triángulo.
 Todos los puntos situados en el interior del triángulo pueden ser descartados, ya que no formarán parte del cierre convexo.
 Repetir los dos pasos anteriores en los dos lados del triángulo (no en el lado inicial).
 Repetir hasta que no queden puntos sin clasificar. Los puntos seleccionados forman el cierre convexo..

Implementaciones públicas
Los autores del algoritmo mantienen una implementación del algoritmo mediante una librería en lenguaje C que 
puede ser llamada desde varios lenguajes (como C++, Python). El código puede descargarse desde la página del proyecto
www.qhull.org o desde su repositorio de GitHub

Referencias y enlaces externos

 
 Pseudocódigo, "https://web.archive.org/web/20180627005540/http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html".
 Implementing QuickHull (GDC 2014) – Algorithm presentation with 3D implementation details.

QuickHull
Quickhull es un método para calcular el cierre convexo de un conjunto finito de puntos ( generalmente en el plano , pero también existen versiones para dimensiones superiores ) . Emplea una técnica basada en divide y vencerás similar a la empleada por el algoritmo de ordenación quicksort , del que toma su nombre . Su complejidad promedio es Θ ( n * log( n ) ) , aunque en el peor caso puede tomar O( n2 ) en situaciones de alta simetría o con conjuntos de puntos situados en forma de circunferencia . Algoritmo La versión en del algoritmo Quickhull puede dividir se en los siguiente pasos : Buscar un par de puntos optimales , generalmente los puntos con menor y mayor coordenada X , ya que estos siempre forman parte del cierre convexo . Usar la línea entre ambos puntos para dividir el conjunto en dos subconjuntos que serán procesador de forma recursiva . Determinar el punto situado a mayor distancia de la línea anterior . Junto a los dos puntos anteriores , formará un triángulo . Todos los puntos situados en el interior del triángulo pueden ser descartados , ya que no formarán parte del cierre convexo . Repetir los dos pasos anteriores en los dos lados del triángulo ( no en el lado inicial ) . Repetir hasta que no queden puntos sin clasificar . Los puntos seleccionados forman el cierre convexo .. Implementaciones públicas Los autores del algoritmo mantienen una implementación del algoritmo mediante una librería en lenguaje C que puede ser llamada desde varios lenguajes ( como C++ , Python ) . El código puede descargar se desde la página del proyecto www.qhull.org o desde su repositorio de GitHub Referencias y enlaces externos Pseudocódigo , " https://web.archive.org/web/20180627005540/http://www.cse.yorku.ca/ ~aaw/Hang/quick_hull/Algorithm.html " . Implementing QuickHull ( GDC– Algorithm presentation with implementation details . QuickHull