Escaneo de Graham - Graham scan

Una demostración del escaneo de Graham para encontrar un casco convexo 2D.

El escaneo de Graham es un método para encontrar el casco convexo de un conjunto finito de puntos en el plano con complejidad de tiempo O ( n log n ). Lleva el nombre de Ronald Graham , quien publicó el algoritmo original en 1972. El algoritmo encuentra todos los vértices del casco convexo ordenados a lo largo de su límite. Utiliza una pila para detectar y eliminar concavidades en el límite de manera eficiente.

Algoritmo

Como se puede ver, PAB y ABC van en sentido contrario a las agujas del reloj, pero BCD no. El algoritmo detecta esta situación y descarta los segmentos previamente elegidos hasta que el giro tomado es en sentido antihorario (ABD en este caso).

El primer paso en este algoritmo es encontrar el punto con la coordenada y más baja. Si la coordenada y más baja existe en más de un punto del conjunto, se debe elegir el punto con la coordenada x más baja de los candidatos. Llame a este punto P . Este paso toma O ( n ), donde n es el número de puntos en cuestión.

A continuación, el conjunto de puntos debe ordenarse en orden creciente según el ángulo que ellos y el punto P forman con el eje x. Cualquier algoritmo de clasificación de propósito general es apropiado para esto, por ejemplo heapsort (que es O ( n log n )).

La clasificación en orden de ángulo no requiere calcular el ángulo. Es posible utilizar cualquier función del ángulo que sea monótona en el intervalo . El coseno se calcula fácilmente usando el producto escalar , o se puede usar la pendiente de la línea. Si está en juego la precisión numérica, la función de comparación utilizada por el algoritmo de clasificación puede utilizar el signo del producto cruzado para determinar los ángulos relativos. ${\ Displaystyle [0, \ pi]}$

El algoritmo procede considerando cada uno de los puntos de la matriz ordenada en secuencia. Para cada punto, primero se determina si viajar desde los dos puntos inmediatamente anteriores a este punto constituye un giro a la izquierda o un giro a la derecha. Si gira a la derecha, el penúltimo punto no forma parte del casco convexo y se encuentra "dentro" de él. Luego se hace la misma determinación para el conjunto del último punto y los dos puntos que preceden inmediatamente al punto que se encuentra dentro del casco, y se repite hasta que se encuentra un conjunto de "giro a la izquierda", momento en el que el algoritmo avanza. al siguiente punto en el conjunto de puntos en la matriz ordenada menos los puntos que se encontraron dentro del casco; No es necesario volver a considerar estos puntos. (Si en alguna etapa los tres puntos son colineales, se puede optar por descartarlos o informarlos, ya que en algunas aplicaciones se requiere encontrar todos los puntos en el límite del casco convexo).

Nuevamente, determinar si tres puntos constituyen un "giro a la izquierda" o un "giro a la derecha" no requiere calcular el ángulo real entre los dos segmentos de línea, y en realidad se puede lograr con aritmética simple solamente. Para tres puntos , y , calcule la coordenada z del producto cruzado de los dos vectores y , que viene dada por la expresión . Si el resultado es 0, los puntos son colineales; si es positivo, los tres puntos constituyen un "giro a la izquierda" o una orientación en sentido antihorario, de lo contrario un "giro a la derecha" u orientación en el sentido de las agujas del reloj (para puntos numerados en sentido antihorario). ${\ Displaystyle P_ {1} = (x_ {1}, y_ {1})}$${\ Displaystyle P_ {2} = (x_ {2}, y_ {2})}$${\ Displaystyle P_ {3} = (x_ {3}, y_ {3})}$ ${\ displaystyle {\ overrightarrow {P_ {1} P_ {2}}}}$${\ displaystyle {\ overrightarrow {P_ {1} P_ {3}}}}$${\ Displaystyle (x_ {2} -x_ {1}) (y_ {3} -y_ {1}) - (y_ {2} -y_ {1}) (x_ {3} -x_ {1})}$

Este proceso eventualmente regresará al punto en el que comenzó, momento en el cual se completa el algoritmo y la pila ahora contiene los puntos en el casco convexo en orden antihorario.

Complejidad del tiempo

La clasificación de los puntos tiene una complejidad temporal O ( n log n ). Si bien puede parecer que la complejidad de tiempo del bucle es O ( n ² ), porque para cada punto retrocede para verificar si alguno de los puntos anteriores hace un "giro a la derecha", en realidad es O ( n ), porque cada punto se considera como máximo dos veces en algún sentido. Cada punto puede aparecer solo una vez como un punto en un "giro a la izquierda" (porque el algoritmo avanza al siguiente punto después de ese), y como un punto en un "giro a la derecha" (porque el punto se elimina). Por lo tanto, la complejidad del tiempo total es O ( n log n ), ya que el tiempo para clasificar domina el tiempo para calcular realmente el casco convexo. ${\ Displaystyle (x_ {2}, y_ {2})}$${\ Displaystyle (x_ {3}, y_ {3})}$${\ Displaystyle (x_ {2}, y_ {2})}$${\ Displaystyle (x_ {2}, y_ {2})}$

Pseudocódigo

El siguiente código usa una función ccw: ccw> 0 si tres puntos hacen un giro en sentido antihorario, en sentido horario si ccw <0 y colineal si ccw = 0. (En aplicaciones reales, si las coordenadas son números reales arbitrarios, la función requiere comparación exacta de números de punto flotante, y hay que tener cuidado con las singularidades numéricas de los puntos "casi" colineales).

Luego, deje que el resultado se almacene en el archivo stack.

let points be the list of points
let stack = empty_stack()

find the lowest y-coordinate and leftmost point, called P0
sort points by polar angle with P0, if several points have the same polar angle then only keep the farthest

for point in points:
    # pop the last point from the stack if we turn clockwise to reach this point
    while count stack > 1 and ccw(next_to_top(stack), top(stack), point) <= 0:
        pop stack
    push point to stack
end

Ahora la pila contiene el casco convexo, donde los puntos están orientados en sentido antihorario y P0 es el primer punto.

Aquí, next_to_top()hay una función para devolver el elemento una entrada por debajo de la parte superior de la pila, sin cambiar la pila, y de manera similar, top()para devolver el elemento superior.

Este pseudocódigo está adaptado de Introducción a los algoritmos .

Notas

La misma idea básica funciona también si la entrada se ordena en la coordenada x en lugar del ángulo, y el casco se calcula en dos pasos produciendo las partes superior e inferior del casco respectivamente. Esta modificación fue ideada por AM Andrew y se conoce como el algoritmo de cadena monótona de Andrew . Tiene las mismas propiedades básicas que el escaneo de Graham.

La técnica de pila utilizada en el escaneo de Graham es muy similar a la del problema de todos los valores más pequeños más cercanos , y también se pueden usar algoritmos paralelos para todos los valores más cercanos más pequeños (como el escaneo de Graham) para calcular cascos convexos de secuencias ordenadas de puntos de manera eficiente.

Robustez numérica

La robustez numérica es un problema a tratar en los algoritmos que utilizan aritmética informática de punto flotante de precisión finita . Un artículo de 2004 analizó una estrategia incremental simple, que se puede utilizar, en particular, para una implementación del escaneo de Graham. El objetivo declarado del artículo no era analizar específicamente el algoritmo, sino más bien proporcionar un ejemplo de libro de texto de qué y cómo puede fallar debido a cálculos de punto flotante en geometría computacional . Más tarde, D. Jiang y NF Stewart desarrollaron esto y, utilizando el análisis de errores hacia atrás, llegaron a dos conclusiones principales. La primera es que el casco convexo es un problema bien condicionado y, por lo tanto, se pueden esperar algoritmos que produzcan una respuesta dentro de un margen de error razonable. En segundo lugar, demuestran que una modificación del escaneo de Graham al que llaman Graham-Fortune (que incorpora ideas de Steven Fortune para la estabilidad numérica) supera los problemas de precisión finita y datos inexactos "en la medida en que sea posible".

Ver también

• Algoritmos de casco convexo

Referencias

Otras lecturas

• 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. 949–955. ISBN 0-262-03293-7.