Casco rápido

Quickhull es un método para calcular la envoltura convexa de un conjunto finito de puntos en un espacio n -dimensional. Utiliza un enfoque de divide y vencerás similar al de quicksort , de donde deriva su nombre. Su complejidad temporal en el peor de los casos para espacios bidimensionales y tridimensionales es , pero cuando la precisión de entrada está restringida a bits, se conjetura que su complejidad temporal en el peor de los casos es , donde es el número de puntos de entrada y es el número de puntos procesados ​​(hasta ). ^[1]${\displaystyle O(n^{2})}$${\displaystyle O(\log n)}$${\displaystyle O(n\log r)}$${\estilo de visualización n}$${\estilo de visualización r}$${\estilo de visualización n}$

El algoritmo Quickhull N-dimensional fue inventado en 1996 por C. Bradford Barber, David P. Dobkin y Hannu Huhdanpaa. ^[1] Fue una extensión del algoritmo Quickhull planar de Jonathan Scott Greenfield de 1990, aunque los autores de 1996 no conocían sus métodos. ^[2] En cambio, Barber et al. lo describen como una variante determinista del algoritmo de Clarkson y Shor de 1989. ^[1]

El algoritmo bidimensional se puede dividir en los siguientes pasos: ^[2]

1. Encuentra los puntos con coordenadas x mínimas y máximas, ya que siempre serán parte de la envoltura convexa. Si existen muchos puntos con la misma x mínima/máxima, utiliza los que tengan la y mínima/máxima, respectivamente.
2. Utilice la línea formada por los dos puntos para dividir el conjunto en dos subconjuntos de puntos, que se procesarán de forma recursiva. A continuación, describimos cómo determinar la parte del casco que está por encima de la línea; la parte del casco que está por debajo de la línea se puede determinar de forma similar.
3. Determinar el punto situado por encima de la recta con la máxima distancia a la misma. Este punto forma un triángulo con los dos puntos de la recta.
4. Los puntos que se encuentran dentro de ese triángulo no pueden ser parte de la envoltura convexa y, por lo tanto, pueden ignorarse en los siguientes pasos.
5. Repita recursivamente los dos pasos anteriores en las dos líneas formadas por los dos nuevos lados del triángulo.
6. Continúe hasta que no queden más puntos, la recursión haya llegado a su fin y los puntos seleccionados constituyan la envoltura convexa.

El problema es más complejo en el caso de dimensiones superiores, ya que el casco está formado por muchas facetas; la estructura de datos debe tenerlo en cuenta y registrar también la línea/plano/hiperplano (cresta) que comparten las facetas vecinas. Para dimensiones d : ^[1]

1. Seleccione d + 1 puntos del conjunto que no compartan un plano o un hiperplano. Esto forma una envoltura inicial con facetas Fs[] .
2. Para cada F en Fs[] , encuentre todos los puntos no asignados que están "por encima" de él; es decir, que apuntan lejos del centro de la envoltura, y asígnelos a un conjunto "externo" FO asociado con F . El algoritmo mantiene la invariante de que cada punto que no se ha agregado a la envoltura pero que potencialmente podría ser un vértice de ella se asigna exactamente a un conjunto externo.
3. Para cada F con un FO no vacío :
   1. Encuentre el punto p en FO con la distancia máxima desde F y agréguelo al casco. Tenga en cuenta que p no necesariamente será un vértice del casco final, ya que podría eliminarse más adelante.
   2. Crea un conjunto visible V e inicialízalo en F. Extiende V en todas las direcciones para las facetas vecinas Fv hasta que no haya más facetas visibles desde p . El hecho de que Fv sea visible desde p significa que p está por encima de Fv.
   3. El límite de V forma entonces el conjunto de crestas del horizonte H.
   4. Sea Fnew[] el conjunto de facetas creadas a partir de p y todas las crestas en H .
   5. Anule la asignación de todos los puntos en los conjuntos externos de facetas en V. Para cada faceta nueva en Fnew[] , realice el paso (2) considerando únicamente estos puntos recién anulados para inicializar su conjunto externo. Tenga en cuenta que todos los puntos que permanecen sin asignar al final de este proceso se encuentran dentro del casco actual.
   6. Elimine las facetas internas de V de Fs[] . Agregue las facetas nuevas de Fnew[] a Fs[] y continúe la iteración.

Entrada = un conjunto S de n puntos
Supongamos que hay al menos 2 puntos en el conjunto de entrada S de puntos

función QuickHull( S ) es 
    // Encuentra la envoltura convexa del conjunto S de n puntos
    Casco convexo := {}
    Encuentre los puntos más a la izquierda y a la derecha, digamos A y B, y agregue A y B a la envoltura convexaEl segmento AB divide los ( n − 2) puntos 
    restantes en 2 grupos S1 y S2  
        donde S1 son puntos en S que están en el lado derecho de la línea orientada de A a B ,
        y S2 son puntos en S que están en el lado derecho de la línea orientada de B a A  
    FindHull( S1 , A , B )
    BuscarHull( S2 , B , A )
    Salida: Envolvente convexa
función final

función FindHull( Sk , P , Q ) es 
    // Encuentra puntos en la envoltura convexa del conjunto Sk de puntos  
    // que están en el lado derecho de la línea orientada de P a Q 
    si  Sk no tiene punto entonces 
        regresa 
    Del conjunto dado de puntos en Sk , encuentra el punto más alejado, digamos C , del segmento PQ  
    Agrega el punto C a la envoltura convexa en la ubicación entre P y Q  
    Tres puntos P , Q y C dividen los puntos restantes de Sk en 3 subconjuntos: S0 , S1 y S2  
        donde S0 son puntos dentro del triángulo PCQ, S1 son puntos en el lado derecho de la línea orientada
        La línea de P a C y S2 son puntos en el lado derecho de la línea orientada de C a Q.
    BuscarHull( S1 , P , C )Función final 
    FindHull( S2 , C , Q ) 

Jordan Smith ofrece un pseudocódigo especializado para el caso 3D. Incluye una estrategia de "punto máximo" similar para elegir la envoltura inicial. Si estos puntos máximos son degenerados, también lo es toda la nube de puntos. ^[3]

• Algoritmos de envoltura convexa

• Dave Mount. "Conferencia 3: Más algoritmos de envoltura convexa". Archivado desde el original el 11 de abril de 2001.

• Implementación de QuickHull (GDC 2014): presentación del algoritmo con detalles de implementación en 3D.