Geometría

Algoritmos geométricos

Algoritmo de Weiler-Atherton

Calcula el polígono recortado como la intersección del polígono de recorte y el polígono a recortar.Se puede aplicar a regiones arbitrarias de polígonos, no tiene problemas con los cóncavos.

Consiste en que en lugar de procesar siempre alrededor de las aristas del polígono como se preocesan los vertices, en ocasiones deseamos seguir la frontera de la ventana.

Por ejemplo, en sentido de las manecillas del reloj, para un par de vértices del polígono del exterior al interior de la ventana, seguimos la frontera del polígono y para un par del interior al exterior seguimos la frontera de la ventana en el sentido de las manecillas del reloj.

Algoritmo de Weiler-Atherton

^

Este algoritmo se ideó originalmente para determinar la visibilidad de polígonos. Sin embargo, también sirve para determinar la intersección de dos polígonos, lo que implica que este mismo algoritmo se puede aplicar para recortar un polígono en un polígono de recorte. La ventaja de este algoritmo, comparado con otros, es que sirve para recortar polígonos convexos o cóncavos en cualquier polígono de recorte que también puede ser convexo o cóncavo; incluso acepta polígonos con agujeros. El resultado de este algoritmo es uno o varios polígonos que representan las partes visibles e interiores al polígono de recorte. Se supone, para cada polígono, una lista de vértices ordenada en el sentido de las agujas del reloj para representar el exterior del polígono. Una ordenación en el sentido contrario de las agujas del reloj sirve para describir cualesquier agujeros que contenga el polígono.

La estrategia se basa en recorrer los vértices y aristas del polígono a recortar que sean interiores al polígono de recorte. Si la arista está a punto de salirse del polígono de recorte, entonces cambiamos el recorrido al polígono de recorte, para continuar con su lista de vértices y aristas. Esto sugiere que debemos determinar todos los puntos de intersección entre ambos polígonos, teniendo en cuenta cuáles son entrantes y cuáles son salientes. Aplicamos las siguientes reglas al llegar a un punto de intersección en nuestro recorrido:

• Entrante: Recorra el polígono a recortar.
• Saliente: Recorra el polígono de recorte.

Ambos recorridos se hacen en el sentido de las agujas del reloj.

Por lo tanto, el algoritmo se divide en dos partes principales consecutivas: el cálculo de todas las intersecciones y posteriormente el recorrido de todos los puntos, según las reglas descritas anteriormente, para generar los polígonos resultantes.

Para formar cada polígono recortado, comenzamos con un punto de intersección entrante, agregando los demás puntos recorridos según las reglas establecidas hasta reencontrar ese mismo punto de intersección del comienzo, así cerrando el polígono.

Como ocurre en el recorte, es posible que las aristas de ambos polígonos no se crucen y por tanto no existan puntos de intersección. Si esto ocurriere, tenemos tres posibles casos a considerar según el polígono a recortar, P, y el polígono de recorte, R:

• P es interior a R, por lo que el resultado es P.
• R es interior a P o que es lo mismo, P engloba R, por lo que el resultado es R.
• P y R son polígonos que no se intersectan entre sí, ni en las aristas ni en sus interiores y por tanto no existe ningún polígono recortado resultante.

Ejemplo

Descripción Figura 61 - Ejemplo Retomamos el mismo ejemplo del método de Sutherland-Hodgman y Liang-Barsky. Tenemos un polígono de recorte, R, cuya lista de vértices es: R : \ Queremos uno varios polígonos, en tal polígono de recorte, a partir del polígono, P, descrito por la siguiente lista de vértices: P : \

Solución Figura 62 - Calculamos todas las intersecciones Creamos una lista de polígonos, Q, que cada uno incluye una lista de vértices para representar los polígonos resultantes del recorte, inicialmente vacía: Q1 : \{} Antes de empezar el recorte de nuestro polígono, calculamos todos los puntos de intersección. Como tenemos que insertar estos puntos correctamente en las dos listas de vértices, P y R, para que ambas listas sigan el sentido de las agujas del reloj. Para realizar esta ordenación, calculamos y guardamos sus parámetros del segmento, t. Adicionalmente, necesitamos saber cuáles de estos puntos de intersección son entrantes (en rojo en la figura 62) y cuáles son salientes (en morado en la figura 62). Los puntos son: i1 = ( 0, 3 ) ⇐ t = 0,6666 (saliente) i2 = ( -1, 2 ) ⇐ t = 0,3333 (entrante) i3 = ( 3, 0 ) ⇐ t = 0 (entrante) i4 = (0,75, 3 ) ⇐ t = 0,75 (saliente) Insertamos estos puntos de intersección correctamente en cada lista de vértices. i1 e i2 deben insertarse correctamente entre los vértices P.v1 y P.v2. Comparando los parámetros de i1 e i2, determinamos que el orden correcto es: v1 i2 i1 v2 (-2,1), (-1,2), (0,3), (1,4) t=0 t=0,33 t=0,66 t=1 El resultando de todas las inserciones correctas en las listas de vértices de ambos polígonos es: P : \ R : \ Seguimos el recorrido, pero llegamos al punto i1 que es saliente. Según las reglas, debemos cambiar de lista de vértices para continuar el recorrido en R. Agregando este punto i1, por el momento, Q1 contiene la siguiente lista: Q1 : \

Figura 64 - Recorremos R Ahora, seguimos con el recorrido del polígono, R. Para ello, buscamos el punto de intersección saliente, i1, en la lista de R. Recorriendo R, nos encontramos con el vértice, R.r2, el cual agregamos a Q1. El siguiente punto es una intersección entrante, i3, por lo que debemos cambiar a la lista de vértices del polígono, P. Ahora la lista de vértices, Q1, es: Q1 : \

Figura 65 - Recorremos P Al saltar al polígono, P, buscamos el punto de intersección, i3. Siguiendo la lista de P, a partir de i3, nos encontramos con el punto de intersección saliente, i4, el cual agregamos a Q1. Como se trata de un punto de intersección saliente, debemos cambiar a la lista de vértices del polígono, R. Por ahora la lista de vértices, Q1, es: Q1 : \

Figura 66 - Recorremos R Con la lista de vértices, R, buscamos el punto de intersección, i4. Siguiendo la lista de R, a partir de i4, nos encontramos con el vértice original, R.r3, el cual agregamos a Q1. El siguiente punto en R es de intersección entrante, i1, que también se debería agregar a Q1, pero ya lo visitamos previamente; y por tanto, se agregó en una etapa anterior del algoritmo. Como se trata de un punto de intersección entrante, debemos cambiar a la lista de vértices del polígono, P. Terminamos la lista de vértices, Q1, que queda así: Q1 : \

Figura 67 - Solución Final Al terminar un polígono recortado, volvemos a comenzar el algoritmo con la lista de vértices, P. Buscamos el siguiente punto de intersección entrante que no hayamos visitado, ni por lo tanto hayamos agregado al polígono de recorte, previamente. Como todos los puntos entrantes han sido visitados y usados anteriormente, finalizamos el recorte, dando lugar al polígono resultante, Q, que queda así: Q : \

Algoritmo

El algoritmo hace uso de cierta información que agruparemos en la siguiente estructura especial, definida así:

PuntoInfo
\{
  real t;
  Punto vértice;
  booleano entrante;
}

Esta información se asociará a los puntos de intersección que calcularemos. Como el algoritmo debe distinguir entre un punto original de un polígono dado y un punto de intersección calculado, agregaremos una propiedad a Punto llamada original; si es verdadero, entonces se trata de un punto original, y falsoindicará que es una intersección. También agregamos otra propiedad a Punto llamada visitado; si es verdadero, entonces hemos procesado este punto en el algoritmo de la intersección, y falso indicará que aún está por procesar.

Presentamos el algoritmo para Recortar() que acepta cualquier tipo de polígono convexo o cóncavo cerrado:

ListaPolígonos Recortar( Polígono P, Polígono R )

Crear ListaPolígonos: Resultado ← vacía
P.Agregar( P.v[1] )  // Agregamos el primer vértice al final
R.Agregar( R.v[1] )
ExistenIntersecciones ← Calcular_Intersecciones( P, R )
Si ExistenIntersecciones = verdadero, entonces


Resultado ← Intersectar( P, R, Resultado )

Si no, entonces


ContienePunto ← Acepta( P, R.v[1] )
Si ContienePunto = verdadero, entonces


Resultado ← R

Si no, entonces


ContienePunto ← Acepta( R, P.v[1] )
Si ContienePunto = verdadero, entonces


Resultado ← P

Si no, entonces


Resultado ← vacía



Terminar( Resultado )

Exponemos el algoritmo de Calcular_Intersecciones() para calcular los puntos de intersección de las aristas entre los dos polígonos. Simultáneamente, agregamos estos puntos de intersección a los dos polígonos. Adicionalmente indicamos cuáles puntos son entrantes y cuáles son salientes.

booleano Calcular_Intersecciones( ref Polígono P, ref Polígono R )

ExistenIntersecciones ← falso
A ← P.v1
B ← Siguiente_Original( P, A )
Mientras que, B ≠ P.v1


C ← R.v1
D ← Siguiente_Original( R, C )
Mientras que, D ≠ R.v1, repetir


tp ← Calcular_Parámetro( A, B, C, D )
Si 0 ≤ tp ≤ 1, entonces


tr ← Calcular_Parámetro( C, D, A, B )
Si 0 ≤ tr ≤ 1, entonces


ExistenIntersecciones ← verdadero
nuevo.vértice ← A + tp*(B-A)
nuevo.vértice.original ← falso
nuevo.t ← tp
nuevo.entrante ← Es_Entrante( A, B, C, D )
Insertar( P, A, B, nuevo )
nuevo.t ← tr
Insertar( Q, C, D, nuevo )


C ← D
D ← Siguiente_Original( R, C )

A ← B
B ← Siguiente_Original( P, A )

Terminar( ExistenIntersecciones )

El algoritmo de Siguiente_Original() requiere un polígono y un punto que pertenece a tal polígono. Recorrerá todos los puntos en busca del siguiente que es un vértice - un punto original del polígono.

Punto Siguiente_Original( Polígono P, Punto A )

Resultado ← P.Siguiente( A )
Mientras que, Resultado.original = falso, repetir


Resultado ← P.Siguiente( Resultado )

Terminar( Resultado )

Hacemos uso del algoritmo básico Siguiente() que obtendrá el siguiente vértice en la lista que forma el polígono.

El algoritmo para Calcular_Parámetro() requiere los puntos extremos de cada segmento para calcular el valor del parámetro del primer segmento del punto de intersección de ambos segmentos.

real Calcular_Parámetro( Punto P0, Punto P1, Punto Q0, Punto Q1 )

N ← ( Q0y - Q1y, Q1x - Q0x )
numerador ← N⋅(P0 - Q0)
denominador ← -N⋅(P1 - P0)
Si denominador ≠ 0, entonces


t ← numerador / denominador

Si no, entonces


t ← ∞

Terminar( t )

He aquí el algoritmo de Es_Entrante(), que determina si el segmento, descrito por el vector U, es entrante (verdadero) al cruzar la arista descrita por el vector V. Esto implica que su punto de intersección, tambié es entrante.

booleano Es_Entrante( Vector U, Vector V )

N ← ( -Vy, Vx )
denominador ← N⋅U
Si denominador < 0, entonces


Terminar( verdadero )

Si no, entonces


Terminar( falso )

El siguiente algoritmo describe Insertar(), que acepta un polígono, dos puntos extremos de una arista, y el nuevo punto a insertar correctamente.

Insertar( ref Polígono P, Punto A, Punto B, PuntoInfo nuevo )

Actual ← A
Sig ← P.Siguiente( A )
terminar ← falso
Mientras que, terminar = falso  y  Sig.original = falso, repetir


Si nuevo.t < Sig.t, entonces


P.Insertar_Nuevo( Actual, nuevo )
terminar ← verdadero

Si no, entonces


Actual ← Sig
Sig ← P.Siguiente( Actual )

Resultado ← P.Siguiente( Resultado )

P.Insertar_Nuevo( Actual, nuevo )
Terminar

El algoritmo básico del polígono, Insertar_Nuevo(), sirve para agregar un nuevo punto a ello, justo después del punto indicado.

Exponemos el algoritmo de Intersectar() para determinar los polígonos de intersección entre dos polígonos dados.

ListaPolígonos Intersectar( Polígono P, Polígono R )

Crear ListaPolígonos: Actual ← \   // Actual[1] = P, Actual[2] = R
Crear ListaPolígonos: Resultado ← vacía
Crear Polígono: Auxiliar ← vacío
índice ← Buscar_Punto_Entrante_No_Visitado( P )
Mientras que, índice > 0, repetir


n ← 1
Mientras que, Actual[n].v[índice].visitado = falso, repetir


Actual[n].v[índice].visitado = verdadero
Auxiliar.Agregar( Actual[n].v[índice].vértice )
Si Actual[n].v[índice].original = falso, entonces


Si Actual[n].v[índice].entrante = falso, entonces  // Cambio de polígono


n_ant ← n
Si n = 1, entonces


n ← 2

Si no, entonces


n ← 1

índice ← Buscar_Punto( Actual[n], Actual[n_ant].v[índice].vértice )


índice ← índice + 1
Si índice > Actual[n].Cantidad_Vértices(), entonces


índice ← 1


Resultado.AgregarPolígono( Auxiliar )
Auxiliar.Vaciar()
índice ← Buscar_Punto_Entrante_No_Visitado( P )

Terminar( Resultado )

He aquí el algoritmo de Buscar_Punto_Entrante_No_Visitado() para encontrar el punto entrante sin marcar como visitado del polígono dado. El algoritmo retornará el índice al punto encontrado o 0 (cero), para indicar que no existe ninguno.

entero Buscar_Punto_Entrante_No_Visitado( Polígono P )

Para: índice ← 1 hasta P.Cantidad_Vértices(), repetir


Si P.v[índice].original = falso  y  Si P.v[índice].entrante = verdadero  y  Si P.v[índice].visitado = falso, entonces


Terminar( índice )


Terminar( 0 )

Presentamos el algoritmo de Buscar_Punto() para encontrar el punto indicado en el polígono dado. El algoritmo retornará el índice al punto encontrado o 0 (cero), para indicar que no se encontró.

entero Buscar_Punto( Polígono P, Punto I )

Para: índice ← 1 hasta P.Cantidad_Vértices(), repetir


Si P.v[índice].vértice = I, entonces


Terminar( índice )


Terminar( 0 )