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:

\

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:

\

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:

\

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:

\

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:

\

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:

\

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:

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

\

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:

\

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:

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

\

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:

\

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:

\

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:

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

\

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:

\

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:

\

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:

\

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:

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

\

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 )