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

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

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 : \
[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 : \

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

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

Q : \

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

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

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 : \
[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 : \
[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 : \
[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:

\

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.