Algoritmo de envoltura de regalos

En geometría computacional , el algoritmo de envoltura de regalos es un algoritmo para calcular la envoltura convexa de un conjunto dado de puntos.

En el caso bidimensional, el algoritmo también se conoce como marcha de Jarvis , en honor a R. A. Jarvis, quien lo publicó en 1973; tiene una complejidad temporal de O ( nh ) , donde n es el número de puntos y h es el número de puntos en la envoltura convexa. Su rendimiento en la práctica, comparado con otros algoritmos de envoltura convexa, es favorable cuando n es pequeño o se espera que h sea muy pequeño con respecto a n . En casos generales, muchos otros algoritmos superan a este (véase Algoritmos de envoltura convexa ).

Para simplificar, la descripción que sigue asume que los puntos están en posición general , es decir, que no hay tres puntos colineales . El algoritmo puede modificarse fácilmente para abordar la colinealidad, incluyendo la decisión de si debe reportar solo los puntos extremos (vértices de la envoltura convexa) o todos los puntos que se encuentran en ella . Además, la implementación completa debe decidir cómo manejar los casos degenerados cuando la envoltura convexa tiene solo 1 o 2 vértices, así como los problemas de precisión aritmética limitada , tanto en los cálculos computacionales como en los datos de entrada.

El algoritmo de envoltura de regalos comienza con i = 0 y un punto p ₀ conocido que está en la envoltura convexa, por ejemplo, el punto más a la izquierda, y selecciona el punto p _{i + 1} tal que todos los puntos estén a la derecha de la línea p _i p _{i + 1.} Este punto se puede encontrar en tiempo O ( n ) comparando los ángulos polares de todos los puntos con respecto al punto p _i tomado como centro de coordenadas polares . Haciendo i = i + 1, y repitiendo hasta que se alcance p _h = p ₀ nuevamente produce la envoltura convexa en h pasos. En dos dimensiones, el algoritmo de envoltura de regalos es similar al proceso de enrollar una cuerda (o papel de regalo) alrededor del conjunto de puntos.

Este enfoque puede extenderse a dimensiones superiores.

El algoritmo jarvis(S) es // S es el conjunto de puntos // P será el conjunto de puntos que forman la envoltura convexa. El tamaño final del conjunto es i. pointOnHull := punto más a la izquierda en S // que está garantizado que forma parte del CH(S) i := 0 repetir P[i] := puntoEnElCasco endpoint := S[0] // punto final inicial para una arista candidata en el casco para j desde 0 hasta |S| hacer // endpoint == pointOnHull es un caso raro y solo puede ocurrir cuando j == 1 y aún no se ha establecido un mejor punto final para el bucle. si (endpoint == pointOnHull) o (S[j] está a la izquierda de la línea desde P[i] hasta endpoint) entonces endpoint := S[j] // Se encontró un giro a la izquierda mayor, se actualiza el endpoint i := i + 1 puntoEnElCasco := puntoFinal hasta que el punto final sea igual a P[0] // se envolvió hasta el primer punto del casco

El bucle interno comprueba cada punto del conjunto S , y el bucle externo se repite para cada punto del casco. Por lo tanto, el tiempo total de ejecución es${\displaystyle O(nh)}$El tiempo de ejecución depende del tamaño de la salida, por lo que la marcha de Jarvis es un algoritmo sensible a la salida .

Sin embargo, debido a que el tiempo de ejecución depende linealmente del número de vértices del casco, solo es más rápido que ${\displaystyle O(n\log n)}$algoritmos como el escaneo de Graham cuando el número h de vértices de la envoltura es menor que log n . El algoritmo de Chan , otro algoritmo de envoltura convexa, combina la dependencia logarítmica del escaneo de Graham con la sensibilidad de salida del algoritmo de envoltura de regalos, logrando un tiempo de ejecución asintótico.  ${\displaystyle O(n\log h)}$ que mejora tanto el escaneo de Graham como el empaquetado de regalos.

• Algoritmos de envolvente convexa