Algoritmo de Liang-Barsky

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.

Basándonos 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.

Implementación en C# del algoritmo de Liang-Barsky

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

Adaptación a recorte de polígonos

Se amplía con un planteamiento similar el del método Sutherland-Hodgman. Las representaciones paramétricas de líneas se utilizan para procesar las aristas de los polígonos en orden alrededor del perímetro del polígono utilizando procedimientos de prueba similares a aquellos que se emplean en el recorte de líneas.

Véase también

• Cohen-Sutherland, algoritmo para recorte de líneas.
• Cyrus-Beck, algoritmo para recorte de líneas.
• Fast-Clipping, algoritmo para recorte de líneas.
• Nicholl-Lee-Nicholl, algoritmo para recorte de líneas.
• Sutherland-Hodgman, algoritmo para recorte de líneas y polígonos.
• Weiler-Atherton, algoritmo para recorte de líneas y polígonos.
• Recorte de Polígonos, algoritmos de recorte de polígonos.

• Datos: Q606795