El escaneo de Graham es un método para encontrar el casco convexo de un conjunto finito de puntos en el plano con complejidad temporal O ( n log n ). Lleva el nombre de Ronald Graham , quien publicó el algoritmo original en 1972. [1] 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.
El primer paso de 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 entre los candidatos. Llame a este punto P . Este paso requiere O ( n ), donde n es el número de puntos en cuestión.
A continuación, se debe ordenar el conjunto de puntos en orden creciente del ángulo que forman y el punto P 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 )).
Ordenar 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 utilizando el producto escalar o se puede utilizar la pendiente de la recta. 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.
Si varios puntos tienen el mismo ángulo, rompa los vínculos aumentando la distancia ( se puede usar la distancia de Manhattan o Chebyshev en lugar de la euclidiana para facilitar el cálculo, ya que los puntos se encuentran en el mismo rayo), o elimine todos menos el punto más lejano.
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 a la derecha. Si se 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 cual el algoritmo continúa. al siguiente punto del conjunto de puntos de la matriz ordenada menos cualquier punto que se encuentre dentro del casco; No es necesario volver a considerar estos puntos. (Si en algún momento los tres puntos son colineales, se puede optar por descartarlo o informarlo, ya que en algunas aplicaciones es necesario 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, sólo se puede lograr con aritmética simple. Para tres puntos , y , calcula 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 el sentido contrario a las agujas del reloj; de lo contrario, un "giro a la derecha" o una orientación en el sentido de las agujas del reloj (para puntos numerados en el sentido contrario a las agujas del reloj).
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.
Ordenar los puntos tiene una complejidad temporal O ( n log n ). Si bien puede parecer que la complejidad temporal del bucle es O( n 2 ), porque para cada punto vuelve a comprobar si alguno de los puntos anteriores hace un "giro a la derecha", en realidad es O( n ), porque cada El punto se considera como máximo dos veces en algún sentido. Cada punto puede aparecer sólo una vez como un punto en un "giro a la izquierda" (porque el algoritmo avanza al siguiente punto después de eso) y como un punto en un "giro a la derecha" (porque el punto se elimina). Por lo tanto, la complejidad temporal general es O ( n log n ), ya que el tiempo para ordenar domina el tiempo para calcular realmente el casco convexo.
El pseudocódigo siguiente utiliza una función ccw: ccw > 0 si tres puntos giran en el sentido contrario a las agujas del reloj, ccw < 0 si es en el sentido de las agujas del reloj y ccw = 0 si es colineal. (En aplicaciones reales, si las coordenadas son números reales arbitrarios, la función requiere una comparación exacta de números de punto flotante, y hay que tener cuidado con las singularidades numéricas para puntos "casi" colineales).
Luego deje que el resultado se almacene en el archivo stack.
deje que los puntos sean la lista de puntos deje que la pila = vacía_pila ()encuentre la coordenada y más baja y el punto más a la izquierda, llamado P0, ordene los puntos por ángulo polar con P0, si varios puntos tienen el mismo ángulo polar, entonces solo mantenga el más lejanopara punto en puntos: # sacamos el último punto de la pila si giramos en el sentido de las agujas del reloj para llegar a este punto while count stack > 1 and ccw (next_to_top(stack), top(stack), point) <= 0: pop stack empuja el punto hasta el final de la pila
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 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 .
La misma idea básica funciona también si la entrada se ordena según 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. [2] Tiene las mismas propiedades básicas que la exploración de Graham. [3]
La descripción original de Graham implicaba clasificar alrededor de un punto interior del casco convexo , en lugar de uno de sus vértices. [1] Para la misma elección de un punto de pivote para el algoritmo de clasificación, conectar todos los demás puntos en su orden de clasificación alrededor de este punto en lugar de realizar los pasos restantes del escaneo de Graham produce un polígono en forma de estrella , una poligonalización del aporte. [4]
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 pequeños más cercanos (como el escaneo de Graham) para calcular cascos convexos de secuencias ordenadas de puntos de manera eficiente. [5]
La robustez numérica es un problema que hay que abordar 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 puede usarse, en particular, para una implementación del escaneo de Graham. [6] 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 los cálculos de punto flotante en geometría computacional . [6] Más tarde, D. Jiang y NF Stewart [7] profundizaron en esto y, utilizando el análisis de error hacia atrás, llegaron a dos conclusiones principales. La primera es que el casco convexo es un problema bien condicionado y, por 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 a la que llaman Graham-Fortune (que incorpora ideas de Steven Fortune para la estabilidad numérica [8] ) supera los problemas de precisión finita y datos inexactos "en la medida en que sea posible hacerlo". .
![{\displaystyle [0,\pi ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e2a912eda6ef1afe46a81b518fe9da64a832751)
