This algorithm divides a 2D space into 9 parts, of which only the middle part (viewport) is visible. The algorithm includes, excludes or partially includes the line based on where the two endpoints are:

  • Both endpoints are in the viewport (bitwise OR of endpoints == 0): trivial accept.
  • Both endpoints are in the same part, which is not visible (bitwise AND of endpoints != 0): trivial reject.
  • Both endpoints are in different parts: In case of this non trivial situation the algorithm finds one of the two points that are outside the viewport (there is at least one point outside).

The intersection of the outpoint and extended viewport border is then calculated (i.e. with the parametric equation for the line) and this new point replaces the outpoint. The algorithm repeats until a trivial accept or reject occurs.

The numbers in the figure below are called outcodes. An outcode is computed for each of the two points in the line. The first bit is set to 1 if the point is above the viewport. The bits in the outcode represent: Top, Bottom, Right, Left. For example the outcode 1010 represents a point that is top-right of the viewport.

1001  |  1000  |  1010
-----------------------
      |        |
0001  |  0000  |  0010
      |        |
------------------------
      |        |
0101  |  0100  |  0110

#include <iostream.h>
#include <conio.h>
#include <graphics.h>

#define TOP 8
#define BOTTOM 4
#define LEFT 2
#define RIGHT 1

struct point
{
  float x;
  float y;
};

struct box
{
  int xx, yx, yn, xn;
};


int ncode(box b, point p)
{
  int code=0;
  if (p.x<b.xn)
    code+=LEFT;
  if (p.x>b.xx)
    code+=RIGHT;
  if (p.y<b.yn)
    code+=BOTTOM;
  if (p.y>b.yx)
    code+=TOP;
  return code;
}

void clipline(box b,point p1, point p2)
{
  int c1,c2;
  c1=ncode(b,p1);
  c2=ncode(b,p2);
  getch();
  float m;
  m=(p2.y-p1.y)/(p2.x-p1.x);
  if (!(c1 & c2))
  {
      if (c1 & TOP && c1 | c2)
      {
        p1.x=p1.x+1/m*(b.yx-p1.y);
        p1.y=b.yx;
        c1=ncode(b,p1);
      }
      if (c1 & BOTTOM && c1 | c2)
      {
        p1.x=p1.x+1/m*(b.yn-p1.y), p1.y=b.yn;
        c1=ncode(b,p1);
      }
      if (c1 & LEFT&& c1 | c2)
      {
        p1.y=p1.y+m*(b.xn-p1.x), p1.x=b.xn;
        c1=ncode(b,p1);
      }
      if (c1 & RIGHT&& c1 | c2)
      {
        p1.y=p1.y+m*(b.xx-p1.x), p1.x=b.xx;
        c1=ncode(b,p1);
      }
      if (c2 & TOP&& c1 | c2)
      {
        p2.x=p2.x+1/m*(b.yx-p2.y), p2.y=b.yx ;
        c2=ncode(b,p2);
      }
      if (c2 & BOTTOM&& c1 | c2)
      {
        p2.x=p2.x+1/m*(b.yn-p2.y), p2.y=b.yn; 
                c2=ncode(b,p2);
      }
      if (c2 & LEFT&& c1 | c2)
      {
        p2.y=p2.y+m*(b.xn-p2.x), p2.x=b.xn ;
                c2=ncode(b,p2);
      }

      if (c2 & RIGHT&& c1 | c2)
      {
        p2.y=p2.y+m*(b.xx-p2.x), p2.x=b.xx ;
        c2=ncode(b,p2);
      }

    line(p1.x+getmaxx()/2,getmaxy()/2-p1.y,p2.x+getmaxx()/2,getmaxy()/2-p2.y);
  }
}

void main()
{
  point p1,p2;
  box b;
  int gdriver = DETECT, gmode = VGAHI;
  initgraph(&gdriver, &gmode, "");
  int x1,y1,x2,y2,xx,xn,yx,yn;
  b.xx=getmaxx()/4;
  b.xn=-getmaxx()/4;
  b.yn=-getmaxy()/4;
  b.yx=getmaxy()/4;
  rectangle (getmaxx()/2+b.xn,getmaxy()/2-b.yn,b.xx+getmaxx()/2,getmaxy()/2-b.yx);
  cout<<"Enter the line's co-ordinates ";
  cin>>p2.x>>p2.y>>p1.x>>p1.y;
  clipline(b,p1,p2);
  getch();
}