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 \ 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 )