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.