Quickhull

Quickhull és un método per a calcular el tancament convexo d'un conjunt finito de punts (generalment en el pla 2D, pero també existixen versions per a dimensions superiors). Ampra una tècnica basada en dividix i venceràs similar a l'empleada per l'algoritme d'ordenació quicksort, del que pren el seu nom.

La seua complexitat promig és Θ(n * log(n)), encara que en el pijor cas pot prendre O(n²) en situacions d'alta simetria o en conjunts de punts situats en forma de circumferència.

Algoritme

La versió en 2D de l'algoritme Quickhull pot dividir-se en els següents passos:

1. Buscar un parell de punts optimales, generalment els punts en menor i major coordenada X, ya que estos sempre formen part del tancament convexo.
2. Usar la llínea entre abdós punts per a dividir el conjunt en dos subconjunts que seran processador de forma recursiva.
3. Determinar el punt situat a major distància de la llínea anterior. Junt als dos punts anteriors, formarà un triàngul.
4. Tots els punts situats en l'interior del triàngul poden ser descartats, ya que no formaran part del tancament convexo.
5. Repetir els dos passos anteriors en els dos costats del triàngul (no en el costat inicial).
6. Repetir fins que no queden punts sense classificar. Els punts seleccionats formen el tancament convexo..

• Passos 1-2: Dividir els punts en dos subconjunts per mig d'una llínea.
  Passos 1-2: Dividir els punts en dos subconjunts per mig d'una llínea.
• Passe 3: Buscar el punt a major distància i formar un triàngul.
  Passe 3: Buscar el punt a major distància i formar un triàngul.
• Passe 4: Descartar els punts interiors al triàngul.
  Passe 4: Descartar els punts interiors al triàngul.
• Passe 5: Repetir la classificació amprant els dos nous costats del triàngul.
  Passe 5: Repetir la classificació amprant els dos nous costats del triàngul.
• Passe 6: Resultat final.
  Passe 6: Resultat final.

Implementacions públiques

Els autors de l'algoritme mantenen una implementació de l'algoritme per mig d'una llibreria en llenguage C que pot ser cridada des de varis llenguages (com C++, Python). El còdic pot descarregar-se des de la pàgina del proyecte www.qhull.org o des del seu repositori de GitHub

Referències i enllaços externs

• Dave Mount. «QHull.org code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection about a Point.».
• Dave Mount. «Lecture 3: More Convex Hull Algorithms». Archivat des d'el original, el 10 de juny de 2018. Consultat el 6 de juliol de 2018.
• 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.