Algoritmo de Jarvis

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 19 de enero de 2015; las comprobaciones requieren 9 ediciones .

El algoritmo de Jarvis (o el algoritmo transversal de Jarvis, o el algoritmo de envoltorio de regalo) determina una secuencia de elementos del conjunto que forman un casco convexo para este conjunto. El método se puede imaginar como envolver un conjunto de clavos clavados en una tabla con una cuerda. El algoritmo se ejecuta en el tiempo , donde es el número total de puntos en el plano, es el número de puntos en el casco convexo. $O(nh)$ $norte$ $h$

Descripción del algoritmo

Sea dado un conjunto de puntos . El punto inferior más a la izquierda se toma como punto inicial (se puede encontrar detrás del paso habitual a través de todos los puntos), es exactamente la parte superior del casco convexo. El siguiente punto ( ) es el punto que tiene el ángulo polar positivo más pequeño en relación con el punto como origen. Después de eso, para cada punto (2<i<=|P|) en sentido contrario a las agujas del reloj, dicho punto se busca encontrando más allá entre los puntos restantes (+ el más bajo a la izquierda), en el que el ángulo más grande entre las líneas y será formado Será el siguiente vértice del casco convexo. En este caso no se busca el ángulo en sí, sino sólo su coseno a través del producto escalar entre los rayos y , donde se encuentra el último mínimo, es el mínimo anterior, y es el candidato a mínimo siguiente. El nuevo mínimo será el punto en el que el coseno tomará el menor valor (cuanto menor sea el coseno, mayor será su ángulo). Encontrar los vértices del casco convexo continúa hasta . En ese momento, cuando el siguiente punto en el casco convexo coincide con el primero, el algoritmo se detiene: se construye el casco convexo. $P=\{\,p_{1},p_{2},\ldots,p_{n}\,\}$ $p_{1}$ $En)$ $p_{2}$ $p_{1}$ $Pi}$ $p_{{yo+1}}$ $En)$ $p_{{i-1}}p_{{i}}$ $p_{{i}}p_{{i+1}}$ $p_{{i-1}}p_{{i}}$ $p_{{i}}p'_{{i+1}}$ $Pi}}$ $p_{{i-1}}$ $p'_{{i+1}}$ $p_{{i+1}}\neq p_{1}$

Pseudocódigo

Jarvis (P) 1) p[1] = el punto inferior más a la izquierda del conjunto P; 2) p[2] = punto vecino de p[1] a la derecha (ubicado a través del ángulo polar positivo mínimo) 3) yo = 2; 4) hacer : (a) para cada punto j de 1 a |P|, excepto para aquellos que ya están en el casco convexo, pero incluyendo p[1] p[i+1] = punto_con_min_cos(p[i-1], p[i], P[j]); //punto que forma el coseno mínimo con la línea p[i-1]p[i], (b) i = i + 1; mientras que p[i] != p[1] 5) devolver p;

Análisis

El bucle (4) se ejecutará una vez, mientras que el bucle (a) se ejecutará cada vez durante . Todas las demás operaciones se realizan en formato . Por lo tanto, el algoritmo funciona para o en el peor de los casos, cuando todos los puntos caen en el casco convexo. $h$ $\Theta(n)$ $O(1)$ $\ Theta (hn)$ $\Theta (n^{2})$

Véase también

algoritmo de Graham
algoritmo de Chan

Literatura

Preparata F., Shaimos M. Geometría computacional Una introducción. — M .: Mir, 1989. — 478 p.
Laszlo M. Geometría computacional y gráficos por computadora en C++. - M. : BINOM, 1997. - 304 p.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmos. Construcción y Análisis = Introducción a los Algoritmos. - 2ª ed. - "Williams", 2005. - 1296 p.

Enlaces

implementación c++