El algoritmo del embalaje de regalo del es un algoritmo simple para computar el casco convexo de un sistema dado de puntos.

Caso planar

En el caso de dos dimensiones el algoritmo también se conoce como marzo de Jarvis del, después del R. Jarvis, que lo publicó en 1973; tiene complejidad del tiempo O ( nh ), donde está el número el n de puntos y el h es el número de puntos en el casco convexo. Su funcionamiento de la vida real comparado con otros algoritmos convexos del casco es favorable cuando n es pequeña o se espera que h sea muy pequeño con respecto al N. En casos del general el algoritmo es superado por muchos otros.

Algoritmo

Por simplicidad, la descripción abajo asume que los puntos están en la posición general, es decir, no hay tres puntos el colineal. El algoritmo se puede modificar fácilmente para tratar de collinearity, incluyendo la opción si debe divulgar solamente a los puntos extremos (cimas del casco convexo) o todos los puntos que mienten en el casco convexo. También, la puesta en práctica completa debe tratar de los casos degenerados cuando el casco convexo tiene solamente 1 o 2 cimas, así como con las aplicaciones la precisión aritmética limitado, de los cómputos de la computadora y de los datos de entrada. El algoritmo del embalaje de regalo comienza con el i =0 y un p₀ del punto sabido para estar en el casco convexo, e., el punto extremo izquierdo, y selecciona el p_i+1 del punto tales que todos los puntos están a la derecha de la línea p_i p_i+1 . Este punto se puede encontrar el tiempo de O ( n ) comparando los ángulos polares de todos los puntos con respecto al p₀ del punto tomado para el centro de los coordenadas polares . Dejando el i = el i +1, y repitiéndolo con hasta que uno alcance el p_h = el p₀ rinde otra vez el casco convexo en pasos del h . El algoritmo del embalaje de regalo es exactamente análogo al proceso de enrollar una secuencia (o el papel de embalaje) alrededor del sistema de puntos.

jarvis del def (P) i = 0 p = punto extremo izquierdo de P hacer p = punto tales que el resto de los puntos en P están a derecho de la línea pp i = i + 1 ¡mientras que p! = p p de vuelta

El acercamiento es extensible a dimensiones más altas.