En geometría computacional , el algoritmo de envoltura de regalo es un algoritmo para calcular el casco convexo de un conjunto dado de puntos.
Caso plano
En el caso bidimensional, el algoritmo también se conoce como marcha de Jarvis , en honor a RA Jarvis, que lo publicó en 1973; tiene una complejidad de tiempo O ( nh ) , donde n es el número de puntos y h es el número de puntos en el casco convexo. Su rendimiento en la vida real en comparación con otros algoritmos de casco convexo es favorable cuando n es pequeño o se espera que h sea muy pequeño con respecto a n [ cita requerida ] . En casos generales, el algoritmo es superado por muchos otros (Ver algoritmos de casco convexo ).
Algoritmo
En aras de la simplicidad, la descripción siguiente asume que los puntos están en posición general , es decir, no hay tres puntos colineales . El algoritmo se puede modificar fácilmente para lidiar con la colinealidad, incluida la elección de si debe informar solo los puntos extremos (vértices del casco convexo) o todos los puntos que se encuentran en el casco convexo [ cita requerida ] . Además, la implementación completa debe tratar [ ¿cómo? ] con casos degenerados cuando el casco convexo tiene sólo 1 o 2 vértices, así como con los problemas de precisión aritmética limitada , tanto de cálculos de computadora como de datos de entrada.
El algoritmo de envoltura de regalo comienza con i = 0 y un punto p 0 que se sabe que está en el casco convexo, por ejemplo, el punto más a la izquierda, y selecciona el punto p i + 1 de manera que todos los puntos estén a la derecha de la línea p i p yo + 1 . Este punto se puede encontrar en O ( n ) tiempo comparando los ángulos polares de todos los puntos con respecto al punto p i tomado para el centro de las coordenadas polares . Dejando i = i +1, y repitiendo con hasta que se alcance p h = p 0 nuevamente, se obtiene el casco convexo en h pasos. En dos dimensiones, el algoritmo para envolver regalos es similar al proceso de enrollar una cuerda (o papel de envolver) alrededor del conjunto de puntos.
El enfoque puede extenderse a dimensiones superiores.
Pseudocódigo
algoritmo jarvis (S) es // S es el conjunto de puntos // P será el conjunto de puntos que forman el casco convexo. El tamaño final del conjunto es i. pointOnHull = punto más a la izquierda en S // que se garantiza que es parte del CH (S) yo: = 0 repetir P [i]: = pointOnHull punto final: = S [0] // punto final inicial para un borde candidato en el casco para j de 0 a | S | hacer // endpoint == pointOnHull es un caso raro y puede suceder solo cuando j == 1 y aún no se ha establecido un punto final mejor para el bucle si (punto final == pointOnHull) o (S [j] está a la izquierda de la línea desde P [i] hasta el punto final) entonces punto final: = S [j] // encontrado mayor giro a la izquierda, actualizar punto final yo: = yo + 1 pointOnHull = punto final hasta el punto final = P [0] // envuelto alrededor del primer punto del casco
Complejidad
El bucle interior comprueba todos los puntos del conjunto S , y el bucle exterior se repite para cada punto del casco. Por lo tanto, el tiempo de ejecución total es. 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 quealgoritmos como Graham escanean cuando el número h de vértices del casco es menor que log n . El algoritmo de Chan , otro algoritmo de casco convexo, combina la dependencia logarítmica del escaneo de Graham con la sensibilidad de salida del algoritmo de envoltura de regalo, logrando un tiempo de ejecución asintótico. que mejora tanto el escaneado Graham como el envoltorio de regalo.
Ver también
Referencias
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "33.3: Encontrar el casco convexo". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 955–956. ISBN 0-262-03293-7.
- Jarvis, RA (1973). "Sobre la identificación del casco convexo de un conjunto finito de puntos en el plano". Cartas de procesamiento de información . 2 : 18-21. doi : 10.1016 / 0020-0190 (73) 90020-3 .