Liang–Barsky algorithm

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.

The algorithm

Below is a 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";
    }
}

Java code:

/*

* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package lineclip; /**

*
* @author Alamgir
*/

public class Algorithm {

   /**
    * @param args the command line arguments
    */
   private int x1, x2, y1, y2;
   public void liang_barsky(int x1, int y1, int x2, int y2, int xmin, int ymin, int xmax, int ymax)
   {
       double deltaX, deltaY, p, q;
       double u1 = 0.0, u2 = 1.0;
       double r;

       deltaX = (x2 - x1);
       deltaY = (y2 - y1);

       /*
        * left edge, right edge, bottom edge and top edge checking
        */
       double pPart[] = {-1 * deltaX, deltaX, -1 * deltaY, deltaY};
       double qPart[] = {x1 - xmin, xmax - x1, y1 - ymin, ymax - y1};

       boolean accept = true;

       for( int i = 0; i < 4; i ++ )
       {
           p = pPart[ i ];
           q = qPart[ i ];

           if( p == 0 && q < 0 )
           {
               accept = false;
               break;
           }

           r = q / p;

           if( p < 0 )
           {
               u1 =Math.max(u1, r);
           }

           if( p > 0 )
           {
               u2 = Math.min(u2, r);
           }

           if( u1 > u2 )
           {
               accept = false;
               break;
           }
           //System.out.println(u1 +" " + u2);

       }
       if(accept)
       {
           if( u2 < 1 )
           {
               x2 = (int)(x1 + u2 * deltaX);
               y2 = (int)(y1 + u2 * deltaY);
           }
           if( u1 > 0)
           {
               x1 = (int)(x1 + u1 * deltaX);
               y1 = (int)(y1 + u1 * deltaY);
           }
           
           set(x1, y1, x2, y2);
       }
       else
       {
           set(-1, -1, -1, -1);
       }             
   }
   public void set( int x1, int y1, int x2, int y2 )
   {
       this.x1 = x1;
       this.y1 = y1;
       this.x2 = x2;
       this.y2 = y2;
       return;
   }
   public int getx1()
   {
       return x1;
   }
   public int getx2()
   {
       return x2;
   }
   public int gety1()
   {
       return y1;
   }
   public int gety2()
   {
       return y2;
   }

}

Liang–Barsky algorithm

The algorithm

See also