El escaneo de Graham es un método para encontrar la envoltura convexa de un conjunto finito de puntos en el plano con complejidad temporal O ( n log n ). Recibe su nombre en honor a Ronald Graham , quien publicó el algoritmo original en 1972. [1] El algoritmo encuentra todos los vértices de la envoltura convexa 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 de todos los candidatos. Llamemos 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 del ángulo que forman con el eje x. Cualquier algoritmo de ordenamiento de propósito general es adecuado para esto, por ejemplo, heapsort (que es O( n log n )).
La clasificación por 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 línea. Si la precisión numérica está en juego, la función de comparación utilizada por el algoritmo de clasificación puede utilizar el signo del producto vectorial para determinar los ángulos relativos.
Si varios puntos tienen el mismo ángulo, rompa los empates aumentando la distancia ( se puede usar la distancia de Manhattan o de Chebyshev en lugar de la euclidiana para facilitar el cálculo, ya que los puntos se encuentran en el mismo rayo) o elimine todos los puntos excepto el más alejado.
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 es un giro a la derecha, el segundo punto desde el último no forma parte de la envoltura convexa y se encuentra "dentro" de ella. Luego se realiza la misma determinación para el conjunto del último punto y los dos puntos que preceden inmediatamente al punto que se encontró que estaba dentro de la envoltura, y se repite hasta que se encuentra un conjunto de "giro a la izquierda", momento en el cual el algoritmo pasa al siguiente punto en el conjunto de puntos de la matriz ordenada menos los puntos que se encontraron dentro de la envoltura; no hay necesidad de considerar estos puntos nuevamente. (Si en cualquier etapa los tres puntos son colineales, se puede optar por descartarlo o informarlo, ya que en algunas aplicaciones se requiere encontrar todos los puntos en el límite de la envoltura convexa).
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 solo con aritmética simple. Para tres puntos , y , calcule la coordenada z del producto vectorial de los dos vectores y , que se da 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" o una orientación en el sentido horario (para puntos numerados en sentido antihorario).
Este proceso eventualmente regresará al punto en el que comenzó, momento en el cual el algoritmo se completa y la pila ahora contiene los puntos en la envoltura convexa en orden antihorario.
La ordenación de los puntos tiene una complejidad temporal de O( n log n ). Si bien puede parecer que la complejidad temporal del bucle es O( n 2 ), porque para cada punto se vuelve a comprobar 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 se elimina el punto ). Por lo tanto, la complejidad temporal general es O( n log n ), ya que el tiempo para ordenar domina el tiempo para calcular realmente la envoltura convexa.
El pseudocódigo que se muestra a continuación utiliza una función ccw: ccw > 0 si tres puntos giran en sentido antihorario, ccw < 0 si giran en sentido horario y ccw = 0 si son colineales. (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 en el caso de puntos "casi" colineales).
Luego deje que el resultado se almacene en el stack.
sea puntos la lista de puntos sea pila = pila_vacía()Encuentra la coordenada y más baja y el punto más a la izquierda, llamado P0. Ordena los puntos por ángulo polar con P0, si varios puntos tienen el mismo ángulo polar, entonces solo conserva el más alejado.Para 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 mientras la pila de conteo > 1 y ccw (next_to_top(pila), top(pila), punto) <= 0: saca la pila y empuja el punto al final de la pila
Ahora la pila contiene la envoltura convexa, donde los puntos están orientados en sentido antihorario y P0 es el primer punto.
Aquí next_to_top()se encuentra una función para devolver el elemento que se encuentra una entrada debajo de la parte superior de la pila, sin cambiar la pila, y de manera similar, top()para devolver el elemento más alto.
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 el escaneo de Graham. [3]
La descripción original de Graham implicaba ordenar alrededor de un punto interior de la envoltura convexa , en lugar de uno de sus vértices. [1] Para la misma elección de un punto pivote para el algoritmo de ordenamiento, conectar todos los demás puntos en su orden ordenado 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 de la entrada. [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 utilizar algoritmos paralelos para todos los valores más pequeños más cercanos (como el escaneo de Graham) para calcular envolturas convexas de secuencias ordenadas de puntos de manera eficiente. [5]
La robustez numérica es un problema que se debe abordar en algoritmos que utilizan aritmética computacional 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. [6] El objetivo declarado del artículo no era analizar específicamente el algoritmo, sino más bien proporcionar un ejemplo clásico 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 la envoltura convexa 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 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)
