Capítulo 7 - Recorte

Siguiendo nuestro modelado en dos dimensiones, hablaremos de una operación importante acerca de líneas y polígonos. El recorte (o clipping, en inglés) modifica las líneas y polígonos a visualizar debidos a una región que los limita. Técnicamente, se trata de una intersección de dos entidades geométricas. Típicamente, la región de recorte es un rectángulo vertical, cuyos lados son paralelos a los ejes del sistema de coordenadas, que suele representar la vista de nuestra escena o la pantalla en sí.

Existen varios algoritmos y métodos para hacer el recorte. Por ahora, sólo miraremos aquellas técnicas analíticas. Esto significa que aplicaremos la operación de recorte a nuestro modelo en nuestro sistema de coordenadas matemático de nuestro mundo y escena. Existen otros métodos de recorte que se pueden aplicar en la etapa de conversión del modelo a píxeles. Trataremos estas técnicas en posteriores capítulos.

Veremos varios métodos para varios casos de recorte, como son el recorte de líneas y polígonos en un rectángulo vertical, al igual que en una región de recorte descrita por un polígono.

Recortando Líneas

Realmente, no pretendemos recortar líneas sino más bien segmentos. Como un segmento se describe por sus puntos extremos, no tenemos que consultar la infinidad de puntos que componen tal segmento.

De la misma manera que analizamos el recorte de puntos individuales, podemos aplicar la misma lógica para los puntos extremos de un segmento. El resultado es cuatro casos diferentes. Si ambos extremos están dentro del rectángulo de recorte, entonces no tenemos que hacer nada más que aceptar el segmento. Si un extremo está dentro y el otro fuera del rectángulo, entonces el segmento cruza uno de los lados de la región de recorte. Tenemos que calcular el punto de intersección lo cual modificará el extremo del segmento externo para que sea interno al rectángulo de recorte. Si ambos extremos están fuera del rectángulo de recorte, entonces el segmento puede estar completamente fuera del rectángulo, por lo que es rechazado inmediatamente. Sin embargo, tal segmento podría cruzar dos lados del rectángulo. En este caso, tenemos que realizar dos cálculos de intersección, modificando ambos extremos del segmento para que éste sea interior al rectángulo de recorte.

Veremos varios algoritmos para solucionar este problema: Algoritmo Exhaustivo, Algoritmo de Cohen-Sutherland, Algoritmo de Cyrus-Beck, Algoritmo de Liang-Barsky, y Algoritmo de Nicholl-Lee-Nicholl.

Recortando Polígonos

Lo normal es que nuestra escena contenga varios polígonos y no segmentos sueltos. Como nuestra vista limita el contenido de la escena que podemos mostrar, tendremos que recortar los polígonos de la escena para eliminarlos de la vista o dibujarlos parcial o completamente. Como representamos los polígonos mediante los segmentos que forman sus aristas, al recortar los polígonos en un rectángulo, acabaremos eliminando, aceptando, o recortando las aristas existentes y posiblemente añadiendo nuevas. Los diferentes resultados dependen del tipo de polígono a recortar.

Un polígono convexo que intersecta un rectángulo dará lugar a un polígono convexo. Un polígono cóncavo recortado por un rectángulo puede resultar en uno o varios polígonos cóncavos o convexos.

Veremos varios algoritmos para recortar polígonos: Algoritmo de Sutherland-Hodgman, Algoritmo de Liang-Barsky, y Algoritmo de Weiler-Atherton.

Recortando Puntos

Veamos el problema sencillo de recortar puntos. Para este caso, sólo necesitamos aceptar o rechazar tal punto. Nos basamos en los valores de las coordenadas del punto y de las del rectángulo vertical. Como el rectángulo está de pie, sólo tenemos que considerar las coordenadas de ciertos ejes y tratarlas como condiciones de contorno. Por consiguiente, el punto P = (x,y) debe satisfacer todas las siguientes inecuaciones para aceptarlo como un punto interior al rectángulo:

xizq ≤ x ≤ xder
yinf ≤ y ≤ ysup

donde, xizq, xder, yinf, e ysup son las coordenadas que describen los lados del rectángulo vertical de recorte izquierdo, derecho, inferior, y superior, respectivamente. Esto lo podemos ver fácilmente en las figuras 1 y 2:

[IMAGEN]: Figura 1 - Antes de Recortar Puntos
Figura 1 - Antes
[IMAGEN]: Figura 2 - Puntos Recortados
Figura 2 - Después

Algoritmo Exhaustivo

Si no podemos aceptar inmediatamente un segmento, entonces comprobamos tal segmento con cada arista del rectángulo. Cada comprobación da lugar a una intersección con un lado del rectángulo, acortando el segmento hasta que esté dentro de ello. A continuación, comprobamos cada intersección es interior a nuestro rectángulo de recorte.

Con esta solución, debemos resolver varias ecuaciones por cada intersección entre segmento y arista del rectángulo. Podríamos usar la fórmula de la intersección de la pendiente, pero ésta sirve para líneas (infinitas) y no para segmentos. Además, esta fórmula no puede describir líneas verticales. Sin embargo, podemos usar una forma paramétrica para describir cualquier punto del segmento con los extremos (x0,y0) y (x1,y1):

x = x0 + t (x1 - x0)
y = y0 + t (y1 - y0)

donde, t queda comprendido en el intervalo [0,1].

También debemos describir cada arista del rectángulo de la misma forma con los extremos (x′0,y′0) y (x′1,y′1):

x′ = x′0 + t′ (x′1 - x′0)
y′ = y′0 + t′ (y′1 - y′0)

donde, t′ queda comprendido en el intervalo [0,1].

Nos interesa el punto de intersección del segmento con cada arista del rectángulo de recorte. Esto significa que debemos encontrar el punto común para ambos segmentos, por lo que (x,y) = (x′,y′). Como sabemos la coordenada de intersección para un arista concreta del rectángulo vertical, el cálculo de t es sencillo. Sólo necesitamos calcular la otra coordenada basándonos en tal valor de t. Por ejemplo, si queremos determinar la intersección de un segmento con el arista xizq del rectángulo de recorte, entonces sabemos la coordenada del punto de intersección x = xizq. Por lo tanto, tendremos que hallar la coordenada y a través del parámetro t, que calcularíamos previamente.

Ahora bien, ambos parámetros t - calculado del segmento - y t′ de la arista deben yacer en el intervalo [0,1], para considerar el punto (x,y) como interior al rectángulo de recorte. Por consiguiente, aceptamos tal punto de intersección como válido para el recorte del segmento. También debemos considerar el caso de un segmento paralelo a una arista, antes de resolver las ecuaciones.

Concluimos que este método involucra varios cálculos y comprobaciones y que por tanto se considera ineficiente.

Ejemplo

Veamos un ejemplo sencillo para entender este método.

Descripción

[IMAGEN]: Figura 3 - Ejemplo del Método Exhaustivo
Figura 3 - Ejemplo

Tenemos un rectángulo de recorte cuya diagonal es de (-1,3) a (3,-3) que representa nuestra vista. Queremos mostrar el segmento AB, en tal rectángulo de recorte, descrito por los puntos,

A = ( -2, 1 )  y   B = ( 2, 2 )

Solución

[IMAGEN]: Figura 4 - Intersección con la arista superior
Figura 4 - Arista Superior

Comenzamos estableciendo las ecuaciones paramétricas de la línea que contiene el segmento AB y la que contiene la arista superior PQ del rectángulo de recorte,

{ x  = Ax + t (Bx - Ax)
{ y  = Ay + t (By - Ay)

{ x′ = Px + t′ (Qx - Px)
{ y′ = Py + t′ (Qy - Py)

Esto quedaría así:

{ x  = -2 + 4 t
{ y  =  1 +   t

{ x′ = -1 + 4 t′
{ y′ =  3 + 0 t′

Como (x,y) = (x′,y′), calculamos t y t′:

{ -2 + 4 t = -1 + 4 t′
{  1 +   t =  3

Dando,

t  = 3 - 1 = 2
t′ = 7 / 4 = 1,75

Como ninguno de estos valores queda comprendido entre 0 y 1, no calculamos el punto de intersección porque no pertenece a ambos segmentos AB ni PQ.

[IMAGEN]: Figura 5 - Intersección con la arista derecha
Figura 5 - Arista Derecha

Establecemos las ecuaciones paramétricas de la línea que contiene el segmento AB y la que contiene la arista derecha QR del rectángulo de recorte,

{ x′ = Qx + t′ (Rx - Qx)
{ y′ = Qy + t′ (Ry - Qy)

Esto quedaría así:

{ x  = -2 + 4 t
{ y  =  1 +   t

{ x′ = 3 + 0 t′
{ y′ = 3 - 6 t′

Como (x,y) = (x′,y′), calculamos t y t′:

{ -2 + 4 t =  3
{  1 +   t =  3 - 6 t′

Dando,

t  = 5 / 4 = 1,25
t′ = 1 / 8 = 0,125

Aunque t′ queda comprendido entre 0 y 1, t no, por lo que no calculamos el punto de intersección porque no pertenece a ambos segmentos AB ni QR.

[IMAGEN]: Figura 6 - Intersección con la arista inferior
Figura 6 - Arista Inferior

Establecemos las ecuaciones paramétricas de la línea que contiene el segmento AB y la que contiene la arista inferior RS del rectángulo de recorte,

{ x′ = Rx + t′ (Sx - Rx)
{ y′ = Ry + t′ (Sy - Ry)

Esto quedaría así:

{ x  = -2 + 4 t
{ y  =  1 +   t

{ x′ =  3 - 4 t′
{ y′ = -3 + 0 t′

Como (x,y) = (x′,y′), calculamos t y t′:

{ -2 + 4 t =  3 - 4 t′
{  1 +   t = -3

Dando,

t  = -4
t′ = 21 / 4 = 5,25

Obviamente ninguno de estos valores paramétricos queda comprendido entre 0 y 1, por lo que no calculamos el punto de intersección porque no pertenece a ambos segmentos AB ni RS.

[IMAGEN]: Figura 7 - Intersección con la arista izquierda
Figura 7 - Arista Izquierda

Establecemos las ecuaciones paramétricas de la línea que contiene el segmento AB y la que contiene la arista izquierda SP del rectángulo de recorte,

{ x′ = Sx + t′ (Px - Sx)
{ y′ = Sy + t′ (Py - Sy)

Esto quedaría así:

{ x  = -2 + 4 t
{ y  =  1 +   t

{ x′ = -1 + 0 t′
{ y′ = -3 + 9 t′

Como (x,y) = (x′,y′), calculamos t y t′:

{ -2 + 4 t = -1
{  1 +   t = -3 + 9 t′

Dando,

t  = 1 / 4 = 0,25
t′ = 4,25 / 9 ≅ 0,4722

Ambos valores paramétricos quedan comprendidos entre 0 y 1, por lo que calculamos el punto de intersección a partir de cualquiera de los dos segmentos. Por ejemplo, usando el segmento AB, volvemos a las ecuaciones paramétricas con el parámetro t = 0,25,

{ x  = -2 + 4 (0,25) = -1
{ y  =  1 +   (0,25) =  1,25

Dando el punto de intersección (-1, 1,25).

[IMAGEN]: Figura 8 - Ejemplo Solución
Figura 8 - Solución Final

Vemos que debemos acortar el segmento AB dando lugar a nuevos valores usando este punto de intersección:

A′ = (-1, 1,25)
B  = ( 2, 2)

Al final, el segmento AB es acortado al segmento A′B.

Algoritmo de Cohen-Sutherland

Este algoritmo realiza varias comprobaciones iniciales para descubrir si se puede evitar cálculos de las intersecciones. El primer paso es comprobar si los puntos extremos del segmento son aceptados por sus posiciones. Si esto no es posible, entonces realizamos varias comprobaciones por regiones exteriores al rectángulo de recorte, formadas por las líneas rectas al extender sus aristas. Asimismo, podemos rechazar un segmento inmediatamente si sus extremos yacen en regiones a la izquierda de xizq, por encima de ysup, a la derecha de xder, y por debajo de yinf.

Si el segmento no se puede aceptar ni rechazar inmediatamente, entonces es partido en dos segmentos por un arista del rectángulo de recorte, para que uno de ellos sea rechazado de inmediato. Esto implica que implementamos un método iterativo de recorte para el segmento hasta que éste sea aceptado o rechazado. Este algoritmo es eficiente especialmente en el caso de tener un rectángulo de recorte muy grande que comprende a todos o una gran mayoría de los segmentos a visualizar. Asimismo, podemos tener el caso de un rectángulo de recorte muy pequeño que fuerza a todos o casi todos los segmentos a ser rechazados.

Se le asigna un código de cuatro bits, b3b2b1b0, a cada región de las nueve creadas. Este código binario es creado estratégicamente para representar rápida y fácilmente cada región. El valor de 1 indicará que un extremo yace en tal región mientras que un 0 indicará lo contrario. Aquí tenemos la estrategia a usar:

Bit Condición Descripción
b3 y > ysup  por encima de la arista superior
b2 y < yinf  por debajo de la arista inferior
b1 x > xder  a la derecha de la arista derecha
b0 x < xizq  a la izquierda de la arista izquierda
[IMAGEN]: Figura 9 - Las regiones con los Códigos del Algoritmo de Cohen-Sutherland
Figura 9 - Las regiones con los Códigos

Usaremos ciertas operaciones a nivel de bit para asginar el código regional a cada extremo en el que yace y también para determinar tal región cuando necesitemos discriminarlos. Una forma eficiente de asignar un valor a un bit particular es tomando el primer bit que indica el signo positivo o negativo de la resta entre las dos coordenadas de la condición. Esto es, b3 es asignado el bit del signo de (ysup-y), b2 es asignado el bit de (y - yinf), b1 es asignado el bit de (xsup-x), y b0 es asignado el bit de (x - xinf).

La figura 9 muestra las regiones con sus correspondientes códigos.

Con estos códigos podemos determinar si los extremos, y por tanto el segmento que representan, pueden ser aceptados o rechazados inmediatamente. Obviamente, si ambos códigos son 0, entonces ambos extremos existen dentro del rectángulo de recorte, y por consiguiente el segmento es aceptado de inmediato. Para combinar estos dos códigos, simplemente aplicamos una operación OR y comprobamos si el resultado es 0. Si el código no es 0, entonces aplicamos la operación AND a ambos códigos. Si el resultado no es cero, entonces rechazamos el segmento de inmediato.

Si no podemos aceptar ni rechazar inmediatamente el segmento, entonces iremos dividiendo el segmento y comprobando sus nuevos códigos, para determinar su aceptación o rechazo. Dividimos el segmento calculando la intersección con las líneas creadas al extender las aristas del rectángulo de recorte. Si no podemos discriminar el nuevo segmento, entonces debemos continuar dividiéndolo hasta que al final lo aceptamos o lo rechazamos. Una propiedad notable es que modificamos el segmento mudando el extremo, cuyo código no es cero. Dicho de otra manera, el algoritmo elige un extremo exterior que será mudado a la intersección con la arista o con la línea que separa y define las regiones. Asignamos el código regional del punto de intersección al extremo mudado.

La desventaja de este algoritmo es que puede realizar varias intersecciones antes de alcanzar la intersección final y válida. Una mejora es calcular la pendiente para determinar el punto de intersección una sola vez y conservarla para posteriores iteraciones. Aun con esta mejora, este algoritmo no es tan eficiente. Por otro lado, la ventaja de este algoritmo es su simplicidad y además se puede extender fácilmente al caso de un volumen de recorte en 3D.

Ejemplo

Descripción

[IMAGEN]: Figura 10 - Ejemplo del Algoritmo de Cohen-Sutherland
Figura 10 - Ejemplo

Queremos mostrar varios segmentos, pero únicamente dentro de nuestra vista representada por un rectángulo vertical descrito con las siguientes esquinas: superior izquierda (-1,3) e inferior derecha (3,-3). Tenemos los siguientes segmentos definidos por parejas de puntos que forman sus extremos:
A = (-2, 1) y B = ( 2, 2),
C = ( 1, 4) y D = ( 0,-4),
E = ( 4, 3) y F = ( 3, 0),
G = (-3,-1) y H = (-2,-4).

Solución

[IMAGEN]: Figura 11 - Ejemplo Solución con Códigos
Figura 11 - Solución

Calculamos los códigos regionales para cada punto:

A: 0001  B: 0000
C: 1000  D: 0100
E: 0010  F: 0000
G: 0001  H: 0101
[IMAGEN]: Figura 12 - Ejemplo Solución Aplicando Criterios
Figura 12 - Aplicando Criterios

Aplicamos nuestros criterios a los resultados de las operaciones a nivel de bit de los códigos regionales de cada punto dando lugar a:

AB: 0001 OR 0000 = 0001  ⇒  0001 AND 0000 = 0000  ⇒  Hay que recortar
CD: 1000 OR 0100 = 1100  ⇒  1000 AND 0100 = 0000  ⇒  Hay que recortar
EF: 0010 OR 0000 = 0010  ⇒  0010 AND 0000 = 0000  ⇒  Hay que recortar
GH: 0001 OR 0101 = 0101  ⇒  0001 AND 0101 = 0001  ⇒  Inmediatamente lo rechazamos
[IMAGEN]: Figura 13 - Ejemplo Solución Recortando con las Primeras Aristas Encontradas
Figura 13 - Recortando

Hacemos la primera tanda de recortes de los puntos con sus primeras aristas del algoritmo, obteniendo:

{ A'x = -1
{ A'y =  1 + 1 * 1 / 4 = 1,25

{ C'x =  1 - 1 * 1 / (-8) = 1,125
{ C'y =  3

{ E'x =  3
{ E'y =  3 - 3 * (-1) / (-1) = 0

Recalculamos los códigos de cada punto:

A′B: 0000 OR 0000 = 0000  ⇒  Aceptamos el segmento
C′D: 0000 OR 0100 = 0100  ⇒  0000 AND 0100 = 0000  ⇒  Hay que recortar
E′F: 0000 OR 0000 = 0000  ⇒  Aceptamos el segmento
[IMAGEN]: Figura 14 - Ejemplo Solución Recortar C′D
Figura 14 - Recortando

Nos falta recortar una segunda vez para el segmento C′D. El algoritmo elige el punto D para recortar, obteniendo:

{ D'x =  0 + 1,125 * 1 / 7 = 0,1607
{ D'y = -3

Recalculamos los códigos de cada punto:

C′D′: 0000 OR 0000 = 0000  ⇒  Aceptamos el segmento
[IMAGEN]: Figura 15 - Ejemplo Solución Final
Figura 15 - Final

Al final, obtenemos la siguiente imagen con los segmentos recortados e interiores al rectángulo de recorte.

Algoritmo

La función principal es Recortar(), la cual aceptará tres parámetros: dos puntos extremos, P y Q, donde cada uno contiene las coordenadas (x,y) que representan el segmento a recortar, y un rectángulo, R, que contiene los elementos {xizq,ysup, xder,yinf} representando las coordenadas de las dos esquinas izquierda superior y derecha inferior. También debemos definir los códigos binarios para: SUPERIOR=8, INFERIOR=4, DERECHA=2, e IZQUIERDA=1.

Para Recortar(), el algoritmo es:

booleano Recortar( ref Punto P, ref Punto Q, Rectángulo R )
  1. aceptar ← falso
  2. terminar ← falso
  3. códigoP ← Calcular_Código(P,R)
  4. códigoQ ← Calcular_Código(Q,R)
  5. Repetir:
  6. Si (códigoP OR códigoQ) = 0, entonces
  7. aceptar ← verdadero
  8. terminar ← verdadero
  9. Si no, compruebe que (códigoP AND códigoQ) ≠ 0,
  10. terminar ← verdadero
  11. Si no, entonces
  12. Si códigoP = 0, entonces
  13. código ← códigoQ
  14. Si no, entonces
  15. código ← códigoP
  16. Si código es SUPERIOR, entonces
  17. Δy ← Q.y-P.y
  18. Si Δy = 0, entonces // segmento vertical
  19. x ← P.x
  20. Si no, entonces
  21. x ← P.x + (Q.x-P.x)*(R.ysup-P.y) / Δy
  22. y ← ysup
  23. Si no, compruebe que código es INFERIOR
  24. Δy ← Q.y-P.y
  25. Si Δy = 0, entonces // segmento vertical
  26. x ← P.x
  27. Si no, entonces
  28. x ← P.x + (Q.x-P.x)*(R.yinf-P.y) / Δy
  29. y ← yinf
  30. Si no, compruebe que código es DERECHA
  31. x ← xder
  32. y ← P.y + (Q.y-P.y)*(R.xder-P.x) / (Q.x-P.x)
  33. Si no, entonces // código = IZQUIERDA
  34. x ← xizq
  35. y ← P.y + (Q.y-P.y)*(R.xizq-P.x) / (Q.x-P.x)
  36. Si código = códigoP, entonces
  37. P.x ← x
  38. P.y ← y
  39. códigoP ← Calcular_Código(P,R)
  40. Si no, entonces
  41. Q.x ← x
  42. Q.y ← y
  43. códigoQ ← Calcular_Código(Q,R)
  44. Mientras que terminar = falso
  45. Terminar( aceptar )

Si el segmento es aceptado, entonces el algoritmo terminará con el valor booleano verdadero. Además, los extremos, P y Q, contendrán los valores recortados por este mismo algoritmo. Si el segmento es rechazado, entonces uno debería hacer caso omiso de los parámetros, P y Q. En cualquier caso, se pasan estos dos parámetros por referencia, para así poder modificarlos.

A continuación presentamos el algoritmo para Calcular_Código(), el cual requiere un punto, P, y el rectángulo de recorte, R:

entero Calcular_Código( Punto P, Rectángulo R )
  1. código ← 0
  2. Si P.y > R.ysup, entonces
  3. código ← código OR SUPERIOR
  4. Si no, compruebe que P.y < R.yinf
  5. código ← código OR INFERIOR
  6. Si P.x > R.xder, entonces
  7. código ← código OR DERECHA
  8. Si no, compruebe que P.x < R.xizq
  9. código ← código OR IZQUIERDA
  10. Terminar( código )

No todos los lenguajes de programación aceptan realizar operaciones a nivel de bit con números que no sean enteros. Tampoco todos los lenguajes establecen exactamente la cantidad de bits para representar internamente un número real. Por estas razones, no hemos presentado el algoritmo mejorado para Calcular_Código() que previamente hablamos en este apartado.

Suponiendo que un número real se representase con 32 bits y el 32º bit contiene su signo positivo, como 0, o negativo, como 1, aquí presentamos otra versión del algoritmo Calcular_Código():

entero Calcular_Código( Punto P, Rectángulo R )
  1. código ← (((P.y - R.ysup) SHR 31) SHL 3) OR (((R.yinf - P.y) SHR 31) SHL 2) OR (((P.x - R.xder) SHR 31) SHL 1) OR ((R.xizq - P.x) SHR 31)
  2. Terminar( código )

El operador SHL se refiere a la operación común de desplazamiento de bits a la izquierda y el operador SHR se refiere a la del desplazamiento de bits a la derecha.

Algoritmo de Cyrus-Beck

Este algoritmo se basa en calcular las intersecciones del segmento, P0P1, con cada arista de un polígono convexo de recorte. Se usa la ecuación paramétrica de la línea para determinar los cuatro valores de t. Posteriormente, realizamos varias comparaciones para determinar cuáles de estos cuatro valores de t corresponden a intersecciones reales. Sólo al tener los valores válidos de t es cuando calculamos los puntos de intersección.

[IMAGEN]: Figura 16 - Tres ejemplos de puntos fuera, dentro, y en la arista de la región de recorte
Figura 16 - Clasificación de Puntos

Para encontrar el punto de intersección, el algoritmo de Cyrus-Beck se basa en la ecuación paramétrica de una línea recta. Como tenemos dos segmentos: P0P1 y la arista, que yacen sobre dos líneas rectas, tenemos dos ecuaciones paramétricas que las representan. Al resolver estas dos ecuaciones, averiguaremos un valor de t con el que determinaremos el punto de intersección. La ecuación paramétrica es la siguiente:
P(t) = P0 + (P1-P0) t
donde t queda comprendido en el intervalo [0,1]. Esto implica que P(0) = P0 y P(1) = P1.

Para determinar el valor exacto de t, haremos uso del producto escalar entre dos vectores. El primer vector será el vector normal de la arista que apunta hacia fuera de la región de recorte. El segundo vector será uno que coincide con la arista. Crearemos este segundo vector a partir de un punto cualquiera, Pa, en la arista, y el punto P(t) que es común a la línea del segmento, P0P1, que queremos recortar y a esta misma arista. El cálculo es el siguiente:
N⋅(P(t) - Pa)

Si el producto escalar es positivo, entonces el punto, P(t), yace fuera de la región de recorte y si es negativo, entonces P(t) yace dentro. Como nos interesa averiguar el punto común que yace en la arista y por tanto el borde de la región de recorte, el producto escalar debe ser 0; véase la figura 16. Esto significa que debemos resolver la siguiente ecuación:
N⋅(P(t) - Pa) = 0

Sustituimos P(t) por su definición,
N⋅(P0 + (P1-P0) t - Pa) = 0

Aplicamos la propiedad distributiva,
N⋅(P0 - Pa) + N⋅(P1-P0) t = 0

Dejemos que D = P1-P0, que es el vector de P0 a P1 del segmento. Ahora resolvemos para t:

     N⋅(P0 - Pa) 
t = ------------
        -N⋅D

Este valor de t es válido solamente si el denominador no es cero. Esto significa que las siguientes condiciones deben mantenerse:

N0  El vector normal jamás debería ser nulo. Si ocurriere lo contrario, entonces se trata de un error.
D0  Esto significa que P0 ≠ P1. Si ocurriere lo contrario, entonces se trata de un solo punto y no de un segmento.
N⋅D ≠ 0  Esto significa que la arista y el segmento no son paralelos. Si fueren paralelos, entonces no existe ninguna intersección.

El algoritmo calcula cada intersección entre el mismo segmento y cada arista de la región de recorte. Para este cálculo, determinamos el vector normal de cada arista y un punto arbitrario que yace en una arista. Lo más sencillo y práctico es elegir un punto conocido como un vértice que forma la arista. Posteriormente, debemos elegir cuáles de los cuatro valores de t corresponden a intersecciones internas a la región de recorte. Primeramente, comprobamos que los valores de t quedan comprendidos en el intervalo [0,1]. Si no se cumple esta condición, entonces significa que el punto de intersección no yace en el segmento y por tanto descartamos tal valor de t. Como cada cálculo que hacemos se basa en encontrar las intersecciones entre dos líneas rectas, esto significa que un valor de t puede indicar una intersección que no yace en una arista.

En algunos casos, no es tan sencillo determinar si una intersección yace dentro o fuera de la región de recorte. Podríamos realizar varias comprobaciones, pero entonces ralentizaríamos el algoritmo y no conseguiríamos una ventaja sobre otros algoritmos, como el de Cohen-Sutherland. Analizando varios casos de intersecciones entre segmentos y aristas, descubrimos un comportamiento que nos servirá para discriminar tal intersección y así determinar si es aceptada o rechazada. Esta técnica se basa en denominar las intersecciones como potencialmente entrantes (PE) y potencialmente salientes (PS) de la región de recorte. Si cruzamos una arista, yendo desde los extremos P0 a P1, que nos hace entrar en la mitad del plano, entonces la intersección lleva la etiqueta de PE. Si por el contrario, al cruzar la arista, nos hace salir del plano interior creado por la arista, entonces tal intersección es PS. Con esta clasificación, notamos que dos intersecciones interiores a la región de recorte tienen etiquetas opuestas.

Para clasificar si una intersección es PE o PS, podemos basarnos en el ángulo formado por los vectores del segmento P0P1 y el normal de una arista. Si el ángulo es mayor de 90°, entonces es PE; y si es menor de 90°, entonces es PS. No requerimos calcular el ángulo, ya que esta información está contenida en el producto escalar del vector normal N y el vector D del segmento P0P1:

N⋅D < 0  ⇒ ángulo > 90°  ⇒ PE
N⋅D > 0  ⇒ ángulo < 90°  ⇒ PS

Vemos que N⋅D es el denominador en el cálculo de t para determinar el punto de intersección. Por lo tanto, podemos clasificar el valor de t mientras lo calculamos.

Nos interesa encontrar aquellos puntos de intersección etiquetados de PE a PS. El punto de intersección con la etiqueta PE que sea interior a la región de recorte es aquél que tenga el mayor valor de t; lo llamaremos, te. El punto interior que tenga la etiqueta PS es aquél que tenga el menor valor de t, al cual lo llamaremos, ts. El segmento cruzante se define en el intervalo [te,ts]. Como ya mencionamos anteriormente, los valores de t deben estar comprendidos en el intervalo de [0,1]. Por consiguiente, la cota inferior de te = 0 y la cota superior de ts = 1. Si te > ts, entonces el segmento no es interior a la región de recorte y por tanto lo rechazamos. Al final, obtendremos los valores correctos de te y ts para así calcular las coordenadas x e y de los puntos de intersección.

[IMAGEN]: Figura 17 - Tres casos de segmentos cruzando las aristas del polígono de recorte con las etiqutas PE y PS
Figura 17 - Ejemplo de Tres Casos

Este algoritmo tiene la ventaja de no estar basado en un bucle comparado con el algoritmo de Cohen-Sutherland.

Ejemplo

Descripción

[IMAGEN]: Figura 18 - Ejemplo del Algoritmo de Cyrus-Beck
Figura 18 - Ejemplo

Queremos mostrar un segmento, pero únicamente dentro de nuestra vista representada por un triángulo descrito con los siguientes vértices: { (2,3), (3,-3), (-4,-2) }. Tenemos un segmento definido por la siguiente pareja de sus puntos extremos:
A = (-3,-1) y B = (1,1)

Solución

[IMAGEN]: Figura 19 - Calculamos los vectores normales de cada arista
Figura 19 - Calculamos Normales

Calculamos los vectores normales - sin normalizar - de todas las aristas de nuestro triángulo de recorte:

v12 = (  3, -3 ) - (  2,  3 ) = (  1, -6 )N1 = (  6,  1 )
v23 = ( -4, -2 ) - (  3, -3 ) = ( -7,  1 )N2 = ( -1, -7 )
v31 = (  2,  3 ) - ( -4, -2 ) = (  6,  5 )N3 = ( -5,  6 )
[IMAGEN]: Figura 20 - Calculamos y etiquetamos t para la primera intersección
Figura 20 - Primera Intersección

Calculamos el valor de t para la intersección de la línea que contiene el segmento AB con la línea generada por v1v2. Primero calculamos y comprobamos el denominador del cálculo de t por si es 0 y por tanto el segmento es paralelo a la arista:

N1⋅D = (  6,  1 ) ⋅ (  4,  2 ) = 6*4 + 1*2 = 26

Como el denominador no es 0, calculamos el valor de t para ts ya que el denominador es positivo por lo que se trata de un punto potencialmente saliente:

     (  6,  1 ) ⋅ (( -3, -1 ) - (  2,  3 ))
t = ---------------------------------------- 
                     -26

     (  6,  1 ) ⋅ ( -5, -4 )
  = -------------------------
               -26

     6*(-5) + 1*(-4)     -34
  = ----------------- = ----- = 1,3077
            -26          -26

Como el valor de t no queda comprendido en [0,1], lo descartamos. El valor de ts sigue siendo 1, en estos momentos, ya que queremos el menor valor para ts. Esto es correcto, ya que 1 < 1,3077.

[IMAGEN]: Figura 21 - Calculamos y etiquetamos t para la segunda intersección
Figura 21 - Segunda Intersección

Calculamos el valor de t para la intersección de la línea que contiene el segmento AB con la línea generada por v2v3. Primero calculamos y comprobamos el denominador del cálculo de t por si es 0 y por tanto el segmento es paralelo a la arista:

N2⋅D = ( -1, -7 ) ⋅ (  4,  2 ) = (-1)*4 + (-7)*2 = -18

Como el denominador no es 0, calculamos el valor de t para te ya que el denominador es negativo por lo que se trata de un punto potencialmente entrante:

     ( -1, -7 ) ⋅ (( -3, -1 ) - (  3, -3 ))
t = ---------------------------------------- 
                   -(-18)

     ( -1, -7 ) ⋅ ( -6,  2 )
  = -------------------------
               18

     (-1)*(-6) + (-7)*2     -8
  = -------------------- = ---- = -0,4444
             18             18

Como el valor de t no queda comprendido en [0,1], lo descartamos. El valor de te sigue siendo 0, en estos momentos, ya que queremos el mayor valor para te. Esto es correcto, ya que -0,4444 < 0.

[IMAGEN]: Figura 22 - Calculamos y etiquetamos t para la tercera intersección
Figura 22 - Tercera Intersección

Calculamos el valor de t para la intersección de la línea que contiene el segmento AB con la línea generada por v3v1. Primero calculamos y comprobamos el denominador del cálculo de t por si es 0 y por tanto el segmento es paralelo a la arista:

N3⋅D = ( -5,  6 ) ⋅ (  4,  2 ) = (-5)*4 + 6*2 = -8

Como el denominador no es 0, calculamos el valor de t para te ya que el denominador es negativo por lo que se trata de un punto potencialmente entrante:

     ( -5,  6 ) ⋅ (( -3, -1 ) - ( -4, -2 ))
t = ---------------------------------------- 
                     -(-8)

     ( -5,  6 ) ⋅ (  1,  1 )
  = -------------------------
                8

     (-5)*1 + 6*1     1
  = -------------- = --- = 0,125
           8          8

Como el valor de t queda comprendido en [0,1], actualizamos el valor de te para que sea 0,125, ya que 0,125 > 0, su valor anterior.

[IMAGEN]: Figura 23 - Recortamos el segmento AB
Figura 23 - Solución Final

Al terminar de inspeccionar todas las aristas del triángulo de recorte, comprobamos los valores de te y ts, ya que son las cotas inferior y superior, respectivamente, de un intervalo: tets. En nuestro caso, obtenemos el siguiente intervalo válido: [0,125, 1].

Pasamos a calcular los nuevos puntos extremos para el segmento recortado:

A′ = ( -3, -1 ) + (( -3, -1 ) - ( 1, 1 )) * 0,125
   = ( -3, -1 ) + (  4,  2 ) * 0,125
   = ( -3 + 0,5, -1 + 0,25 )
   = ( -2,5, -0,75 )

B′ = ( -3, -1 ) + (( -3, -1 ) - ( 1, 1 )) * 1
   = ( -3, -1 ) + ( 4, 2 ) * 1
   = ( -3 + 4, -1 + 2 )
   = (  1,  1 )

Algoritmo

Tenemos varias funciones a destacar para implementar este algoritmo:

  • La función principal es Recortar(), la cual aceptará tres parámetros: dos puntos extremos, P y Q, donde cada uno contiene las coordenadas (x,y) que representan el segmento a recortar, y un polígono convexo, R, que contiene una lista de vértices {v1, v2, v3, ..., vn} en el sentido de las agujas del reloj para representar la región de recorte.
  • La función Recortar_Punto() se invocará para tratar el segmento como un único punto. Básicamente, se realizará el algoritmo explicado anteriormente.
  • La función Calcular_Normal() es necesaria si no tenemos una lista de normales de las aristas del polígono de recorte, R.
  • Las funciones mayor() y menor() determinan cuáles de los dos parámetros dados son el mayor y el menor, respectivamente.
  • La función Calcular_Punto() sirve para obtener un punto en una línea recta según la ecuación paramétrica. Esta función requiere dos puntos extremos de la línea y el parámetro, t.

Para Recortar(), el algoritmo es:

booleano Recortar( ref Punto P, ref Punto Q, PolígonoConvexo R )
  1. Si P = Q, entonces
  2. resultado ← Recortar_Punto( P, R )
  3. Terminar( resultado )
  4. Si no, entonces
  5. te ← 0
  6. ts ← 1
  7. Para cada vértice, vi, de R, hacer
  8. N ← Calcular_Normal( vi+1 - vi )
  9. numerador ← N⋅(P - vi)
  10. denominador ← -N⋅(Q - P)
  11. Si denominador ≠ 0, entonces
  12. t ← numerador / denominador
  13. Si denominador < 0, entonces
  14. te ← mayor( te, t )
  15. Si no, entonces
  16. ts ← menor( ts, t )
  17. Si no, compruebe que numerador > 0,
  18. Terminar( falso )
  19. Si te > ts, entonces
  20. Terminar( falso )
  21. Si no, entonces
  22. Pe ← Calcular_Punto( P, Q, te )
  23. Ps ← Calcular_Punto( P, Q, ts )
  24. P ← Pe
  25. Q ← Ps
  26. Terminar( verdadero )

Si el segmento es aceptado, entonces el algoritmo terminará con el valor booleano verdadero. Además, los extremos, P y Q, contendrán los valores recortados por este mismo algoritmo. Si el segmento es rechazado, el algoritmo termina con el valor falso, lo cual implica que los parámetros, P y Q, no son alterados. En cualquier caso, se pasan estos dos parámetros por referencia, para así poder modificarlos.

A continuación presentamos el algoritmo para Calcular_Normal(), el cual requiere un vector, v:

Vector Calcular_Normal( Vector v )
  1. vector N ← ( -v.y, v.x )
  2. N ← Normalizar( N )
  3. Terminar( N )

Este cálculo nos sirve si el vector dado sigue el convenio de ir en el sentido de las agujas del reloj. La función Normalizar() se refiere a la operación vectorial para convertir un vector en unitario. Sin embargo, en este algoritmo, no es necesario normalizar estos vectores normales, por lo que podemos conseguir una optimización para el algoritmo de Cyrus-Beck.

Por último, tenemos el algoritmo para Calcular_Punto(), que requiere dos puntos, P y Q, y un valor para t:

Punto Calcular_Punto( Punto P, Punto Q, real t )
  1. Punto A ← P + (Q-P) t
  2. Terminar( A )

Algoritmo de Liang-Barsky

Este algoritmo se basa en el algoritmo propuesto por Cyrus-Beck. La diferencia es que el algoritmo de Liang-Barsky aplica ciertas interpretaciones geométricas y simplificaciones al basarse en un rectángulo vertical de recorte. Con un rectángulo vertical, podemos definir los vectores normales sin problemas al igual que los vectores en las aristas. Veamos una tabla de ciertos valores y las simplificaciones que podemos realizar.

Arista de Recorte    Normal, N    Vértice, V    P0-V    D = P1-P0    t = -N⋅(P0 - V) / N⋅D
izquierda: x = xizq    (-1,0)    (xizq, Vy)    (x0-xizq, y0-Vy)    (x1-x0, y1-y0)    -(x0-xizq) / (x1-x0)   
derecha: x = xder (1,0) (xder, Vi.y) (x0-xder, y0-Vy)    (x1-x0, y1-y0)    (x0-xder) / -(x1-x0)   
superior: y = ysup (0,-1) (Vi.x, ysup) (x0-Vx, y0-ysup)    (x1-x0, y1-y0)    -(y0-ysup) / (y1-y0)   
inferior: y = yinf (0,1) (Vi.x, yinf) (x0-Vx, y0-yinf)    (x1-x0, y1-y0)    (y0-yinf) / -(y1-y0)   

Según esta tabla, vemos que el cálculo de t se reduce a una división de distancias entre coordenadas homogéneas: anchuras para el recorte de las coordenadas en X y alturas para el recorte de las coordenadas en Y. El numerador pasa a ser la distancia del punto extremo del segmeneto a la arista. Esta distancia equivale a la misma cantidad que usamos en el método de Cohen-Sutherland al calcular el código binario para cada punto extremo. También podemos ver que el denominador es la anchura, dx, o la altura, dy. Según el signo de estas longitudes, el segmento es PE o PS, y por ello los signos del numerador y del denominador se deben conservar, para que el algoritmo funcione correctamente.

Ejemplo

Descripción

[IMAGEN]: Figura 24 - Ejemplo del Algoritmo de Liang-Barsky
Figura 24 - Ejemplo

Retomamos el mismo ejemplo del método exhaustivo. Tenemos un rectángulo de recorte cuya diagonal es de (-1,3) a (3,-3) que representa nuestra vista. Queremos mostrar el segmento AB, en tal rectángulo de recorte, descrito por los puntos,

A = ( -2, 1 )  y  B = ( 2, 2 )

Solución

[IMAGEN]: Figura 25 - Calculamos t[e] y t[s] para la intersección con la arista izquierda
Figura 25 - Arista Izquierda

Calculamos el vector D de A a B:

D = B - A = (  2,  2 ) - ( -2,  1 ) = (  4,  1 )

Comprobamos el caso trivial en el que los dos puntos representan un mismo punto visible, en lugar de un segmento. Como D ≠ (0,0), tenemos un segmento.

Calculamos la intersección del segmento AB con la arista izquierda. Como el denominador, Dx = 4, es positivo, calculamos t:

     R.xizq - Ax    -1 - (-2)    1
t = ------------ = --------- = --- = 0,25
          Dx           4        4

Como t > te, actualizamos te = 0,25. El intervalo de t por ahora es [0,25, 1].

[IMAGEN]: Figura 26 - Calculamos t[e] y t[s] para la intersección con la arista derecha
Figura 26 - Arista Derecha

Calculamos la intersección del segmento AB con la arista derecha. Usamos el denominador, -Dx = -4, que al ser negativo, calculamos t:

     Ax - R.xder     -2 - 3     -5
t = ------------ = -------- = ---- = 1,25
         -Dx          -4       -4

Como t > ts, no actualizamos ts. El intervalo de t por ahora sigue siendo [0,25, 1].

[IMAGEN]: Figura 27 - Calculamos t[e] y t[s] para la intersección con la arista inferior
Figura 27 - Arista Inferior

Calculamos la intersección del segmento AB con la arista inferior. Usamos el denominador, Dy = 1, que al ser positivo, calculamos t:

     R.yinf - Ay     -3 - 1
t = ------------ = -------- = -4
          Dy           1

Como t < te, no actualizamos te. El intervalo de t por ahora sigue siendo [0,25, 1].

[IMAGEN]: Figura 28 - Calculamos t[e] y t[s] para la intersección con la arista superior
Figura 28 - Arista Superior

Calculamos la intersección del segmento AB con la arista superior. Usamos el denominador, -Dy = -1, que al ser negativo, calculamos t:

     Ay - R.ysup     1 - 3
t = ------------ = ------- = 2
         -Dy          -1

Como t > ts, no actualizamos ts. El intervalo de t por ahora sigue siendo [0,25, 1].

[IMAGEN]: Figura 29 - Calculamos los puntos extremos a partir de t[e] y t[s]
Figura 29 - Solución Final

Como ts no fue actualizado, no necesitamos que realizar ningún cáculo. Como te fue actualizado, calculamos el punto entrante de intersección, A:

A′ = A + te * ( Dx, Dy ) 
   = ( -3,  1 ) + 0,25 * (  4,  1 ) 
   = ( -2,  1,25 )

Algoritmo

Tenemos varias funciones a destacar para implementar este algoritmo:

  • La función principal es Recortar(), la cual aceptará tres parámetros: dos puntos extremos, P y Q, donde cada uno contiene las coordenadas (x,y) que representan el segmento a recortar, y un rectángulo vertical, R, que contiene los elementos {xizq,ysup, xder,yinf} representando las coordenadas de las dos esquinas izquierda superior y derecha inferior.
  • La función Recortar_Punto() se invocará para tratar el segmento como un único punto. Básicamente, se realizará el algoritmo explicado anteriormente. El resultado es un valor booleano que indicará si el punto fue recortado (verdadero) o no (falso).
  • La función Calcular_Parámetros() servirá para calcular los parámetros, te y ts. Necesitamos pasar el numerador, el denominador, y los parámetros, te y ts, que serán modificados. Esta función nos indicará si estos parámetros, te y ts, han sido modificados y por tanto, el segmento es aceptado (verdadero) o rechazado (falso).

Para Recortar(), el algoritmo es:

booleano Recortar( ref Punto P, ref Punto Q, Rectángulo R )
  1. dx ← Q.x - P.x
  2. dy ← Q.y - P.y
  3. resultado ← falso
  4. Si dx = 0, y Si dy = 0, y Si Recortar_Punto( P, R ) = verdadero, entonces
  5. Q ← P
  6. resultado ← verdadero
  7. Si no, entonces
  8. te ← 0
  9. ts ← 1
  10. Si Calcular_Parámetros( R.xizq-P.x, dx, te, ts ) = verdadero, entonces
  11. Si Calcular_Parámetros( P.x-R.xder, -dx, te, ts ) = verdadero, entonces
  12. Si Calcular_Parámetros( R.yinf-P.y, dy, te, ts ) = verdadero, entonces
  13. Si Calcular_Parámetros( P.y-R.ysup, -dy, te, ts ) = verdadero, entonces
  14. resultado ← verdadero
  15. Si ts < 1, entonces
  16. Q.x ← P.x + ts dx
  17. Q.y ← P.y + ts dy
  18. Si te > 0, entonces
  19. P.x ← P.x + te dx
  20. P.y ← P.y + te dy
  21. Terminar( resultado )

Si el segmento es aceptado, entonces el algoritmo terminará con el valor booleano verdadero. Además, los extremos, P y Q, contendrán los valores recortados por este mismo algoritmo. Si el segmento es rechazado, el algoritmo termina con el valor falso, lo cual implica que los parámetros, P y Q, no son alterados. En cualquier caso, se pasan estos dos parámetros por referencia, para así poder modificarlos.

A continuación presentamos el algoritmo para Calcular_Parámetros(), el cual requiere el numerador, el denominador, te, y ts, los cuales estos dos últimos se pasan por referencia:

booleano Calcular_Parámetros( real numerador, real denominador, ref real te, ref real ts )
  1. Si denominador > 0, entonces
  2. t ← numerador / denominador
  3. Si t > ts
  4. Terminar( falso )
  5. Si no, compruebe que t > te
  6. te ← t
  7. Si no, compruebe que denominador < 0,
  8. t ← numerador / denominador
  9. Si t < te
  10. Terminar( falso )
  11. Si no, compruebe que t < ts
  12. ts ← t
  13. Si no, compruebe que numerador > 0,
  14. Terminar( falso )
  15. Terminar( verdadero )

Algoritmo de Nicholl-Lee-Nicholl

Este algoritmo intenta corregir los problemas de los algoritmos anteriores para recortar segmentos en un rectángulo vertical. El algoritmo de Cohen-Sutherland se basa en realizar varias comprobaciones, pero acaba calculando varias intersecciones que pueden o no servir. Los algoritmos de Cyrus-Beck y Liang-Barsky se basan en calcular varias intersecciones y luego comprobar cuáles sirven. El algoritmo de Nicholl-Lee-Nicholl elimina la necesidad de realizar todos estos cálculos de intersecciones favoreciendo las comprobaciones para dar con la intersección correcta, si existe. Al final, este algoritmo es más rápido que los mencionados anteriormente.

Para recortar un segmento con los extremos P y Q, necesitamos determinar las intersecciones, si existen, con las aristas. Comenzamos dividiendo la geometría en nueve regiones al extender horizontal y verticalmente las aristas del rectángulo vertical, como hicimos en el algoritmo de Cohen-Sutherland. Sin embargo, sólo necesitamos considerar tres casos de la posición del punto extremo, P, porque los demás casos son simétricos a uno de estos tres casos principales. Estos casos son:

  1. P es interior al rectángulo de recorte,
    [IMAGEN]: Figura 30 - Se divide el plano en varias regiones con el punto P interior
    Figura 30 - Interior
  2. P está en una región exterior que hace esquina con el rectángulo de recorte, o
    [IMAGEN]: Figura 31 - Se divide el plano en varias regiones con el punto P en una esquina
    Figura 31 - Esquina
  3. P está en una región exterior que toca una arista del rectángulo de recorte.
    [IMAGEN]: Figura 31 - Se divide el plano en varias regiones con el punto P en un lateral
    Figura 32 - Lateral

En cada caso, podemos dividir nuevamente nuestro espacio en diferentes regiones para determinar dónde se encuentra el otro punto extremo, Q. Las nuevas divisiones se basan en crear vectores desde el punto conocido, P, a cada uno de los vértices del rectángulo de recorte. Al determinar si el punto extremo, Q, está a la izquierda de uno de estos vectores, de P a un vértice, podemos reducir las posibles regiones hasta encontrar la que contiene el punto, Q. Una vez que hayamos encontrado el punto, Q, y la región en la que se encuentra, podemos aplicar la ecuación de la intersección precisa para el caso en cuestión. Para los dos últimos casos, podemos pensar que los vectores de P a los vértices del rectángulo de recorte que son exteriores forman un "campo de visión". Cualquier punto dentro de este campo será visible y por tanto el segmento cruzará el rectángulo. Para el primer caso, usamos estos vectores simplemente para dividir el espacio en regiones para encontrar rápidamente el otro punto, Q, ya que sabemos de antemano que el segmento será visible, parcial o completamente.

Ejemplo

Descripción

[IMAGEN]: Figura 33 - Ejemplo del Algoritmo de Nicholl-Lee-Nicholl
Figura 33 - Ejemplo

Retomamos el mismo ejemplo del método exhaustivo. Tenemos un rectángulo de recorte cuya diagonal es de (-1,3) a (3,-3) que representa nuestra vista. Queremos mostrar el segmento AB, en tal rectángulo de recorte, descrito por los puntos,

A = ( -2, 1 )  y  B = ( 2, 2 )

Solución

[IMAGEN]: Figura 34 - Calculamos el código regional del punto A como criterio del algoritmo a usar
Figura 34 - Código Regional

Calculamos el código regional del punto A como hicimos en el método de Cohen-Sutherland:

A : 0001

Vemos que A está en una región lateral del rectángulo vertical de recorte. Esto significa que estamos ante el caso #2, en la figura 32.

Ahora nos toca descubrir la ubicación del punto B para determinar si hace falta recortar el segmento o no. Si es necesario recortar el segmento, debemos descubrir exactamente el punto de intersección. En principio, podemos comprobar si B está en alguna región vertical a la de A. Esto es,

Bx < R.xizq  ⇒  2 < -1

Como no es cierto, debemos continuar con el algoritmo.

[IMAGEN]: Figura 35 - Determinamos si B está a la izquierda o derecha de la línea AVis
Figura 35 - Esquina Izquierda Superior

Averiguamos si B está a la derecha o a la izquierda de una línea que contiene A y la esquina izquierda superior del rectángulo de recorte. Para ello, calculamos los siguientes vectores:

D = B - A = (  2,  2 ) - ( -2,  1 ) = (  4,  1 )
vis = ( R.xizq, R.ysup ) - A = ( -1,  3 ) - ( -2,  1 ) = (  1,  2 )

Aplicamos el mismo método que usamos en el algoritmo de Cyrus-Beck para determinar si un punto estaba a un lado o a otro de una línea recta. Calculamos el vector normal de vis - sin normalizar:

Nis = ( -2,  1 )

El signo de N ⋅ D nos indicará si B está a la izquierda o a la derecha:

( -2,  1 ) ⋅ (  4,  1 ) = (-2)*4 + 1*1 = -7 < 0

Como el signo es negativo, B está a la derecha y por tanto debemos continuar con el algoritmo.

[IMAGEN]: Figura 36 - Determinamos si B está a la izquierda o derecha de la línea AVds
Figura 36 - Esquina Derecha Superior

Averiguamos si B está a la derecha o a la izquierda de una línea que contiene A y la esquina derecha superior del rectángulo de recorte. Para ello, calculamos el vector de tal línea:

vds = ( R.xder, R.ysup ) - A = (  3,  3 ) - ( -2,  1 ) = (  5,  2 )

Calculamos el vector normal de vds:

Nds = ( -2,  5 )

El signo de N ⋅ D nos indicará si B está a la izquierda o a la derecha:

( -2,  5 ) ⋅ (  4,  1 ) = (-2)*4 + 5*1 = -3 < 0

Como el signo es negativo, B está a la derecha y por tanto debemos continuar con el algoritmo.

[IMAGEN]: Figura 37 - Determinamos si B está a la izquierda o derecha de la línea AVdi
Figura 37 - Esquina Derecha Inferior

Averiguamos si B está a la derecha o a la izquierda de una línea que contiene A y la esquina derecha inferior del rectángulo de recorte. Para ello, calculamos el vector de tal línea:

vdi = ( R.xder, R.yinf ) - A = (  3, -3 ) - ( -2,  1 ) = (  5, -4 )

Calculamos el vector normal de vdi:

Ndi = (  4,  5 )

El signo de N ⋅ D nos indicará si B está a la izquierda o a la derecha:

(  4,  5 ) ⋅ (  4,  1 ) = 4*4 + 5*1 = 21 > 0

Como el signo es positivo, B está a la izquierda de esta línea.

[IMAGEN]: Figura 38 - Determinamos si B está a la izquierda o derecha de la arista derecha
Figura 38 - Arista Derecha y Solución Final

Como B está a la izquierda de vdi pero a la derecha de vds, entonces sabemos que debemos recortar A con la arista izquierda:

A′x = R.xizq  ⇒  A′x = -1
A′y = Ay - (Ax - R.xizq) * Dy / Dx
    = 1 - (-2 - (-1)) * 1 / 4  ⇒  A′y = 1,25

B está o bien dentro del rectángulo de recorte o bien fuera. Esto implica que B está a la izquierda de la arista derecha del rectángulo, y por tanto es interior, o a la derecha, y por tanto se debe recortar. Realizamos una comprobación sencilla:

Bx < R.xder  ⇒  2 < 3

Por lo tanto, B está dentro y no necesitamos realizar ninguna intersección. El segmento AB se recorta quedando como,

A′B = ( -1,  1,25 )

Algoritmo

La función principal es Recortar(), la cual aceptará tres parámetros: dos puntos extremos, P y Q, donde cada uno contiene las coordenadas (x,y) que representan el segmento a recortar, y un rectángulo vertical, R, que contiene los elementos {xizq,ysup, xder,yinf} representando las coordenadas de las dos esquinas izquierda superior y derecha inferior. Para hallar la región en la que se encuentra el punto extremo, P, del segmento a recortar, podemos usar el algoritmo de Calcular_Código() de Cohen-Sutherland para conseguir un código representativo de la región. Por ello, volvemos a definir los códigos binarios para: SUPERIOR=8, INFERIOR=4, DERECHA=2, e IZQUIERDA=1.

Como existen tres casos principales, definimos tres algoritmos especializados para recortar un segmento: Recortar_Interior(), Recortar_Izquierda_Inferior(), y Recortar_Izquierda(). Para los otros seis casos, modificamos los puntos extremos, P y Q, aplicando traslaciones y reflejo debido a las propiedades simétricas para convertir cada caso en uno principal. Cada algoritmo especializado hará uso de otros dos tipos de algoritmos:

  • La función Izquierda() nos indicará si un punto está a la izquierda (verdadero) de una línea representada por dos puntos o no (falso). La función Derecha() realizará una comprobación parecida si un punto está a la derecha (verdadero) de una línea o no (falso).
  • Las funciones Intersección_Vertical() e Intersección_Horizontal() calcularán la intersección entre el segmento, representado como un vector de A a B, y una arista vertical u horizontal del rectángulo de recorte, respectivamente.
booleano Recortar( ref Punto P, ref Punto Q, Rectángulo R )
  1. tipo ← Calcular_Código( P, R )
  2. Si no, compruebe que tipo = INTERIOR, // Caso #1
  3. aceptar ← Recortar_Interior( P, Q, R )
  4. Si tipo = IZQUIERDA OR INFERIOR, entonces // Caso #2
  5. aceptar ← Recortar_Izquierda_Inferior( P, Q, R )
  6. Si no, compruebe que tipo = DERECHA OR INFERIOR,
  7. Tx ← (R.xizq + R.xder) / 2
  8. P.x ← Tx - P.x
  9. Q.x ← Tx - Q.x
  10. aceptar ← Recortar_Izquierda_Inferior( P, Q, R )
  11. P.x ← Tx - P.x
  12. Q.x ← Tx - Q.x
  13. Si no, compruebe que tipo = IZQUIERDA OR SUPERIOR,
  14. Ty ← (R.ysup + R.yinf) / 2
  15. P.y ← Ty - P.y
  16. Q.y ← Ty - Q.y
  17. aceptar ← Recortar_Izquierda_Inferior( P, Q, R )
  18. P.y ← Ty - P.y
  19. Q.y ← Ty - Q.y
  20. Si no, compruebe que tipo = DERECHA OR SUPERIOR,
  21. Tx ← (R.xizq + R.xder) / 2
  22. Ty ← (R.ysup + R.yinf) / 2
  23. P ← T - P
  24. Q ← T - Q
  25. aceptar ← Recortar_Izquierda_Inferior( P, Q, R )
  26. P ← T - P
  27. Q ← T - Q
  28. Si no, compruebe que tipo = IZQUIERDA, // Caso #3
  29. aceptar ← Recortar_Izquierda( P, Q, R )
  30. Si no, compruebe que tipo = DERECHA,
  31. Tx ← (R.xizq + R.xder) / 2
  32. P.x ← Tx - P.x
  33. Q.x ← Tx - Q.x
  34. aceptar ← Recortar_Izquierda( P, Q, R )
  35. P.x ← Tx - P.x
  36. Q.x ← Tx - Q.x
  37. Si no, compruebe que tipo = INFERIOR,
  38. Tx ← R.xizq
  39. Ty ← R.yinf
  40. P ← T - P
  41. Q ← T - Q
  42. aceptar ← Recortar_Izquierda( P, Q, R )
  43. P ← T - P
  44. Q ← T - Q
  45. Si no, compruebe que tipo = SUPERIOR,
  46. Tx ← R.xizq
  47. Ty ← R.ysup
  48. P ← T - P
  49. Q ← T - Q
  50. aceptar ← Recortar_Izquierda( P, Q, R )
  51. P ← T - P
  52. Q ← T - Q
  53. Terminar( aceptar )

Usamos el operador OR para indicar la operación OR a nivel de bits.

Aquí presentamos los algoritmos particulares para el recorte según la región donde se encuentra P, empezando por Recortar_Interior():

booleano Recortar_Interior( ref Punto P, ref Punto Q, Rectángulo R )
  1. aceptar ← verdadero
  2. PQ ← Q - P
  3. PVis ← (R.xizq,R.ysup) - P
  4. Si Izquierda( PQ, PVis ), entonces
  5. PVii ← (R.xizq,R.yinf) - P
  6. Si Izquierda( PQ, PVii ), entonces
  7. PVdi ← (R.xder,R.yinf) - P
  8. Si Izquierda( PQ, PVdi ), entonces
  9. Si Q.x > R.xder, entonces
  10. Q ← Intersección_Vertical( P, Q, R.xder )
  11. Si no, entonces
  12. Si Q.y < R.yinf, entonces
  13. Q ← Intersección_Horizontal( P, Q, R.yinf )
  14. Si no, entonces
  15. Si Q.x < R.xizq, entonces
  16. Q ← Intersección_Vertical( P, Q, R.xizq )
  17. Si no, entonces
  18. PVds ← (R.xder,R.ysup) - P
  19. Si Izquierda( PQ, PVds ), entonces
  20. Si Q.y > R.ysup, entonces
  21. Q ← Intersección_Horizontal( P, Q, R.ysup )
  22. Si no, entonces
  23. PVdi ← (R.xder,R.yinf) - P
  24. Si Izquierda( PQ, PVdi ), entonces
  25. Si Q.x > R.xder, entonces
  26. Q ← Intersección_Vertical( P, Q, R.xder )
  27. Si no, entonces
  28. Si Q.y < R.yinf, entonces
  29. Q ← Intersección_Horizontal( P, Q, R.yinf )
  30. Terminar( aceptar )

Aquí presentamos el algoritmo de Recortar_Izquierda_Inferior():

booleano Recortar_Izquierda_Inferior( ref Punto P, ref Punto Q, Rectángulo R )
  1. Si Q.x < R.xizq, entonces
  2. aceptar ← falso
  3. Si no, compruebe que Q.y < R.yinf,
  4. aceptar ← falso
  5. Si no, entonces
  6. PQ ← Q - P
  7. PVis ← (R.xizq,R.ysup) - P
  8. Si Izquierda( PQ, PVis ), entonces
  9. aceptar ← falso
  10. Si no, entonces
  11. PVds ← (R.xder,R.ysup) - P
  12. Si Izquierda( PQ, PVds ), entonces
  13. aceptar ← verdadero
  14. Si Q.y > R.ysup, entonces
  15. Q ← Intersección_Horizontal( P, Q, R.ysup )
  16. PVii ← (R.xizq,R.yinf) - P
  17. Si Izquierda( PQ, PVii ), entonces
  18. P ← Intersección_Vertical( P, Q, R.xizq )
  19. Si no, entonces
  20. P ← Intersección_Horizontal( P, Q, R.yinf )
  21. Si no, entonces
  22. PVdi ← (R.xder,R.yinf) - P
  23. Si Derecha( PQ, PVdi ), entonces
  24. aceptar ← falso
  25. Si no, entonces,
  26. aceptar ← verdadero
  27. Si Q.x > R.xder, entonces
  28. Q ← Intersección_Vertical( P, Q, R.xder )
  29. PVii ← (R.xizq,R.yinf) - P
  30. Si Izquierda( PQ, PVii ), entonces
  31. P ← Intersección_Vertical( P, Q, R.xizq )
  32. Si no, entonces
  33. P ← Intersección_Horizontal( P, Q, R.yinf )
  34. Terminar( aceptar )

Por último presentamos el algoritmo de Recortar_Izquierda():

booleano Recortar_Izquierda( ref Punto P, ref Punto Q, Rectángulo R )
  1. Si Q.x < R.xizq, entonces
  2. aceptar ← falso
  3. Si no, entonces
  4. PQ ← Q - P
  5. PVis ← (R.xizq,R.ysup) - P
  6. Si Izquierda( PQ, PVis ), entonces
  7. aceptar ← falso
  8. Si no, entonces
  9. PVds ← (R.xder,R.ysup) - P
  10. Si Izquierda( PQ, PVds ), entonces
  11. aceptar ← verdadero
  12. P ← Intersección_Vertical( P, Q, R.xizq )
  13. Si Q.y > R.ysup, entonces
  14. Q ← Intersección_Horizontal( P, Q, R.ysup )
  15. Si no, entonces
  16. PVdi ← (R.xder,R.yinf) - P
  17. Si Izquierda( PQ, PVdi ), entonces
  18. aceptar ← verdadero
  19. P ← Intersección_Vertical( P, Q, R.xizq )
  20. Si Q.x > R.xder, entonces
  21. Q ← Intersección_Vertical( P, Q, R.xder )
  22. Si no, entonces
  23. PVii ← (R.xizq,R.yinf) - P
  24. Si Derecha( PQ, PVii ), entonces
  25. aceptar ← falso
  26. Si no, entonces
  27. aceptar ← verdadero
  28. P ← Intersección_Vertical( P, Q, R.xizq )
  29. Si Q.y < R.yinf, entonces
  30. Q ← Intersección_Horizontal( P, Q, R.yinf )
  31. Terminar( aceptar )

Estos cuatro algoritmos son auxiliares para los algoritmos de recorte.

booleano Izquierda( Vector A, Vector B )
  1. Si -B.y * A.x + B.x * A.y > 0, entonces
  2. Terminar( verdadero )
  3. Si no, entonces
  4. Terminar( falso )
booleano Derecha( Vector A, Vector B )
  1. Si -B.y * A.x + B.x * A.y < 0, entonces
  2. Terminar( verdadero )
  3. Si no, entonces
  4. Terminar( falso )

Podemos implementar este algoritmo como un caso especial de Izquierda(). Esto es,

booleano Derecha( Vector A, Vector B )
  1. Terminar( Izquierda( -A, B ) )

Por lo tanto, podríamos prescindir del uso de este algoritmo, Derecha().

Punto Intersección_Vertical( Punto A, Punto B, real Arista )
  1. D ← B.x - A.x
  2. Si D = 0, entonces
  3. Resultado.x ← Arista
  4. Resultado.y ← A.y
  5. Si no, entonces
  6. Resultado.x ← Arista
  7. Resultado.y ← A.y - (B.y - A.y) * (A.x - Arista) / D
  8. Terminar( Resultado )
Punto Intersección_Horizontal( Punto A, Punto B, real Arista )
  1. D ← B.y - A.y
  2. Si D = 0, entonces
  3. Resultado.x ← A.x
  4. Resultado.y ← Arista
  5. Si no, entonces
  6. Resultado.x ← A.x - (B.x - A.x) * (A.y - Arista) / D
  7. Resultado.y ← Arista
  8. Terminar( Resultado )

Algoritmo de Sutherland-Hodgman

Este algoritmo se basa en recortar el polígono parcialmente usando cada lado del rectángulo vertical de recorte hasta terminar con la intersección final, interior al rectángulo. El polígono a recortar se representa como una lista de vértices: v1,v2,v3,...,vn. Nos interesa que esta lista de vértices esté ordenada para que cada pareja contigua de vértices represente una arista del polígono. Esto significa que ordenaremos la lista geométricamente en el sentido de las agujas del reloj o en el sentido contrario, según elijamos. Los vértices vi y vi+1 describen una arista del polígono, hasta llegar a vn que forma la última arista con el vértice, v1. Cada recorte del polígono generará una nueva lista de vértices que representará el nuevo polígono resultante del recorte.

Para cada recorte por el lado del rectángulo, existen cuatro casos a comprobar para cada pareja de vértices que representa una arista del polígono a recortar. Según las regiones formadas por cada lado de recorte, los vértices se encontrarán dentro o fuera de ellas. Éstos son:

  1. Si ambos vértices están dentro, entonces sólo agregamos el segundo vértice a la lista resultante de vértices.
    [IMAGEN]: Figura 39 - Ambos vértices están dentro
    Figura 39 - Ambos vértices están dentro
  2. Si el primer vértice está dentro de la arista, pero el segundo está fuera, entonces calculamos el punto de intersección. Sólo agregamos este punto de intersección a la lista resultante de vértices.
    [IMAGEN]: Figura 40 - El primer vértice está dentro, pero el segundo está fuera
    Figura 40 - De un vértice interior a otro exterior
  3. Si el primer vértice está fuera de la arista, pero el segundo está dentro, entonces tenemos que calcular el punto de intersección. Este punto de intersección y el segundo vértice son agregados a la lista resultante de vértices.
    [IMAGEN]: Figura 41 - El primer vértice está fuera, pero el segundo está dentro
    Figura 41 - De un vértice exterior a otro interior
  4. Si ambos vértices están fuera, entonces no modificamos la lista resultante de vértices.
    [IMAGEN]: Figura 42 - Ambos vértices están fuera
    Figura 42 - Ambos vértices están fuera

Pasamos la lista resultante de vértices como la lista entrante al mismo algoritmo para las demás aristas del rectángulo.

Ejemplo

Descripción

[IMAGEN]: Figura 43 - Ejemplo del Algoritmo de Sutherland-Hodgman
Figura 43 - Ejemplo

Tenemos un rectángulo vertical de recorte cuya diagonal es de (-1,3) a (3,-3) que representa nuestra vista. Queremos un polígono (convexo), en tal rectángulo de recorte, descrito por la siguiente lista de vértices:

{ (-2,1), (1,4), (4,3), (3,0), (0,-4), (-2,-4), (-3,-1) }

Solución

[IMAGEN]: Figura 44 - Recortamos el polígono con el lado izquierdo del rectángulo de recorte
Figura 44 - Recorte con el Lado Izquierdo

Empezamos el recorte de nuestro polígono con el lado izquierdo de nuestro rectángulo vertical de recorte que es xizq = -1. Elegimos cada arista de nuestro polígono y la comprobamos según su caso, mencionado previamente. También creamos una lista de vértices para representar el polígono resultante del recorte.

Vemos que de v1 a v2, se nos presenta el caso #3, ya que v1 está fuera del lado del rectángulo y v2 está dentro. Por lo tanto, calculamos el punto de intersección del segmento con xizq = -1,

Px = xizq = -1
                           v2y - v1y
Py = v2y + (xizq - v2x) * ----------
                           v2x - v1x
   = 4 + (-1 - 1) * 3 / 3 = 2

Agregamos este punto de intersección y el vértice v2 a la lista resultante de vértices, en este orden. La lista resultante es ahora:

{ (-1,2), (1,4) }

Comprobamos el segmento de v2 a v3. Como ambos son interiores al lado izquierdo del rectángulo de recorte, estamos ante el caso #1, por lo que agregamos v3 a la lista resultante. La lista resultante es ahora:

{ (-1,2), (1,4), (4,3) }

Comprobamos el segmento de v3 a v4. Como ambos son interiores al lado izquierdo del rectángulo de recorte, estamos ante el caso #1, por lo que agregamos v4 a la lista resultante. La lista resultante es ahora:

{ (-1,2), (1,4), (4,3), (3,0) }

Comprobamos el segmento de v4 a v5. Como ambos son interiores al lado izquierdo del rectángulo de recorte, estamos ante el caso #1, por lo que agregamos v5 a la lista resultante. La lista resultante es ahora:

{ (-1,2), (1,4), (4,3), (3,0), (0,-4) }

Vemos que el segmento de v5 a v6 trata del caso #2. Por lo tanto, calculamos el punto de intersección del segmento con xizq = -1,

Px = xizq = -1
                           v6y - v5y
Py = v6y + (xizq - v6x) * ----------
                           v6x - v5x
   = -4 + (-1 - (-2)) * 0 / 2 = -4

Agregamos este punto de intersección a la lista resultante de vértices. La lista resultante es ahora:

{ (-1,2), (1,4), (4,3), (3,0), (0,-4), (-1,-4) }

Comprobando los dos últimos segmentos, v6 a v7 y v7 a v1, vemos que están fuera. Por lo tanto, no agregamos ningún vértice a la lista resultante. Al final, la lista resultante es:

{ (-1,2), (1,4), (4,3), (3,0), (0,-4), (-1,-4) }
[IMAGEN]: Figura 45 - Recortamos el polígono con el lado superior del rectángulo de recorte
Figura 45 - Recorte con el Lado Superior

Continuamos el recorte con el lado superior de nuestro rectángulo vertical de recorte que es ysup = 3. Elegimos cada arista de nuestro polígono actual, previamente recortado, y la comprobamos según su caso, mencionado previamente.

Vemos que de v1 a v2, se nos presenta el caso #2, ya que v1 está dentro del lado del rectángulo y v2 está fuera. Por lo tanto, calculamos el punto de intersección del segmento con ysup = 3,

                           v2x - v1x
Px = v2x + (ysup - v2y) * ----------
                           v2y - v1y
   = 1 + (3 - 4) * 2 / 2 = 0
Py = ysup = 3

Agregamos este punto de intersección a la lista resultante de vértices. La lista resultante es ahora:

{ (0,3) }

Comprobamos que el segmento de v2 a v3 presenta el caso #3, ya que v2 está fuera del lado del rectángulo y v3 está (justo) dentro. Por lo tanto, calculamos el punto de intersección del segmento con ysup = 3,

                           v3x - v2x
Px = v3x + (ysup - v3y) * ----------
                           v3y - v2y
   = 4 + (3 - 3) * 3 / (-1) = 4
Py = ysup = 3

Agregamos este punto de intersección y el vértice v3 a la lista resultante de vértices, en este orden. La lista resultante es ahora:

{ (0,3), (4,3), (4,3) }

Comprobando el resto de los segmentos vemos que están dentro del semiplano, ysup = 3. Por lo tanto, agregamos los segundos vértices de cada segmento a la lista resultante. Al final, la lista resultante es:

{ (0,3), (4,3), (4,3), (3,0), (0,-4), (-1,-4), (-1,2) }
[IMAGEN]: Figura 46 - Recortamos el polígono con el lado derecho del rectángulo de recorte
Figura 46 - Recorte con el Lado Derecho

Continuamos el recorte con el lado derecho de nuestro rectángulo vertical de recorte que es xder = 3. Elegimos cada arista de nuestro polígono actual, previamente recortado, y la comprobamos según su caso, mencionado previamente.

Vemos que de v1 a v2, se nos presenta el caso #2, ya que v1 está dentro del lado del rectángulo y v2 está fuera. Por lo tanto, calculamos el punto de intersección del segmento con xder = 3,

Px = xder = 3
                           v2y - v1y
Py = v2y + (xder - v2x) * ----------
                           v2x - v1x
   = 3 + (3 - 4) * 0 / 4 = 3

Agregamos este punto de intersección a la lista resultante de vértices. La lista resultante es ahora:

{ (3,3) }

Como el "segmento" de v2 a v3 está fuera del semiplano, xder = 3, no agregamos ninguno de los dos vértices. La lista resultante sigue siendo:

{ (3,3) }

Comprobamos que el segmento de v3 a v4 presenta el caso #3, ya que v3 está fuera del lado del rectángulo y v4 está (justo) dentro. Por lo tanto, calculamos el punto de intersección del segmento con xder = 3,

Px = xder = 3
                           v4y - v3y
Py = v4y + (xder - v4x) * ----------
                           v4x - v3x
   = 0 + (3 - 3) * (-3) / (-1) = 0

Agregamos este punto de intersección y el vértice v3 a la lista resultante de vértices, en este orden. La lista resultante es ahora:

{ (3,3), (3,0), (3,0) }

Comprobando el resto de los segmentos vemos que están dentro del semiplano, xder = 3. Por lo tanto, agregamos los segundos vértices de cada segmento a la lista resultante. Al final, la lista resultante es:

{ (3,3), (3,0), (3,0), (0,-4), (-1,-4), (-1,2), (0,3) }
[IMAGEN]: Figura 47 - Recortamos el polígono con el lado inferior del rectángulo de recorte
Figura 47 - Recorte con el Lado Inferior

Continuamos el recorte con el lado inferior de nuestro rectángulo vertical de recorte que es yinf = -3. Elegimos cada arista de nuestro polígono actual, previamente recortado, y la comprobamos según su caso, mencionado previamente.

Comprobamos que tanto el segmento de v1 a v2 como el "segmento" de v2 a v3 están dentro del semiplano, yinf = -3. Por lo tanto, agregamos los segundos vértices de cada segmento a la lista resultante. Al final, la lista resultante es:

{ (3,0), (3,0) }

Vemos que de v3 a v4, se nos presenta el caso #2, ya que v3 está dentro del lado del rectángulo y v4 está fuera. Por lo tanto, calculamos el punto de intersección del segmento con yinf = -3,

                           v4x - v3x
Px = v4x + (yinf - v4y) * ----------
                           v4y - v3y
   = 0 + (-3 - (-4)) * (-3) / (-4) = 0,75
Py = yinf = -3

Agregamos este punto de intersección a la lista resultante de vértices. La lista resultante es ahora:

{ (3,0), (3,0), (0,75, -3) }

Como el segmento de v4 a v5 está fuera del semiplano, yinf = -3, no agregamos ninguno de los dos vértices. La lista resultante sigue siendo:

{ (3,0), (3,0), (0,75, -3) }

Comprobamos que el segmento de v5 a v6 presenta el caso #3, ya que v5 está fuera del lado del rectángulo y v6 está dentro. Por lo tanto, calculamos el punto de intersección del segmento con yinf = -3,

                           v6x - v5x
Px = v6x + (yinf - v6y) * ----------
                           v6y - v5y
   = -1 + (-3 - 2) * 0 / 6 = -1
Py = yinf = -3

Agregamos este punto de intersección y el segundo vértice, v6, a la lista resultante de vértices. La lista resultante es ahora:

{ (3,0), (3,0), (0,75, -3), (-1,-3), (-1,2) }

Comprobando el resto de los segmentos vemos que están dentro del semiplano, yinf = -3. Por lo tanto, agregamos los segundos vértices de cada segmento a la lista resultante. Al final, la lista resultante es:

{ (3,0), (3,0), (0,75, -3), (-1,-3), (-1,2), (0,3), (3,3) }
[IMAGEN]: Figura 48 - El polígono resultante sin vértices contiguos repetidos
Figura 48 - Solución Final

Vemos que el polígono final contiene vértices contiguos repetidos, por lo que podemos procesar nuestra lista de vértices para eliminar las repeticiones. Al final, nos queda la siguiente lista de vértices:

{ (3,0), (0,75, -3), (-1,-3), (-1,2), (0,3), (3,3) }

Algoritmo

El algoritmo se basa en el pseudo-código principal, Recortar(). Tenemos otros algoritmos auxiliares:

  • Recortar_Lado() sirve para recortar un segmento descrito por dos vértices por un lado particular del rectángulo de recorte. También se requiere la lista resultante de vértices para poder agregar nuevos vértices a ella. La salida es la misma lista resultante actualizada de los vértices del polígono recortado.
  • Interior() indica si un punto se considera candidato como interior (verdadero) al rectángulo de recorte o se acepta como exterior (falso).
  • Intersectar() calcula el punto de intersección entre un segmento y un lado dado del rectángulo de recorte.

Presentamos el algoritmo para Recortar():

Polígono Recortar( Polígono P, Rectángulo R )
  1. Resultado, Actual : Polígono
  2. Actual ← P
  3. Para cada lado de R, repetir
  4. Resultado ← vacío // Resultado es un polígono vacío
  5. Para: i ← 1 hasta n, repetir
  6. Resultado ← Recortar_Lado( Actual.vi, Actual.vi+1, lado, R, Resultado )
  7. Resultado ← Recortar_Lado( Actual.vn, Actual.v1, lado, R, Resultado ) // Recortamos la última arista de Actual: vnv1
  8. Actual ← Resultado
  9. Resultado ← Eliminar_Repeticiones( Resultado )
  10. Terminar( Resultado )

Eliminar_Repeticiones() recorre la lista dada de vértices del polígono para eliminar repeticiones contiguas. También hay que comprobar el último vértice con el primero, ya que forman un segmento.

He aquí el algoritmo de Recortar_Lado() que modifica el polígono, Resultado, y lo regresa al terminar:

Polígono Recortar_Lado( Punto v1, Punto v2, Lado L, Rectángulo R, ref Polígono Resultado )
  1. interior1 ← Interior( v1, L, R )
  2. interior2 ← Interior( v2, L, R )
  3. Si interior1 = verdadero, entonces
  4. Si interior2 = verdadero, entonces
  5. Resultado.Agregar( v2 )
  6. Si no, entonces,
  7. P ← Intersectar( v1, v2, L, R )
  8. Resultado.Agregar( P )
  9. Si no, compruebe que interior2 = verdadero,
  10. P ← Intersectar( v1, v2, L, R )
  11. Resultado.Agregar( P )
  12. Resultado.Agregar( v2 )
  13. Terminar( Resultado )

Agregar() se refiere a la operación básica para agregar un punto a la lista de vértices de un polígono.

Exponemos la lógica de Interior():

booleano Interior( Punto v, Lado L, Rectángulo R )
  1. Si L = Izquierdo, entonces
  2. Si vx ≥ R.xizq, entonces
  3. bEsInterior ← verdadero
  4. Si no, entonces
  5. bEsInterior ← falso
  6. Si no, compruebe que L = Superior, entonces
  7. Si vy ≤ R.ysup, entonces
  8. bEsInterior ← verdadero
  9. Si no, entonces
  10. bEsInterior ← falso
  11. Si no, compruebe que L = Derecho, entonces
  12. Si vx ≤ R.xder, entonces
  13. bEsInterior ← verdadero
  14. Si no, entonces
  15. bEsInterior ← falso
  16. Si no, compruebe que L = Inferior, entonces
  17. Si vy ≥ R.yinf, entonces
  18. bEsInterior ← verdadero
  19. Si no, entonces
  20. bEsInterior ← falso
  21. Terminar( bEsInterior )

Este algoritmo para Intersectar() involucra un rectángulo vertical de recorte:

Punto Intersectar( Punto v1, Punto v2, Lado L, Rectángulo R )
  1. dx ← v2.x - v1.x
  2. dy ← v2.y - v1.y
  3. Si L = Izquierdo, entonces
  4. P.x ← R.xizq
  5. Si dx ≠ 0, entonces
  6. P.y ← v2.y + (R.xizq - v2.x) * dy / dx
  7. Si no, entonces
  8. P.y ← v2.y
  9. Si no, compruebe que L = Superior, entonces
  10. Si dy ≠ 0, entonces
  11. P.x ← v2.x + (R.ysup - v2.y) * dx / dy
  12. Si no, entonces
  13. P.x ← v2.x
  14. P.y ← R.ysup
  15. Si no, compruebe que L = Derecho, entonces
  16. P.x ← R.xder
  17. Si dx ≠ 0, entonces
  18. P.y ← v2.y + (R.xder - v2.x) * dy / dx
  19. Si no, entonces
  20. P.y ← v2.y
  21. Si no, compruebe que L = Inferior, entonces
  22. Si dy ≠ 0, entonces
  23. P.x ← v2.x + (R.yinf - v2.y) * dx / dy
  24. Si no, entonces
  25. P.x ← v2.x
  26. P.y ← R.yinf
  27. Terminar( P )

Algoritmo de Liang-Barsky

[IMAGEN]: Figura 49 - Se agrega el vértice de giro, que es un vértice del rectángulo de recorte
Figura 49 - Vértice de Giro

El algoritmo de Liang-Barsky para recortar líneas puede ser ampliado para recortar polígonos en un rectángulo vertical. La idea principal de este algoritmo se basa en la detección de vértices de giro. Un vértice de giro es aquel vértice de la esquina del rectángulo de recorte que formará parte del polígono recortado. Esta posibilidad existe si una arista del polígono a recortar cruza un lado del rectángulo de recorte seguida de una o más aristas que giran entorno a la esquina del rectángulo de recorte, para volver a cruzar el rectángulo por otro lado. Si esto ocurriere, entonces agregaríamos este vértice de giro a nuestra lista de vértices resultante que representa el polígono recortado.

Fijémonos en varios casos de intersección de líneas rectas diagonales - aquéllas que no son verticales ni horizontales. Extendemos las aristas del rectángulo vertical para que sean líneas y así creamos nueve regiones: ocho externas y una interna. Esto implica que una línea diagonal cruza de una esquina regional a otra esquina opuesta.

Si parte de un segmento del polígono yace dentro del rectángulo de recorte, entonces esa parte debe pertenecer al polígono resultante. Debemos agregar los vértices de este segmento, dependiendo de las circunstancias:

  • El segmento yace completamente en el interior del rectángulo de recorte, por lo que ambos extremos del segmento son agregados a la lista de vértices del polígono resultante.
  • El segmento yace parcialmente en el interior, con un extremo dentro del rectángulo de recorte. Esto implica que hay que calcular el punto de intersección con un lado del rectángulo. Se agrega el extremo interior del segmento y el punto de intersección a la lista de vértices del polígono resultante.
  • El segmento yace parcialmente en el interior, pero ambos puntos extremos yacen fuera del rectángulo de recorte. Esto supone calcular dos puntos de intersección con dos lados diferentes del rectángulo. Ambos puntos de intersección son agregados a la lista de vértices del polígono resultante.

Por otro lado, podemos tener el caso de que el segmento no cruce el interior del rectángulo de recorte, pero el siguiente segmento que representa una arista del polígono sí puede cruzar el rectángulo. Como nos limitamos a mirar cada arista según su primer vértice, podemos determinar el lado del rectángulo, si se empieza en una región adyacente a un lado, que el segmento puede cruzar, o entre dos lados, si se empieza en una esquina.

Volviendo al tema del vértice de giro, agregamos tal vértice a la lista de vértices resultante, cuando una arista entra una esquina.

El algoritmo original propuesto por Liang y Barsky funciona de otra manera. Se agrega el vértice de giro a la lista resultante cuando una arista abandona la esquina. Sin embargo, esto no elimina el problema de la arista degenerada y además complica la lectura del algoritmo más de la cuenta. Por lo tanto, usaremos nuestra versión del algoritmo.

Basándonos en la solución dada por Liang y Barsky para recortar segmentos, haremos uso de la ecuación paramétrica de una línea recta y analizaremos los cuatro valores del parámetro, t, debidos a las cuatro intersecciones de la línea, que contiene la arista, con las líneas formadas por las extensiones de los lados del rectángulo de recorte. Dos valores son considerados potencialmente entrantes: te1 y te2 y los otros dos son considerados potencialmente salientes: ts1 y ts2. Tomemos nota de que te1 es el menor y ts2 es el mayor de los cuatro valores calculados; los otros dos valores pueden estar en cualquier orden. Como explicamos en el apartado del algoritmo de Liang-Barsky para recortar segmentos, si te2ts1, entonces la línea cruza el rectángulo de recorte; si te2 > ts1, entonces la línea pasa de una esquina a otra.

[IMAGEN]: Figura 50 - Diferentes casos de los cuatro parámetros de puntos de intersección
Figura 50 - Varios casos de segmentos

Como ya sabemos, los valores de t deben estar comprendidos entre 0 y 1 para representar el segmento, donde t=0 implica un punto extremo y t=1 se refiere al otro. Estableciendo la relación entre estos valores paramétricos y los cuatro valores de las intersecciones, podemos determinar la contribución de la arista al polígono recortado resultante. Si 0 < ts1 y te2 ≤ 1, entonces la arista comienza o incluso puede terminar dentro del rectángulo. Como existe una parte visible de esta arista, debemos agregarla a nuestro polígono recortado.

Si la arista no cruza el rectángulo de recorte, entonces la línea, donde yace la arista, atraviesa tres esquinas: dos opuestas entre sí y una en el medio. Si la arista yace en cualquiera de estas dos esquinas opuestas, entonces se debe agregar un vértice de giro a la lista de vértices resultante. Entrada a esta esquina del medio, se comprueba con 0 < ts1 ≤ 1. Entrando la última esquina se comprueba con 0 < ts2 ≤ 1, que también es válida para el caso de que la arista cruce el rectángulo de recorte, y por tanto se debe agregar el vértice de giro.

El problema del algoritmo es que tenemos que tratar los casos especiales cuando las aristas son horizontales o verticales. Una solución es considerar cada caso cuando se presente, aplicando otra lógica especial que requiere un análisis para cada caso. La otra solución es describir estas aristas de tal manera que podamos usar la misma lógica del algoritmo para todas las aristas. Para implementar esta solución, asignamos los valores de +∞ y -∞ para los parámetros entrantes y salientes.

[IMAGEN]: Figura 51 - Polígono recortado junto con las condiciones satisfechas
Figura 51 - Resultado del Recorte

Ejemplo

Descripción

[IMAGEN]: Figura 52 - Ejemplo del Algoritmo de Liang-Barsky
Figura 52 - Ejemplo

Retomamos el mismo ejemplo anterior del método de Sutherland-Hodgman. Tenemos un rectángulo vertical de recorte cuya diagonal es de (-1,3) a (3,-3) que representa nuestra vista. Queremos un polígono, en tal rectángulo de recorte, a partir del polígono, P, descrito por la siguiente lista de vértices:

P : { (-2,1), (1,4), (4,3), (3,0), (0,-4), (-2,-4), (-3,-1) }

Solución

[IMAGEN]: Figura 53 - Analizamos la primera arista del polígono
Figura 53 - Primera Arista

Creamos una lista de vértices, Q, para representar el polígono resultante del recorte, inicialmente vacía:

Q : {}

Empezamos el recorte de nuestro polígono analizando el primer segmento formado por v1v2. Calculamos las cuatro intersecciones y las clasificamos a través de sus parámetros.

Δx = v2x - v1x = 1 - (-2) = 3
Δy = v2y - v1y = 4 - 1 = 3

te1 =  (v1y - yinf) / -Δy =  ( 1 - (-3) ) / (-3) = -1,3333
te2 = -(v1x - xizq) /  Δx = -( (-2) - (-1) ) / 3 =  0,3333
ts1 = -(v1y - ysup) /  Δy = -( 1 - 3 ) / 3       =  0,6667
ts2 =  (v1x - xder) / -Δx =  ( (-2) - 3 ) / (-3) =  1,6667

Como ts2 > 0, te2ts1, 0 < ts1 y te2 ≤ 1, el segmento es completa o parcialmente visible en el rectángulo de recorte. Como te2 > 0, calculamos el punto de intersección

(x,y) = v1 + te2 * (Δxy) = (-2,1) + 0,3333 * (3,3)
      = (-1,2)

y lo agregamos a la lista resultante, Q. La lista resultante es ahora:

Q : { (-1,2) }

Como ts1 < 1, calculamos el punto de intersección

(x,y) = v1x + ts1 * (Δxy) = (-2,1) + 0,6667 * (3,3)
      = (0,3)

y lo agregamos a la lista resultante, Q. La lista resultante es ahora:

Q : { (-1,2), (0,3) }
[IMAGEN]: Figura 54 - Analizamos la segunda arista del polígono
Figura 54 - Segunda Arista

Seguimos con el análisis con el segundo segmento formado por v2v3. Calculamos las cuatro intersecciones y las clasificamos a través de sus parámetros.

Δx = v3x - v2x = 4 - 1 = 3
Δy = v3y - v2y = 3 - 4 = -1

te1 = -(v2x - xizq) /  Δx = -( 1 - (-1) ) / 3     = -0,6667
te2 = -(v2y - ysup) /  Δy = -( 4 - 3 ) / (-1)     =  1
ts1 =  (v2x - xder) / -Δx =  ( 1 - 3 ) / (-3)     =  0,6667
ts2 =  (v2y - yinf) / -Δy =  ( 4 - (-3) ) / -(-1) =  7

Aunque ts2 > 0, te2 > ts1, el segmento no es visible en el rectángulo de recorte. Sin embargo, como 0 < ts1 ≤ 1, agregamos el vértice de giro: (3,3) a la lista resultante, Q. La lista resultante es ahora:

Q : { (-1,2), (3,3) }

Como ts2 > 1, no agregamos el otro vértice de giro: (3,-3).

[IMAGEN]: Figura 55 - Analizamos la tercera arista del polígono
Figura 55 - Tercera Arista

Analicemos el tercer segmento formado por v3v4. Calculamos las cuatro intersecciones y las clasificamos a través de sus parámetros.

Δx = v4x - v3x = 3 - 4 = -1
Δy = v4y - v3y = 0 - 3 = -3

te1 = -(v3y - ysup) /  Δy = -( 3 - 3 ) / (-3)     = 0
te2 =  (v3x - xder) / -Δx =  ( 4 - 3 ) / -(-1)    = 1
ts1 =  (v3y - yinf) / -Δy =  ( 3 - (-3) ) / -(-3) = 2
ts2 = -(v3x - xizq) /  Δx = -( 4 - (-1) ) / (-1)  = 5

Como ts2 > 0, te2ts1, 0 < ts1 y te2 ≤ 1, el segmento es completa o parcialmente visible en el rectángulo de recorte. Como te2 > 0, calculamos el punto de intersección:

(x,y) = v3 + te2 * (Δxy) = (4,3) + 1 * (-1,-3)
      = (3,0)

y lo agregamos a la lista resultante, Q. La lista resultante es ahora:

Q : { (-1,2), (3,3), (3,0) }

Como ts1 ≥ 1, agregamos el vértice final del segmento, (3,0), a la lista resultante que es ahora:

Q : { (-1,2), (3,3), (3,0), (3,0) }

Como ts2 ≥ 1, no agregamos un vértice de giro.

[IMAGEN]: Figura 56 - Analizamos la cuarta arista del polígono
Figura 56 - Cuarta Arista

Analicemos el cuarto segmento formado por v4v5. Calculamos las cuatro intersecciones y las clasificamos a través de sus parámetros.

Δx = v5x - v4x =  0 - 3 = -3
Δy = v5y - v4y = -4 - 0 = -4

te1 = -(v4y - ysup) /  Δy = -( 0 - 3 ) / (-4)     = -0,75
te2 =  (v4x - xder) / -Δx =  ( 3 - 3 ) / -(-3)    =  0
ts1 =  (v4y - yinf) / -Δy =  ( 0 - (-3) ) / -(-4) =  0,75
ts2 = -(v4x - xizq) /  Δx = -( 3 - (-1) ) / (-3)  =  1,3333

Como ts2 > 0, te2ts1, 0 < ts1 y te2 ≤ 1, el segmento es completa o parcialmente visible en el rectángulo de recorte. Como te2 ≤ 0, agregamos el vértice inicial del segmento, (3,0), a la lista resultante que es ahora:

Q : { (-1,2), (3,3), (3,0), (3,0), (3,0) }

Como ts1 < 1, calculamos la intersección:

(x,y) = v4 + ts1 * (Δxy) = (3,0) + 0,75 * (-3,-4)
      = (0,75, -3)

y lo agregamos a la lista resultante, Q. La lista resultante es ahora:

Q : { (-1,2), (3,3), (3,0), (3,0), (3,0), (0,75, -3) }

Como ts2 ≥ 1, no agregamos un vértice de giro.

[IMAGEN]: Figura 57 - Analizamos la quinta arista del polígono
Figura 57 - Quinta Arista

Analicemos el quinto segmento formado por v5v6. Calculamos las cuatro intersecciones y las clasificamos a través de sus parámetros.

Δx = v6x - v5x = -2 - 0 = -2
Δy = v6y - v5y = -4 - (-4) = 0

te1 = -∞
te2 =  (v5x - xder) / -Δx =  ( 0 - 3 ) / -(-2)    = -1,5
ts1 = -∞
ts2 = -(v5x - xizq) /  Δx = -( 0 - (-1) ) / (-2)  =  0,5

Aunque ts2 > 0, ts1 < te2 y por tanto, el segmento no es visible en el rectángulo de recorte. Como 0 < ts2 ≤ 1, agregamos el vértice de giro, (-1,-3) a la lista resultante, Q. La lista resultante es ahora:

Q : { (-1,2), (3,3), (3,0), (3,0), (3,0), (0,75, -3), (-1,-3) }
[IMAGEN]: Figura 58 - Analizamos la sexta arista del polígono
Figura 58 - Sexta Arista

Analicemos el sexto segmento formado por v6v7. Calculamos las cuatro intersecciones y las clasificamos a través de sus parámetros.

Δx = v7x - v6x = -3 - (-2) = -1
Δy = v7y - v6y = -1 - (-4) =  3

te1 =  (v6x - xder) / -Δx =  ( -2 - 3 ) / -(-1)   = -5
te2 =  (v6y - yinf) / -Δy =  ( -4 - (-3) ) / (-3) =  0,3333
ts1 = -(v6x - xizq) /  Δx = -( -2 - (-1) ) / (-1) = -1
ts2 = -(v6y - ysup) /  Δy = -( -4 - 3 ) / 3       =  2,3333

Aunque ts2 > 0, ts1 < te2 y por tanto, el segmento no es visible en el rectángulo de recorte. Como ts2 > 1, no agregamos un vértice de giro. La lista resultante sigue siendo:

Q : { (-1,2), (3,3), (3,0), (3,0), (3,0), (0,75, -3), (-1,-3) }
[IMAGEN]: Figura 59 - Analizamos la última arista del polígono
Figura 59 - Séptima y Última Arista

Analicemos el último segmento formado por v7v1. Calculamos las cuatro intersecciones y las clasificamos a través de sus parámetros.

Δx = v1x - v7x = -2 - (-3) = 1
Δy = v1y - v7y =  1 - (-1) = 2

te1 =  (v7y - yinf) / -Δy =  ( -1 - (-3) ) / (-2) = -2
te2 = -(v7x - xizq) /  Δx = -( -3 - (-1) ) / 1    =  2
ts1 = -(v7y - ysup) /  Δy = -( -1 - 3 ) / 2       =  2
ts2 =  (v7x - xder) / -Δx =  ( -3 - 3 ) / (-1)    =  6

Aunque ts2 > 0, te2ts1, y 0 < ts1, el segmento no es visible en el rectángulo de recorte ni se agrega ninguna intersección, porque te2 > 1. Como ts2 > 1, tampoco agregamos un vértice de giro. La lista resultante sigue siendo:

Q : { (-1,2), (3,3), (3,0), (3,0), (3,0), (0,75, -3), (-1,-3) }
[IMAGEN]: Figura 60 - El polígono resultante
Figura 60 - Solución Final

Como existen puntos contiguos repetidos en la lista de vértices del polígono resultante, nos interesaría eliminarlos. Al final, la lista resultante es:

{ (-1,2), (3,3), (3,0), (0,75, -3), (-1,-3) }

Algoritmo

Presentamos el algoritmo detallado y optimizado para Recortar() basado en el algoritmo presentado por Foley en su libro:

Polígono Recortar( Polígono P, Rectángulo R )
  1. Crear Polígono: Resultado ← vacío
  2. P.Agregar( P.v[1].x, P.v[1].y ) // Agregamos el primer vértice al final
  3. Para: i ← 1 hasta P.cantidad, repetir
  4. dx ← P.v[i+1].x - P.v[i].x
  5. dy ← P.v[i+1].y - P.v[i].y
  6. Si dx > 0, o Si dx = 0 y P.v[i].x > R.xder, entonces
  7. xe ← R.xizq
  8. xs ← R.xder
  9. Si no, entonces
  10. xe ← R.xder
  11. xs ← R.xizq
  12. Si dy > 0, o Si dy = 0 y P.v[i].y > R.ysup, entonces
  13. ye ← R.yinf
  14. ys ← R.ysup
  15. Si no, entonces
  16. ye ← R.ysup
  17. ys ← R.yinf
  18. Si dx ≠ 0, entonces
  19. tXs ← ( xs - P.v[i].x ) / dx
  20. Si no, compruebe Si R.xizq ≤ P.v[i].x ≤ R.xder, entonces
  21. tXs ← ∞
  22. Si no, entonces
  23. tXs ← -∞
  24. Si dy ≠ 0, entonces
  25. tYs ← ( ys - P.v[i].y ) / dy
  26. Si no, compruebe Si R.yinf ≤ P.v[i].y ≤ R.ysup, entonces
  27. tYs ← ∞
  28. Si no, entonces
  29. tYs ← -∞
  30. // Ordenamos los dos puntos salientes
  31. Si tXs < tYs, entonces
  32. t1s ← tXs
  33. t2s ← tYs
  34. Si no, entonces
  35. t1s ← tYs
  36. t2s ← tXs
  37. Si t2s > 0, entonces // Calculamos t2e
  38. Si dx ≠ 0, entonces
  39. tXe ← ( xe - P.v[i].x ) / dx
  40. Si no, entonces
  41. tXe ← -∞
  42. Si dy ≠ 0, entonces
  43. tYe ← ( ye - P.v[i].y ) / dy
  44. Si no, entonces
  45. tYe ← -∞
  46. Si tXe < tYe, entonces
  47. t2e ← tYe
  48. Si no, entonces
  49. t2e ← tXe
  50. Si t1s < t2e, entonces // El segmento no es visible
  51. Si 0 < t1s ≤ 1, entonces // Agregamos un vértice de giro
  52. Si tXe < tYe, entonces
  53. Resultado.Agregar( xs, ye )
  54. Si no, entonces
  55. Resultado.Agregar( xe, ys )
  56. Si no, entonces
  57. Si 0 < t1s y t2e ≤ 1, entonces
  58. Si 0 < t2e, entonces // Agregamos una intersección
  59. Si tXe > tYe, entonces
  60. Resultado.Agregar( xe, P.v[i].y + tXe * dy )
  61. Si no, entonces
  62. Resultado.Agregar( P.v[i].x + tYe * dx, ye )
  63. Si no, entonces // Agregamos el vértice inicial
  64. Resultado.Agregar( P.v[i].x, P.v[i].y )
  65. Si t1s < 1, entonces // Agregamos una intersección
  66. Si tXs < tYs, entonces
  67. Resultado.Agregar( xs, P.v[i].y + tXs * dy )
  68. Si no, entonces
  69. Resultado.Agregar( P.v[i].x + tYs * dx, ys )
  70. Si no, entonces // Agregamos el vértice final
  71. Resultado.Agregar( P.v[i+1].x, P.v[i+1].y )
  72. Si 0 < t2s ≤ 1, entonces // Agregamos un vértice de giro
  73. Resultado.Agregar( xs, ys )
  74. Terminar( Resultado )

Agregar() se refiere a la operación básica para agregar un punto al final de la lista de vértices de un polígono.

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

[IMAGEN]: Figura 61 - Ejemplo del Algoritmo de Weiler-Atherton
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 : { (-1,3), (3,3), (3,-3), (-1,-3) }

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 : { (-2,1), (1,4), (4,3), (3,0), (0,-4), (-2,-4), (-3,-1) }

Solución

[IMAGEN]: Figura 62 - Calculamos todas las intersecciones
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 : { (-2,1), (-1,2), (0,3), (1,4), (4,3), (3,0), (3,0), (0,75, 3), (0,-4), (-2,-4), (-3,-1) }
R : { (-1,3), (0,3), (3,3), (3,0), (3,-3), (0,75, 3), (-1,-3), (-1,2) }

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 : { (-1,2), (0,3) }
[IMAGEN]: Figura 64 - Seguimos con el recorrido de R
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 : { (-1,2), (0,3), (3,3), (3,0) }
[IMAGEN]: Figura 65 - Seguimos con el recorrido de P
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 : { (-1,2), (0,3), (3,3), (3,0), (0,75, 3 ) }
[IMAGEN]: Figura 66 - Seguimos con el recorrido de R
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 : { (-1,2), (0,3), (3,3), (3,0), (0,75, 3 ), (-1,-3) }
[IMAGEN]: Figura 67 - Polígono recortado, Q
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 : { (-1,2), (0,3), (3,3), (3,0), (0,75, 3 ), (-1,-3) }

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 falso indicará 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 )
  1. Crear ListaPolígonos: Resultado ← vacía
  2. P.Agregar( P.v[1] ) // Agregamos el primer vértice al final
  3. R.Agregar( R.v[1] )
  4. ExistenIntersecciones ← Calcular_Intersecciones( P, R )
  5. Si ExistenIntersecciones = verdadero, entonces
  6. Resultado ← Intersectar( P, R, Resultado )
  7. Si no, entonces
  8. ContienePunto ← Acepta( P, R.v[1] )
  9. Si ContienePunto = verdadero, entonces
  10. Resultado ← R
  11. Si no, entonces
  12. ContienePunto ← Acepta( R, P.v[1] )
  13. Si ContienePunto = verdadero, entonces
  14. Resultado ← P
  15. Si no, entonces
  16. Resultado ← vacía
  17. 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 )
  1. ExistenIntersecciones ← falso
  2. A ← P.v1
  3. B ← Siguiente_Original( P, A )
  4. Mientras que, B ≠ P.v1
  5. C ← R.v1
  6. D ← Siguiente_Original( R, C )
  7. Mientras que, D ≠ R.v1, repetir
  8. tp ← Calcular_Parámetro( A, B, C, D )
  9. Si 0 ≤ tp ≤ 1, entonces
  10. tr ← Calcular_Parámetro( C, D, A, B )
  11. Si 0 ≤ tr ≤ 1, entonces
  12. ExistenIntersecciones ← verdadero
  13. nuevo.vértice ← A + tp*(B-A)
  14. nuevo.vértice.original ← falso
  15. nuevo.t ← tp
  16. nuevo.entrante ← Es_Entrante( A, B, C, D )
  17. Insertar( P, A, B, nuevo )
  18. nuevo.t ← tr
  19. Insertar( Q, C, D, nuevo )
  20. C ← D
  21. D ← Siguiente_Original( R, C )
  22. A ← B
  23. B ← Siguiente_Original( P, A )
  24. 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 )
  1. Resultado ← P.Siguiente( A )
  2. Mientras que, Resultado.original = falso, repetir
  3. Resultado ← P.Siguiente( Resultado )
  4. 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 )
  1. N ← ( Q0y - Q1y, Q1x - Q0x )
  2. numerador ← N⋅(P0 - Q0)
  3. denominador ← -N⋅(P1 - P0)
  4. Si denominador ≠ 0, entonces
  5. t ← numerador / denominador
  6. Si no, entonces
  7. t ← ∞
  8. 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 )
  1. N ← ( -Vy, Vx )
  2. denominador ← N⋅U
  3. Si denominador < 0, entonces
  4. Terminar( verdadero )
  5. Si no, entonces
  6. 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 )
  1. Actual ← A
  2. Sig ← P.Siguiente( A )
  3. terminar ← falso
  4. Mientras que, terminar = falso y Sig.original = falso, repetir
  5. Si nuevo.t < Sig.t, entonces
  6. P.Insertar_Nuevo( Actual, nuevo )
  7. terminar ← verdadero
  8. Si no, entonces
  9. Actual ← Sig
  10. Sig ← P.Siguiente( Actual )
  11. Resultado ← P.Siguiente( Resultado )
  12. P.Insertar_Nuevo( Actual, nuevo )
  13. 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 )
  1. Crear ListaPolígonos: Actual ← { P, R } // Actual[1] = P, Actual[2] = R
  2. Crear ListaPolígonos: Resultado ← vacía
  3. Crear Polígono: Auxiliar ← vacío
  4. índice ← Buscar_Punto_Entrante_No_Visitado( P )
  5. Mientras que, índice > 0, repetir
  6. n ← 1
  7. Mientras que, Actual[n].v[índice].visitado = falso, repetir
  8. Actual[n].v[índice].visitado = verdadero
  9. Auxiliar.Agregar( Actual[n].v[índice].vértice )
  10. Si Actual[n].v[índice].original = falso, entonces
  11. Si Actual[n].v[índice].entrante = falso, entonces // Cambio de polígono
  12. n_ant ← n
  13. Si n = 1, entonces
  14. n ← 2
  15. Si no, entonces
  16. n ← 1
  17. índice ← Buscar_Punto( Actual[n], Actual[n_ant].v[índice].vértice )
  18. índice ← índice + 1
  19. Si índice > Actual[n].Cantidad_Vértices(), entonces
  20. índice ← 1
  21. Resultado.AgregarPolígono( Auxiliar )
  22. Auxiliar.Vaciar()
  23. índice ← Buscar_Punto_Entrante_No_Visitado( P )
  24. 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 )
  1. Para: índice ← 1 hasta P.Cantidad_Vértices(), repetir
  2. Si P.v[índice].original = falso y Si P.v[índice].entrante = verdadero y Si P.v[índice].visitado = falso, entonces
  3. Terminar( índice )
  4. 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 )
  1. Para: índice ← 1 hasta P.Cantidad_Vértices(), repetir
  2. Si P.v[índice].vértice = I, entonces
  3. Terminar( índice )
  4. Terminar( 0 )

Observaciones

Para aquellas implementaciones del algoritmo de Sutherland-Hodgman para hardware, podemos descomponer este algoritmo en varias etapas. Cada etapa manipula un vértice para cada arista y así no tenemos que usar una lista de vértices intermediaria. Esta mejora se puede conseguir con un procesamiento paralelo o con un solo procesador configurado por etapas. Si un vértice es validado al terminar todas las etapas de recorte, entonces se agrega a la lista final de vértices. De lo contrario, el vértice no continúa en el procesamiento.

Una mejora del algoritmo de Weiler-Atherton es mantener una lista de puntos entrantes, en lugar de buscarlos en el polígono a recortar. Dejamos su implementación como un ejercicio. También podemos usar este algoritmo para conseguir la unión de dos polígonos. En lugar de tratar los puntos de intersección entrantes como el principio del polígono resultante y los salientes para alternar entre polígonos, invertimos esta lógica. Tratamos los puntos de intersección entrantes para alternar entre polígonos y los salientes como el principio del polígono resultante. También dejamos esta implementación como un ejercicio.

Concluyendo, el algoritmo de Nicholl-Lee-Nicholl es actualmente el mejor de los algoritmos de recorte de segmentos que hemos tratado. Los algoritmos de Liang-Barsky y Cohen-Sutherland siguen siendo populares, y en este último caso, el algoritmo es muy fácil de implementar. Estos tres algoritmos se basan en un rectángulo vertical de recorte. El algoritmo de Cyrus-Beck se basa en un polígono convexo de recorte, pero requiere varios cálculos costosos en comparación con los algoritmos anteriores. Para los algoritmos de recorte de polígonos, los algoritmos presentados son fáciles de entender y de describir, pero no son recomendados porque requieren varios cálculos, y además existen otros algoritmos de mejor rendimiento.

Volviendo a nuestro esquema de las etapas del procesamiento de datos geométricos a colores asignados a cada píxel de la pantalla o puntos de impresión en papel, agregamos el proceso de recorte como una nueva etapa. Nuestro esquema es ahora el siguiente:

[IMAGEN]: Figura 68 - Procesamiento Geométrico
Figura 68 - Procesamiento Geométrico

Ejercicios

Enlace al paquete de este capítulo.

  1. Como mencionamos en la explicación del algoritmo de Cohen-Sutherland, podemos mejorarlo un poco para que no recalcule la pendiente de la intersección en cada iteración.

    1. Implemente el algoritmo original,

    2. Implemente otra versión del algoritmo con la mejora mencionada, y

    3. Escriba un programa para comparar el rendimiento de ambos algoritmos. Para el programa, cree aleatoriamente varios segmentos - decenas de millares - para pasarlos por los dos algoritmos de a) y b) para ser recortados. Cronometre los procesamientos de ambos algoritmos y muestre los resultados de la comparativa.

  2. Optimice el algoritmo de Nicholl-Lee-Nicholl para reusar multiplicaciones y restas y así no hay que invocar a Izquierda(), ni a Derecha(), ni tampoco a Intersección_Vertical() ni a Intersección_Horizontal(). Por ejemplo, en el algoritmo de Recortar_Interior(), podemos sustituir el comienzo con los siguientes pasos, para no tener que usar Izquierda():

    1. QPX ← Q.x - P.x
    2. QPY ← Q.y - P.y
    3. A ← R.xizq - P.x
    4. B ← R.ysup - P.y
    5. Si A*QPX + B*QPY > 0, entonces
  3. Implemente las mejoras mencionadas anteriormente para el algoritmo Weiler-Atherton. Cree otra lista de puntos, o referencias a los puntos, para guardar las intersecciones entrantes, que previamente hemos calculado. Esta lista contendrá menos puntos que la lista de los vértices originales y puntos de intersección. Ahora, sólo tendremos que consultar esta lista, en lugar de buscar las intersecciones entre todos los puntos, para conseguir aquellas intersecciones entrantes aún sin visitar.

  4. Como mencionamos anteriormente, podemos usar el algoritmo de Weiler-Atherton para el modelado. Con las operaciones básicas de conjuntos - unión, intersección, y diferencia - podemos construir nuevas figuras geométricas a partir de dos figuras básicas, como mínimo.

    [IMAGEN]: Ejercicio 4 - Polígonos A y B
    Ejercicio 4 - Polígonos A y B
    • A ∪ B. Para la unión, buscamos cualesquier intersecciones entre los dos polígonos A y B. Comenzamos con el recorrido de A, el polígono a recortar, o de B, el polígono de recorte. Cambiamos de polígono al encontrarnos con intersecciones.

      [IMAGEN]: Ejercicio 4 - Unión de A y B
      Ejercicio 4 - Unión de A y B
    • A ∩ B. La intersección es justamente el algoritmo original de recorte de Weiler-Atherton. Recorremos el polígono A al encontrarnos con las intersecciones entrantes y recorremos el polígono B al encontrarnos con las intersecciones salientes.

      [IMAGEN]: Ejercicio 4 - Intersección de A y B
      Ejercicio 4 - Intersección de A y B
    • A − B. Para la diferencia, comenzamos con el polígono A y eliminamos partes de ello con el polígono B. Usando el algoritmo de Weiler-Atherton, recorremos el polígono A al encontrarnos con las intersecciones salientes y recorremos el polígono B al encontrarnos con las intersecciones entrantes.

      [IMAGEN]: Ejercicio 4 - Diferencia de A y B
      Ejercicio 4 - Diferencia de A y B

    Cree un programa que permita al usuario generar polígonos con estas operaciones.