Geometría

Algoritmos geométricos

El algoritmo de Liang-Barsky es un algoritmo de recorte de líneas similar al algoritmo de Cohen-Sutherland. Usa la ecuación paramétrica de la línea y desigualdades describiendo el rango del área de recorte para determinar las intersecciones entre la línea y el área de recorte. Fue desarrollado por You-Dong Liang y Brian A. Barsky.

Basandonos en las siguientes ecuaciones:

x=x1 + uΔx
y=y1 + uΔy
0<=u<=1

Donde Δx= x₂-x₁ y Δy= y₂-y₁

Con estas intersecciones se sabe qué porción de la línea debería ser dibujada. Este algoritmo es significativamente más eficiente que el de Cohen-Sutherland.

internal sealed class LiangBarskyClipping : IClippingAlgorithm {
    private Vector2 _clipMin, _clipMax;
 
    public IEnumerable<Vector2> GetBoundingPolygon() {
        yield return _clipMin;
        yield return new Vector2(_clipMax.X, _clipMin.Y);
        yield return _clipMax;
        yield return new Vector2(_clipMin.X, _clipMax.Y);
    }
 
    public void SetBoundingRectangle(Vector2 start, Vector2 end) {
        _clipMin = start;
        _clipMax = end;
    }
 
    public void SetBoundingPolygon(IEnumerable<Vector2> points) {
        throw new NotSupportedException("see Capabilities =)");
    }
 
    private delegate bool ClippingHandler(float p, float q);
 
    public bool ClipLine(ref Line line) {
        Vector2 P = line.End - line.Start;
        float tMinimum = 0, tMaximum = 1;
 
        ClippingHandler pqClip = delegate(float directedProjection,
                                          float directedDistance) {
            if (directedProjection == 0) {
                if (directedDistance < 0) return false;
            }
            else {
                float amount = directedDistance / directedProjection;
                if (directedProjection < 0) {
                    if (amount > tMaximum) return false;
                    else if (amount > tMinimum) tMinimum = amount;
                }
                else {
                    if (amount < tMinimum) return false;
                    else if (amount < tMaximum) tMaximum = amount;
                }
            }
            return true;
        };
 
        if (pqClip(-P.X, line.Start.X - _clipMin.X)) {
            if (pqClip(P.X, _clipMax.X - line.Start.X)) {
                if (pqClip(-P.Y, line.Start.Y - _clipMin.Y)) {
                    if (pqClip(P.Y, _clipMax.Y - line.Start.Y)) {
                        if (tMaximum < 1) {
                            line.End.X = line.Start.X + tMaximum * P.X;
                            line.End.Y = line.Start.Y + tMaximum * P.Y;
                        }
                        if (tMinimum > 0) {
                            line.Start.X += tMinimum * P.X;
                            line.Start.Y += tMinimum * P.Y;
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }
 
    public ClippingCapabilities Capabilities {
        get {
                return ClippingCapabilities.RectangleWindow;
        }
    }
 
    public override string ToString() {
        return "Liang-Barsky algorithm";
    }
}
// This code was implemented by Grishul Eugeny as part of preparation
// to exam in ITMO university

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


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


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].



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].



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].



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 tpor ahora sigue siendo [0,25, 1].



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

dx ← Q.x - P.x
dy ← Q.y - P.y
resultado ← falso
Si dx = 0,  y  Si dy = 0,  y  Si Recortar_Punto( P, R ) = verdadero, entonces


Q ← P
resultado ← verdadero

Si no, entonces


te ← 0
ts ← 1
Si Calcular_Parámetros( R.xizq-P.x, dx, te, ts ) = verdadero, entonces


Si Calcular_Parámetros( P.x-R.xder, -dx, te, ts ) = verdadero, entonces


Si Calcular_Parámetros( R.yinf-P.y, dy, te, ts ) = verdadero, entonces


Si Calcular_Parámetros( P.y-R.ysup, -dy, te, ts ) = verdadero, entonces


resultado ← verdadero
Si ts < 1, entonces


Q.x ← P.x + ts dx
Q.y ← P.y + ts dy

Si te > 0, entonces


P.x ← P.x + te dx
P.y ← P.y + te dy






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 )

Si denominador > 0, entonces


t ← numerador / denominador
Si t > ts


Terminar( falso )

Si no, compruebe que t > te


te ← t


Si no, compruebe que denominador < 0,


t ← numerador / denominador
Si t < te


Terminar( falso )

Si no, compruebe que t < ts


ts ← t


Si no, compruebe que numerador > 0,


Terminar( falso )

Terminar( verdadero )