Liang-Barsky Line Clipping Algorithm with C/C++

Theory
In Liang-Barsky algorithm, we first write the point-clipping conditions in parametric form as 

Each of these for inequalities can be expressed as , k = 1, 2, 3, …..
where parameter p and q are defined as

Any line that is parallel to one of the clipping boundaries has pk = 0 for the value of k corresponding to that boundary. If, for that value of k, we also find qk < 0, then the line is completely outside the boundary and can be eliminated from further consideration. If qk >=0, the line is inside the parallel clipping boundary.

When pk <0, the infinite extension of the line proceeds from the outside to the inside of the inside of the infinite extension of this particular boundary. If pk > 0, the line proceeds from the insides to the outside. For a nonzero value of pk, we can calculate the value of u that corresponds to the point where the infinitely extended line intersects the extension of boundary k as u = qk / pk.

For each line, we calculate values of parameters u1 and u2 that define that part of the line that lies within the clip rectangle. The value of u1 is determined by looking at the rectangle edges for which the line proceeds from the outside to inside (p < 0). For these edges, we calculate rk = qk / pk. The value of u1 is taken as the largest of the set consisting of 0 and the various values of r. Conversely, the value of u2 is determined by examining the boundaries for which the line proceeds from inside to outside (p > 0). A value of rk is calculated for each of these boundaries, and the value of u2 is minimum of the set consisting of 1 and the calculated r values. If u1 > u2, the line is completely outside the clip window and it can be rejected. Otherwise, the endpoints of the clipped line are calculated from the two values of parameter u.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205

<div align="justify"> <b>Source Code</b></div> #include <windows.h> #include <cmath> #define ROUND(a) ((int) (a + 0.5))   static HWND sHwnd; static COLORREF redColor=RGB(255,0,0); static COLORREF blueColor=RGB(0,0,255); static COLORREF greenColor=RGB(0,255,0);   typedef struct Point {     int x;     int y; }pt;   pt winMin = {100, 100}; pt winMax = {800, 400}; pt p1 = {50, 200}; pt p2 = {900, 300};   void SetWindowHandle(HWND hwnd){     sHwnd=hwnd; }   /* SetPixel */ void setPixel(int x,int y,COLORREF& color=redColor){     if(sHwnd==NULL){         MessageBox(NULL,"sHwnd was not initialized !","Error",MB_OK|MB_ICONERROR);         exit(0);     }     HDC hdc=GetDC(sHwnd);     SetPixel(hdc,x,y,color);     ReleaseDC(sHwnd,hdc);     return;   }   void LineBresenham (int xa, int ya, int xb, int yb){     int dx = (xb - xa), dy = (yb - ya);     int x, y, xEnd, yEnd;     int p = 2 * abs(dy) - abs(dx);     int twoDy = 2 * abs(dy), twoDyDx = 2 * (abs(dy) - abs(dx));     int tFactor = dx*dy;     if(xa > xb){         x = xb;         y = yb;         xEnd = xa;     }else{         x = xa;         y = ya;         xEnd = xb;     }     setPixel(x, y);     while(x < xEnd){         x++;         if(p < 0)             p += twoDy;         else{             if(tFactor > 0) //for positive slope                 y++;             else //for negative slope                 y--;             p += twoDyDx;         }         setPixel(x, y);     } }   void drawBoundary(pt winMin, pt winMax){     int x, y;     x = winMin.x;     for(y = winMin.y; y < winMax.y; y++){         setPixel(x,y, blueColor);     }     y = winMin.y;     for(x = winMin.x; x < winMax.x; x++){         setPixel(x,y, blueColor);     }     x = winMax.x;     for(y = winMin.y; y < winMax.y; y++){         setPixel(x,y, blueColor);     }     y = winMax.y;     for(x = winMin.x; x < winMax.x; x++){         setPixel(x,y, blueColor);     }   }   int clipTest(float p, float q, float *u1, float *u2){     float r;     int retVal = TRUE;       if(p < 0.0){         r = q / p;         if(r > *u2)             retVal = FALSE;         else             if (r > *u1)                 *u1 = r;     }     else         if (p > 0.0){             r = q / p;             if (r < *u1)                 retVal = FALSE;             else if (r < *u2)                 *u2 = r;         }         else             if(q < 0.0)                 retVal = FALSE;           return (retVal); }   void clipLine(pt winMin, pt winMax, pt p1, pt p2){     float u1 = 0.0, u2 = 1.0, dx = p2.x - p1.x, dy;     if(clipTest(-dx, p1.x - winMin.x, &u1, &u2))         if(clipTest(dx, winMax.x - p1.x, &u1, &u2)){             dy = p2.y - p1.y;             if(clipTest(-dy, p1.y - winMin.y, &u1, &u2))                 if(clipTest(dy, winMax.y - p1.y, &u1, &u2)){                     if(u2 < 1.0){                         p2.x = p1.x + u2 * dx;                         p2.y = p1.y + u2 * dy;                     }                     if(u1 > 0.0){                         p1.x += u1 * dx;                         p1.y += u1 * dy;                     }                     LineBresenham(ROUND(p1.x), ROUND(p1.y), ROUND(p2.x), ROUND(p2.y));                 }         } } /* Window Procedure WndProc */ LRESULT CALLBACK WndProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam){       switch(message){         case WM_PAINT:             SetWindowHandle(hwnd);             drawBoundary(winMin, winMax);             clipLine(winMin, winMax, p1, p2 );             break;         case WM_CLOSE: // FAIL THROUGH to call DefWindowProc             break;         case WM_DESTROY:             PostQuitMessage(0);             return 0;         default:         break; // FAIL to call DefWindowProc //     }     return DefWindowProc(hwnd,message,wParam,lParam); }   int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,LPSTR lpCmdLine,int iCmdShow){     static TCHAR szAppName[] = TEXT("Line Clipping");     WNDCLASS wndclass;     wndclass.style         = CS_HREDRAW|CS_VREDRAW ;     wndclass.lpfnWndProc   = WndProc ;     wndclass.cbClsExtra    = 0 ;     wndclass.cbWndExtra    = 0 ;     wndclass.hInstance     = hInstance ;     wndclass.hIcon         = LoadIcon (NULL, IDI_APPLICATION) ;     wndclass.hCursor       = LoadCursor (NULL, IDC_ARROW) ;     wndclass.hbrBackground = (HBRUSH) GetStockObject (WHITE_BRUSH) ;     wndclass.lpszMenuName  = NULL ;     wndclass.lpszClassName = szAppName ;       // Register the window //     if(!RegisterClass(&wndclass)){         MessageBox(NULL,"Registering the class failled","Error",MB_OK|MB_ICONERROR);         exit(0);     }       // CreateWindow //     HWND hwnd=CreateWindow(szAppName,"Liang-Barsky Algorithm - Programming Techniques",                 WS_OVERLAPPEDWINDOW,                  CW_USEDEFAULT,                  CW_USEDEFAULT,                  CW_USEDEFAULT,                  CW_USEDEFAULT,                  NULL,                  NULL,                  hInstance,                  NULL);     if(!hwnd){         MessageBox(NULL,"Window Creation Failed!","Error",MB_OK);         exit(0);     }     // ShowWindow and UpdateWindow //     ShowWindow(hwnd,iCmdShow);     UpdateWindow(hwnd);       // Message Loop //     MSG msg;     while(GetMessage(&msg,NULL,0,0)){         TranslateMessage(&msg);         DispatchMessage(&msg);     }     /* return no error to the operating system */     return 0; }

Output