Para comprender la lógica de Graham Scan, debemos entender qué es Convex Hull:
¿Qué es el casco convexo?
Si tiene algunas uñas pegadas en un escritorio al azar y toma una banda elástica y se estira sobre todas las uñas. El límite formado naturalmente será un límite convexo. (El ángulo interno en cualquier punto no excede [matemática] 180 ° [/ matemática]).
- ¿Cuál es la forma más rápida (estructura de datos) para buscar la matriz multidimensional?
- ¿Existe algún libro de estructuras de datos y algoritmos en C ++ (tiene código fuente completo en C ++) disponible de forma gratuita en Internet?
- ¿Cuáles son las aplicaciones de la programación en C?
- ¿Por qué la agrupación aleatoria al iterar sobre ella y cambiarla por un elemento aleatorio entre 0 y el último elemento de la matriz no produce una barajadura distribuida uniformemente?
- Programación de computadoras: Como ingeniero de software, ¿qué cosas crees que son "innecesariamente complicadas"?
La propiedad de este límite será que tendrá todos los demás puntos en el límite o dentro del límite.
Más formalmente,
Un casco convexo de un conjunto de puntos [matemática] X_ {i} \ en Q [/ matemática], de modo que es el conjunto convexo más pequeño que contiene [matemática] Q [/ matemática].
Algoritmo de escaneo de Graham
El algoritmo de escaneo de Graham primero elige un punto. Principalmente es un punto que tiene el valor más bajo del eje Y en el plano cartesiano (en caso de empate, elegimos el que tenga el valor más bajo del eje X.
La pregunta es ¿por qué? Por qué elegir un punto que es más bajo en el eje Y La razón es que este punto es seguro que estará en el límite (ver la imagen nuevamente).
Entonces, más formalmente, el escaneo Graham comienza con un punto que está en el límite del casco. Llamemos a este punto [matemáticas] P [/ matemáticas].
Este paso toma [matemáticas] O (n) [/ matemáticas], donde [matemáticas] n [/ matemáticas] es el número de puntos en cuestión.
Luego, el conjunto de puntos debe ordenarse en orden creciente del ángulo que ellos y el punto [matemático] P [/ matemático] forman con el eje x. Cualquier algoritmo de clasificación de propósito general es apropiado para esto, por ejemplo, heapsort (que es [math] O (n log n) [/ math]).
La pregunta aquí es ¿por qué estamos ordenando los puntos de acuerdo con el ángulo? Esto está oculto en el hecho de que elegimos el punto más bajo y el más a la izquierda. Entonces, cuando los puntos se ordenan según el ángulo con el eje x. Mientras escaneamos, pasaremos por cada punto y determinaremos si el punto puede estar en el límite o no.
La clasificación en orden de ángulo no requiere calcular el ángulo. Es posible utilizar cualquier función del ángulo que sea monotónica en el intervalo [matemática] [0, Ï €] {\ displaystyle [0, \ pi]} [/ matemática]. El coseno se calcula fácilmente usando el producto de puntos, o se puede usar 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 usar el signo del producto cruzado para determinar los ángulos relativos.
El algoritmo procede considerando cada uno de los puntos en 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.
Fig: 2 [1] Como se puede ver, PAB y ABC son en sentido antihorario, pero BCD no. El algoritmo detecta esta situación y descarta los segmentos previamente elegidos hasta que el turno tomado sea en sentido antihorario (ABD en este caso).
Luego se hace la misma determinación para el conjunto del último punto y los dos puntos que preceden inmediatamente al punto encontrado dentro del casco, y se repite hasta que se encuentra un conjunto de “giro a la izquierda”, momento en el cual el algoritmo se mueve al siguiente punto en el conjunto de puntos en la matriz ordenada menos cualquier punto que se encuentre dentro del casco; no hay necesidad de considerar estos puntos nuevamente.
Esta es la intuición detrás del Graham Scan. A continuación se muestra un pseudocódigo para el mismo: [2]
Entrada: un conjunto de puntos S = {P = (Px, Py)}
Seleccione el punto más bajo más a la derecha P0 en S
Ordenar S radialmente (ccw) sobre P0 como centro
{
Utilice las comparaciones isLeft ()
Para los empates, descarte los puntos más cercanos
}
Sea P [N] el conjunto ordenado de puntos con P [0] = P0
Empuje P [0] y P [1] en una pila
mientras yo <N
{
Deje PT1 = el punto superior en
If (PT1 == P [0]) {
Presione P [i] en
i ++ // incremento i
}
Deje PT2 = el segundo punto superior en
Si (P [i] queda estrictamente a la izquierda de la línea PT2 a PT1) {
Presione P [i] en
i ++ // incremento i
}
más
Saque el punto superior PT1 de la pila
}
Salida: O = el casco convexo de S.
Espero que ayude.
Salud.
Notas al pie
[1] Archivo: Graham Scan.svg – Wikipedia
[2] El casco convexo de un conjunto de puntos planos
