Liang-Barsky

From Wikipedia, the free encyclopedia

In computer graphics, the Liang-Barsky algorithm is a line clipping algorithm. The Liang-Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping box to determine the intersections between the line and the clipping box. With these intersections it knows which portion of the line should be drawn. This algorithm is significantly more efficient than Cohen-Sutherland.

[edit] The algorithm

C# implementation for Liang-Barsky algorithm

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

[edit] See also

Algorithms used for the same purpose: