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. [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.
Algoritmo
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 usar el signo del producto cruzado para determinar los ángulos relativos.
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. 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. Por 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 sentido antihorario, de lo contrario un "giro a la derecha" o una orientación en el sentido de las agujas del reloj (para puntos numerados en sentido antihorario).
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 en sentido 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 2 ), 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 eso), y como punto en un "giro a la derecha" (porque el punto es removido). 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.
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
.
deje que los puntos sean la lista de puntos let stack = empty_stack ()encuentre la coordenada y más baja y el punto más a la izquierda, llamados puntos de clasificación P0 por ángulo polar con P0, si varios puntos tienen el mismo ángulo polar, entonces solo mantenga el más alejadopor punto en puntos: # saca el último punto de la pila si giramos en el sentido de las agujas del reloj para llegar a este punto mientras recuento pila> 1 y CCW (next_to_top (pila), superior (pila), punto) <= 0: pop pila empuje punto a pila final
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 [2] y se conoce como el algoritmo de cadena monótona de Andrew . Tiene las mismas propiedades básicas que el escaneo de Graham. [3]
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. [4]
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. [5] 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 . [5] Posteriormente D. Jiang y NF Stewart [6] 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 a la que llaman Graham-Fortune (que incorpora las ideas de Steven Fortune para la estabilidad numérica [7] ) supera los problemas de precisión finita y datos inexactos "en la medida en que sea posible hacerlo". .
Ver también
Referencias
- ^ Graham, RL (1972). "Un algoritmo eficiente para determinar el casco convexo de un conjunto plano finito" (PDF) . Cartas de procesamiento de información . 1 (4): 132-133. doi : 10.1016 / 0020-0190 (72) 90045-2 .
- ^ Andrew, AM (1979). "Otro algoritmo eficiente para cascos convexos en dos dimensiones". Cartas de procesamiento de información . 9 (5): 216–219. doi : 10.1016 / 0020-0190 (79) 90072-3 .
- ^ De Berg, Mark; Cheong, Otfried; Van Kreveld, Marc; Overmars, Mark (2008). Algoritmos y aplicaciones de geometría computacional . Berlín: Springer . págs. 2 –14. doi : 10.1007 / 978-3-540-77974-2 . ISBN 978-3-540-77973-5.
- ^ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993). "Óptimos algoritmos paralelos logarítmicos dobles basados en encontrar todos los valores más pequeños más cercanos". Revista de algoritmos . 14 (3): 344–370. CiteSeerX 10.1.1.55.5669 . doi : 10.1006 / jagm.1993.1018 ..
- ^ a b Kettner, Lutz; Mehlhorn, Kurt; Pion, Sylvain; Schirra, Stefan; Yap, Chee (2008). "Ejemplos de aula de problemas de robustez en cálculos geométricos" (PDF) . Geometría computacional . 40 (1): 61–78. doi : 10.1016 / j.comgeo.2007.06.003 . (Una versión anterior se informó en 2004 en ESA'2004)
- ^ D. Jiang y NF Stewart, Análisis de errores hacia atrás en geometría computacional Archivado 2017-08-09 en Wayback Machine , Computational Science and Its Applications - ICCSA 2006 Volumen 3980 de la serie Lecture Notes in Computer Science , pp 50-59
- ^ Fortune, S. Mantenimiento estable de triangulaciones de conjuntos de puntos en dos dimensiones. Actas del trigésimo simposio anual de IEEE sobre fundamentos de la informática vol. 30, 494-499, 1989.
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.