Part 9: Clipping and Polygon various Technique algorithm

Part 9: Clipping and Polygon various Technique algorithm


When we have to display a large portion of the picture, then not only scaling & translation is necessary, the visible part of picture is also identified. This process is not easy. Certain parts of the image are inside, while others are partially inside. The lines or elements which are partially visible will be omitted. For deciding the visible and invisible portion, a particular process called clipping is used. Clipping determines each element into the visible and invisible portion. Visible portion is selected. An invisible portion is discarded.

Types of Lines:

Lines are of three types:

  1. Visible: A line or lines entirely inside the window is considered visible
  2. Invisible: A line entirely outside the window is considered invisible
  3. Clipped: A line partially inside the window and partially outside is clipped. For clipping point of intersection of a line with the window is determined.


Clipping can be applied through hardware as well as software. In some computers, hardware devices automatically do work of clipping. In a system where hardware clipping is not available software clipping applied.

Following figure show before and after clipping


The window against which object is clipped called a clip window. It can be curved or rectangle in shape.

Applications of clipping:

  1. It will extract part we desire.
  2. For identifying the visible and invisible area in the 3D object.
  3. For creating objects using solid modeling.
  4. For drawing operations.
  5. Operations related to the pointing of an object.
  6. For deleting, copying, moving part of an object.

Clipping can be applied to world co-ordinates. The contents inside the window will be mapped to device co-ordinates. Another alternative is a complete world co-ordinates picture is assigned to device co-ordinates, and then clipping of viewport boundaries is done.

Types of Clipping:

  1. Point Clipping
  2. Line Clipping
  3. Area Clipping (Polygon)
  4. Curve Clipping
  5. Text Clipping
  6. Exterior Clipping

Point Clipping:

Point Clipping is used to determining, whether the point is inside the window or not. For this following conditions are checked.

  1. x ≤ xmax
  2. x ≥ xmin
  3. y ≤ ymax
  4. y ≥ ymin

Point Clipping

The (x, y) is coordinate of the point. If anyone from the above inequalities is false, then the point will fall outside the window and will not be considered to be visible.


To implement Point Clipping:

  1. #include<stdio.h>
  2. #include<conio.h>
  3. #include<graphics.h>
  4. inttlx,tly,brx,bry,px,py;
  5. void point_clip()
  6. {
  7. intwxmin,wymin,wxmax,wymax;
  8. wxmin=tlx;
  9. wxmax=brx;
  10. wymin=tly;
  11. wymax=bry;
  12. if(px>=wxmin&&px<=wxmax)
  13. if(py>=wymin&&py<=wymax)
  14. putpixel(px,py,RED);
  15. getch();
  16. closegraph();
  17. }
  18. void main()
  19. {
  20. intgd=DETECT,gm,xc,yc,r;
  21. clrscr();
  22. printf(“Enter the top left coordinate”);
  23. scanf(“%d%d”,&tlx,&tly);
  24. printf(“Enter the bottom right coordinate”);
  25. scanf(“%d%d”,&brx,&bry);
  26. printf(“\n Enter the point”);
  27. scanf(“%d%d”,&px,&py);
  28. initgraph(&gd,&gm,“c:\\tc\\bgi”);
  29. setbkcolor(BLUE);
  30. setcolor(RED);
  31. rectangle(tlx,tly,brx,bry);
  32. point_clip();
  33. }


Point Clipping
Point Clipping

Line Clipping:

It is performed by using the line clipping algorithm. The line clipping algorithms are:

  1. Cohen Sutherland Line Clipping Algorithm
  2. Midpoint Subdivision Line Clipping Algorithm
  3. Liang-Barsky Line Clipping Algorithm

Cohen Sutherland Line Clipping Algorithm:

In the algorithm, first of all, it is detected whether line lies inside the screen or it is outside the screen. All lines come under any one of the following categories:

  1. Visible
  2. Not Visible
  3. Clipping Case

1. Visible: If a line lies within the window, i.e., both endpoints of the line lies within the window. A line is visible and will be displayed as it is.

2. Not Visible: If a line lies outside the window it will be invisible and rejected. Such lines will not display. If any one of the following inequalities is satisfied, then the line is considered invisible. Let A (x1,y2) and B (x2,y2) are endpoints of line.
3. Clipping Case: If the line is neither visible case nor invisible case. It is considered to be clipped case. First of all, the category of a line is found based on nine regions given below. All nine regions are assigned codes. Each code is of 4 bits. If both endpoints of the line have end bits zero, then the line is considered to be visible.

Line Clipping

The center area is having the code, 0000, i.e., region 5 is considered a rectangle window.

Following figure show lines of various types

Line Clipping

Line AB is the visible case
Line OP is an invisible case
Line PQ is an invisible line
Line IJ are clipping candidates
Line MN are clipping candidate
Line CD are clipping candidate

Advantage of Cohen Sutherland Line Clipping:

  1. It calculates end-points very quickly and rejects and accepts lines quickly.
  2. It can clip pictures much large than screen size.

Algorithm of Cohen Sutherland Line Clipping:

Step1:Calculate positions of both endpoints of the line

Step2:Perform OR operation on both of these end-points

Step3:If the OR operation gives 0000
line is considered to be visible
Perform AND operation on both endpoints
If And ≠ 0000
then the line is invisible
Line is considered the clipped case.

Step4:If a line is clipped case, find an intersection with boundaries of the window
m=(y2-y1 )(x2-x1)

(a) If bit 1 is “1” line intersects with left boundary of rectangle window
where X = Xwmin
where Xwminis the minimum value of X co-ordinate of window

(b) If bit 2 is “1” line intersect with right boundary
where X = Xwmax
where X more is maximum value of X co-ordinate of the window

(c) If bit 3 is “1” line intersects with bottom boundary
where y = ywmin
ywmin is the minimum value of Y co-ordinate of the window

(d) If bit 4 is “1” line intersects with the top boundary
where y = ywmax
ywmax is the maximum value of Y co-ordinate of the window

Example of Cohen-Sutherland Line Clipping Algorithm:

Let R be the rectangular window whose lower left-hand corner is at L (-3, 1) and upper right-hand corner is at R (2, 6). Find the region codes for the endpoints in fig:

Line Clipping

The region code for point (x, y) is set according to the scheme
Bit 1 = sign (y-ymax)=sign (y-6)         Bit 3 = sign (x-xmax)= sign (x-2)
Bit 2 = sign (ymin-y)=sign(1-y)         Bit 4 = sign (xmin-x)=sign(-3-x)


Line Clipping


A (-4, 2)→ 0001         F (1, 2)→ 0000
B (-1, 7) → 1000         G (1, -2) →0100
C (-1, 5)→ 0000         H (3, 3) → 0100
D (3, 8) → 1010         I (-4, 7) → 1001
E (-2, 3) → 0000         J (-2, 10) → 1000

We place the line segments in their appropriate categories by testing the region codes found in the problem.

Category1 (visible): EF since the region code for both endpoints is 0000.

Category2 (not visible): IJ since (1001) AND (1000) =1000 (which is not 0000).

Category 3 (candidate for clipping): AB since (0001) AND (1000) = 0000, CD since (0000) AND (1010) =0000, and GH. since (0100) AND (0010) =0000.

The candidates for clipping are AB, CD, and GH.

In clipping AB, the code for A is 0001. To push the 1 to 0, we clip against the boundary line xmin=-3. The resulting

intersection point is I1 (-3,3Line Clipping). We clip (do not display) AI1 and I1 B. The code for I1is 1001. The clipping category for I1 B is 3 since (0000) AND (1000) is (0000). Now B is outside the window (i.e., its code is 1000), so we push the 1

to a 0 by clipping against the line ymax=6. The resulting intersection is l2 (-1Line Clipping,6). Thus I2 B is clipped. The code for I2 is 0000. The remaining segment I1 I2 is displayed since both endpoints lie in the window (i.e., their codes are 0000).

For clipping CD, we start with D since it is outside the window. Its code is 1010. We push the first 1 to a 0 by clipping against the line ymax=6. The resulting intersection I3 is (Line Clipping,6),and its code is 0000. Thus I3 D is clipped and the remaining segment CI3 has both endpoints coded 0000 and so it is displayed.

For clipping GH, we can start with either G or H since both are outside the window. The code for G is 0100, and we push the 1 to a 0 by clipping against the line ymin=1.The resulting intersection point is I4 (2Line Clipping,1) and its code is 0010. We clip GI4 and work on I4 H. Segment I4 H is not displaying since (0010) AND (0010) =0010.

Program to perform Line Clipping using Cohen Sutherland Algorithm:

  1. #include <iostream.h>
    #include <conio.h>
    #include <graphics.h>
    #include <dos.h>
    class data
        int gd, gmode, x, y, xmin,ymin,ymax,xmax;
        int a1,a2;
        float x1, y1,x2,y2,x3,y3;
        int xs, ys, xe, ye;
        float maxx,maxy;
            void getdata ();
            void find ();
            void clip ();
            void display (float, float,float,float);
            void checkonof (int);
            void showbit (int);
    void data :: getdata ()
        cout<<"Enter the minimum and maximum coordinate of window (x, y) ";
               cin >>xmin>>ymin>>xmax>>ymax;
               cout<<"Enter the end points of the line to be clipped";
               cin >>xs>>ys>>xe>>ye;
               display (xs, ys, xe,ye);
    void data :: display (float, xs, float, ys,float xe, float ye)
        int gd=DETECT;
        initgraph (&gd,&gmode, "");
        line (maxx/2,0,maxx/2,maxy);
        line (0, maxy/2,maxx,maxy/2);
        rectangle (maxx/2+xmin,maxy/2-ymax,maxx/2+xmax,maxy/2-ymin);
        line (maxx/2+xs,maxy/2-ys,maxx/2+xe,maxy/2-ye);
    void data :: find ()
        if ((ys-ymax)>0)
        if ((ymin-ys)>0)
        if ((xs-xmax)>0)
                if ((xmin-xs)>0)
         if ((ye-ymax)>0)
               if ((ymin-ye)>0)
              if ((xe-xmax)>0)
              if ((xmin-xe)>0)
             cout<<"\nThe area code of Ist point is ";
                     showbit (a1);
             getch ();
             cout <<"\nThe area code of 2nd point is ";
             showbit (a2);
             getch ();
    void data :: showbit (int n)
            int i,k, and;
            for (i=3;i>=0;i--)
                  and =1<<i;
           k = n?
           k ==0?cout<<"0": cout<<"1\"";
    void data ::clip()
             int j=a1&a2;
             if (j==0)
                  cout<<"\nLine is perfect candidate for clipping";
                  if (a1==0)
                 if (a2=0)
                     x3=xe; y3=ye;
                       checkonof (a2);
                       x3=x1; y3=y1;
                xs=x2; ys=y2;xe=x3;ye=y3;
                cout << endl;
                display (xs,ys,xe,ye);
                cout<<"Line after clipping";
                getch ()
           else if ((a1==0) && (a2=0))
                   cout <<"\n Line is in the visible region";
                   getch ();
    void data :: checkonof (int i)
          int j, k,l,m;
           if (1==1)
                 y1=ys+ ((x1-xs)/ (xe-xs))*(ye-ys);
       if (j>0)
        k=i & 4;
        if (k==1)
        m= i&2;
         if (m==1)
                y1=ys+ ((x1-xs)/ (xe-xs))*(ye-ys);
          main ()
                 data s;
                 closegraph ();
                 return ();



Line Clipping

Mid Point Subdivision Line Clipping Algorithm:

It is used for clipping line. The line is divided in two parts. Mid points of line is obtained by dividing it in two short segments. Again division is done, by finding midpoint. This process is continued until line of visible and invisible category is obtained. Let (xi,yi) are midpoint

Mid Point Subdivision Line Clipping Algorithm
Mid Point Subdivision Line Clipping Algorithm
Mid Point Subdivision Line Clipping Algorithm

x5lie on point of intersection of boundary of window.

Advantage of midpoint subdivision Line Clipping:

It is suitable for machines in which multiplication and division operation is not possible. Because it can be performed by introducing clipping divides in hardware.

Algorithm of midpoint subdivision Line Clipping:

Step1: Calculate the position of both endpoints of the line

Step2: Perform OR operation on both of these endpoints

Step3: If the OR operation gives 0000
Line is guaranteed to be visible
Perform AND operation on both endpoints.
If AND ≠ 0000
then the line is invisible
then the line is clipped case.

Step4: For the line to be clipped. Find midpoint
Xmis midpoint of X coordinate.
Ymis midpoint of Y coordinate.

Step5: Check each midpoint, whether it nearest to the boundary of a window or not.

Step6: If the line is totally visible or totally rejected not found then repeat step 1 to 5.

Step7: Stop algorithm.

Example: Window size is (-3, 1) to (2, 6). A line AB is given having co-ordinates of A (-4, 2) and B (-1, 7). Does this line visible. Find the visible portion of the line using midpoint subdivision?


Step1: Fix point A (-4, 2)

Mid Point Subdivision Line Clipping Algorithm
Mid Point Subdivision Line Clipping Algorithm

Step2: Find b”=mid of b’and b

Mid Point Subdivision Line Clipping Algorithm

So (-1, 5) is better than (2, 4)
Find b”&bb”(-1, 5) b (-1, 7)

Mid Point Subdivision Line Clipping Algorithm

So B””to B length of line will be clipped from upper side

Now considered left-hand side portion.

A and B””are now endpoints

Find mid of A and B””

A (-4, 2) B “”(-1, 6)

Mid Point Subdivision Line Clipping Algorithm Mid Point Subdivision Line Clipping Algorithm

Liang-Barsky Line Clipping Algorithm:

Liang and Barsky have established an algorithm that uses floating-point arithmetic but finds the appropriate endpoints with at most four computations. This algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the viewport.

Mid Point Subdivision Line Clipping Algorithm

Let P(x1, y1), Q(x2, y2) is the line which we want to study. The parametric equation of the line segment from gives x-values and y-values for every point in terms of a parameter that ranges from 0 to 1. The equations are

x=x1+(x2-x1 )*t=x1+dx*t and y=y1+(y2-y1 )*t=y1+dy*t

We can see that when t = 0, the point computed is P(x1, y1); and when t = 1, the point computed is Q(x2, y2).



Algorithm of Liang-Barsky Line Clipping:

1. Set tmin=0 and tmax=1

2. Calculate the values tL,tR,tT and tB(tvalues).
If t<tmin or t<tmax? ignore it and go to the next edge
Otherwise classify the tvalue as entering or exiting value (using inner product to classify)
If t is entering value set tmin=t if t is exiting value set tmax=t.</t</t

3. If tmin< tmax? then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax?, y1 + dy*tmax? )

4. If the line crosses over the window, you will see (x1 + dx*tmin, y1 + dy*tmin) and (x1 + dx*tmax? , y1 + dy*tmax?) are intersection between line and edge.

Text Clipping:

Several methods are available for clipping of text. Clipping method is dependent on the method of generation used for characters. A simple method is completely considered, or nothing considers method. This method is also called as all or none. If all characters of the string are inside window, then we will keep the string, if a string character is outside then whole string will be discarded in fig (a). Another method is discarded those characters not completely inside the window. If a character overlap boundary of window. Those will be discarded in fig (b).In fig (c) individual character is treated. Character lies on boundary is discarded as which it is outside the window.

Text Clipping

Curve Clipping:

Curve Clipping involves complex procedures as compared to line clipping. Curve clipping requires more processing than for object with linear boundaries. Consider window which is rectangular in shape. The circle is to consider against rectangle window. If circle is completely inside boundary of the window, it is considered visible. So save the circle. If a circle is in outside window, discard it. If circle cut the boundary then consider it to be clipping case.

Exterior Clipping:

It is opposite to previous clipping. Here picture which is outside the window is considered. The picture inside the rectangle window is discarded. So part of the picture outside the window is saved.

Uses of Exterior Clipping:

  1. It is used for displaying properly the pictures which overlap each other.
  2. It is used in the concept of overlapping windows.
  3. It is used for designing various patterns of pictures.
  4. It is used for advertising purposes.
  5. It is suitable for publishing.
  6. For designing and displaying of the number of maps and charts, it is also used.

Polygon Clipping:

Polygon clipping is applied to the polygons. The term polygon is used to define objects having outline of solid. These objects should maintain property and shape of polygon after clipping.


Polygon is a representation of the surface. It is primitive which is closed in nature. It is formed using a collection of lines. It is also called as many-sided figure. The lines combined to form polygon are called sides or edges. The lines are obtained by combining two vertices.

Example of Polygon:

  1. Triangle
  2. Rectangle
  3. Hexagon
  4. Pentagon

Following figures shows some polygons.


Types of Polygons

  1. Concave
  2. Convex

A polygon is called convex of line joining any two interior points of the polygon lies inside the polygon. A non-convex polygon is said to be concave. A concave polygon has one interior angle greater than 180°. So that it can be clipped into similar polygons.


A polygon can be positive or negative oriented. If we visit vertices and vertices visit produces counterclockwise circuit, then orientation is said to be positive.


Sutherland-Hodgeman Polygon Clipping:

It is performed by processing the boundary of polygon against each window corner or edge. First of all entire polygon is clipped against one edge, then resulting polygon is considered, then the polygon is considered against the second edge, so on for all four edges.

Four possible situations while processing

  1. If the first vertex is an outside the window, the second vertex is inside the window. Then second vertex is added to the output list. The point of intersection of window boundary and polygon side (edge) is also added to the output line.
  2. If both vertexes are inside window boundary. Then only second vertex is added to the output list.
  3. If the first vertex is inside the window and second is an outside window. The edge which intersects with window is added to output list.
  4. If both vertices are the outside window, then nothing is added to output list.

Following figures shows original polygon and clipping of polygon against four windows.

Sutherland-Hodgeman Polygon Clipping

Disadvantage of Cohen Hodgmen Algorithm:

This method requires a considerable amount of memory. The first of all polygons are stored in original form. Then clipping against left edge done and output is stored. Then clipping against right edge done, then top edge. Finally, the bottom edge is clipped. Results of all these operations are stored in memory. So wastage of memory for storing intermediate polygons.

Sutherland-Hodgeman Polygon Clipping

Weiler-Atherton Polygon Clipping:

Let the clipping window be initially called clip polygon and the polygon to be clipped the subject polygon. We start with an arbitrary vertex of the subject polygon and trace around its border in the clockwise direction until an intersection with the clip polygon is encountered:

1. If the edge enters the clip polygon, record the intersection point and continue to trace the subject polygon.

Weiler-Atherton Polygon Clipping

2. If the edge leaves the clip polygon, record the intersection point and make a right turn to follow the clip polygon in the same manner (i.e., treat the clip polygon as subject polygon and the subject polygon as clip polygon and proceed as before).

Whenever our path of traversal forms a sub-polygon we output the sub-polygon as part of the overall result. We then continue to trace the rest of the original subject polygon from a recorded intersection point that marks the beginning of a not-yet traced edge or portion of an edge. The algorithm terminates when the entire border of the original subject polygon has been traced exactly once.

Weiler-Atherton Polygon Clipping


For example, the number in fig (a) indicates the order in which the edges and portion of edges are traced. We begin at the starting vertex and continue along the same edge (from 1 to 2) of the subject polygon as it enters the clip polygon. As we move along the edge that is leaving the clip polygon, we make a right turn (from 4 to 5) onto the clip polygon, which is now considered the subject polygon. Following the same logic leads to the next right turn (from 5 to 6) onto the current clip polygon, this is the original subject polygon. With the next step done (from 7 to 8) in the same way, we have a sub-polygon for output in fig (b). We then resume our traversal of the original subject polygon from the recorded intersection point where we first changed our course. Going from 9 to 10 to 11 produces no output. After skipping the already traversed 6 and 7, we continue with 12 and 13 and come to an end. The fig (b) is the final result.


Part 9: Clipping and Polygon various Technique algorithm

Part 6: Filled Area Primitives different algorithm on Computer Graphics.

Filled Area Primitives:

Region filling is the process of filling image or region. Filling can be of boundary or interior region as shown in fig. Boundary Fill algorithms are used to fill the boundary and flood-fill algorithm are used to fill the interior.

Filled Area Primitives

Boundary Filled Algorithm:
This algorithm uses the recursive method. First of all, a starting pixel called as the seed is considered. The algorithm checks boundary pixel or adjacent pixels are colored or not. If the adjacent pixel is already filled or colored then leave it, otherwise fill it.

Boundary Filled Algorithm

The filling is done using four connected or eight connected approaches.

Boundary Filled Algorithm

Four connected approaches is more suitable than the eight connected approaches.

1. Four connected approaches: In this approach, left, right, above, below pixels are tested.

2. Eight connected approaches: In this approach, left, right, above, below and four diagonals are selected.

Boundary can be checked by seeing pixels from left and right first. Then pixels are checked by seeing pixels from top to bottom. The algorithm takes time and memory because some recursive calls are needed.

Problem with recursive boundary fill algorithm:
It may not fill regions sometimes correctly when some interior pixel is already filled with color. The algorithm will check this boundary pixel for filling and will found already filled so recursive process will terminate. This may vary because of another interior pixel unfilled.

So check all pixels color before applying the algorithm.


Procedure fill (x, y, color, color1: integer)
int c;
c=getpixel (x, y);
if (c!=color) (c!=color1)
setpixel (x, y, color)
fill (x+1, y, color, color 1);
fill (x-1, y, color, color 1);
fill (x, y+1, color, color 1);
fill (x, y-1, color, color 1);

Flood Fill Algorithm:

In this method, a point or seed which is inside region is selected. This point is called a seed point. Then four connected approaches or eight connected approaches is used to fill with specified color.

The flood fill algorithm has many characters similar to boundary fill. But this method is more suitable for filling multiple colors boundary. When boundary is of many colors and interior is to be filled with one color we use this algorithm.


In fill algorithm, we start from a specified interior point (x, y) and reassign all pixel values are currently set to a given interior color with the desired color. Using either a 4-connected or 8-connected approaches, we then step through pixel positions until all interior points have been repainted.


  1. Very slow algorithm
  2. May be fail for large polygons
  3. Initial pixel required more knowledge about surrounding pixels.


  1. Procedure floodfill (x, y,fill_ color, old_color: integer)  
        If (getpixel (x, y)=old_color)  
        setpixel (x, y, fill_color);  
        fill (x+1, y, fill_color, old_color);  
         fill (x-1, y, fill_color, old_color);  
        fill (x, y+1, fill_color, old_color);  
        fill (x, y-1, fill_color, old_color);  


Program1: To implement 4-connected flood fill algorithm:

  1. #include<stdio.h>  
    void flood(int,int,int,int);  
    void main()  
    void flood(intx,inty,intfillColor, intdefaultColor)  


Flood Fill Algorithm

Program2: To implement 8-connected flood fill algorithm:

  1. #include<stdio.h>  
    void floodfill(intx,inty,intold,intnewcol)  
                    int current;  
    void main()  


Flood Fill Algorithm

Scan Line Polygon Fill Algorithm:

This algorithm lines interior points of a polygon on the scan line and these points are done on or off according to requirement. The polygon is filled with various colors by coloring various pixels.

In above figure polygon and a line cutting polygon in shown. First of all, scanning is done. Scanning is done using raster scanning concept on display device. The beam starts scanning from the top left corner of the screen and goes toward the bottom right corner as the endpoint. The algorithms find points of intersection of the line with polygon while moving from left to right and top to bottom. The various points of intersection are stored in the frame buffer. The intensities of such points is keep high. Concept of coherence property is used. According to this property if a pixel is inside the polygon, then its next pixel will be inside the polygon.

Scan Line Polygon Fill Algorithm

Side effects of Scan Conversion:

1. Staircase or Jagged: Staircase like appearance is seen while the scan was converting line or circle.

2. Unequal Intensity: It deals with unequal appearance of the brightness of different lines. An inclined line appears less bright as compared to the horizontal and vertical line.

Scan Line Polygon Fill Algorithm