Cac Tt Xen Hinh

BÀI CHUYÊN ĐỀ A2: CÁC THUẬT TOÁN XÉN HÌNH  Cohen-Sutherland  Liang-Barsky  Sutherland-Hodgeman

Nhóm sinh viên thực hiện: Nguyễn Thị Hiền Triệu Thị Thu Hiền Nghiêm Văn Hiệp Đặng Hà Hoa Trần Kim Hoàn

THUẬT TOÁN COHEN_SUTHERLAND CLIPPING ĐƯỜNG THẲNG VỚI CỬA SỔ HÌNH CHỮ NHẬT

Để clipping đường thẳng với hình chữ nhật, chúng ta phải thực hiện các bước sau : • •

Kiểm tra xem đường thẳng này nằm trong hay ngoài , hay là có giao điểm với hinh chữ nhật bằng cách tính mã vùng . Sau đó nếu đường thẳng có giao điểm với hình chữ nhật thì sẽ xác định tọa độ giao điểm này dựa vào phương trình đường thằng để từ đó xác định phần của đường thẳng nằm trong cửa sổ hình chữ nhật (nếu có) .

Chương trình :

/*************************************************************************/ /*************************************************************************

A C++ program to show the implementation of Cohen-Sutherland Line Clipping

Algorithm.

*************************************************************************/ /*************************************************************************/

/*************************************************************************

*************************************************************************/

/*************************************************************************/ /*************************************************************************/ //--------------------------- Header Files ----------------------------// /*************************************************************************/ /*************************************************************************/

# include # include # include



# include

<math.h>

/*************************************************************************/ /*************************************************************************/ //----------------- Class Declarations & Definitions ------------------// /*************************************************************************/ /*************************************************************************/

/*************************************************************************/

//--------------------------- LineCoordinates -------------------------// /*************************************************************************/

class LineCoordinates { public: float x_1; float y_1; float x_2; float y_2;

LineCoordinates(const float x1,const float y1, const float x2,const float y2) { x_1=x1; y_1=y1; x_2=x2; y_2=y2; } };

/*************************************************************************/ //------------------------- WindowCoordinates -------------------------// /*************************************************************************/

class WindowCoordinates {

public: float x_min; float y_min; float x_max; float y_max;

WindowCoordinates(const float x1,const float y1, const float x2,const float y2) { x_min=x1; y_min=y1; x_max=x2; y_max=y2; } };

/*************************************************************************/ //----------------------------- RegionCode ----------------------------// /*************************************************************************/

class RegionCode { public: int bit_1; int bit_2; int bit_3; int bit_4;

RegionCode( ) { bit_1=0; bit_2=0; bit_3=0; bit_4=0; }

const int equal_zero( ) { if(bit_1==0 && bit_2==0 && bit_3==0 && bit_4==0) return 1;

return 0; }

void get_logical_AND(RegionCode rc1,RegionCode rc2) { if(rc1.bit_1==1 && rc2.bit_1==1) bit_1=1;

if(rc1.bit_2==1 && rc2.bit_2==1) bit_2=1;

if(rc1.bit_3==1 && rc2.bit_3==1) bit_3=1;

if(rc1.bit_4==1 && rc2.bit_4==1) bit_4=1; }

void get_region_code(const WindowCoordinates wc, const int x,const int y) { if((wc.x_min-x)>0) bit_1=1;

if((x-wc.x_max)>0) bit_2=1;

if((wc.y_min-y)>0) bit_3=1;

if((y-wc.y_max)>0) bit_4=1; } };

/*************************************************************************/ /*************************************************************************/ //----------------------- Function Prototypes -------------------------// /*************************************************************************/ /*************************************************************************/

void show_screen( );

const int clip_line(const WindowCoordinates,LineCoordinates&);

void calculate_intersecting_points(const WindowCoordinates,LineCoordinates&);

void Rectangle(const int,const int,const int,const int); void Line(const int,const int,const int,const int);

/*************************************************************************/ /*************************************************************************/ //------------------------------ main( ) ------------------------------// /*************************************************************************/ /*************************************************************************/

int main( ) { int driver=VGA; int mode=VGAHI;

initgraph(&driver,&mode,"C:\\TC\\BGI");

show_screen( );

WindowCoordinates WC(180,140,470,340);

setcolor(15); Rectangle(WC.x_min,WC.y_min,WC.x_max,WC.y_max);

LineCoordinates LC_1(150,160,120,320); LineCoordinates LC_2(250,150,200,200); LineCoordinates LC_3(160,200,490,260); LineCoordinates LC_4(300,300,400,380); LineCoordinates LC_5(550,300,450,400); LineCoordinates LC_6(440,110,400,370);

setcolor(7); Line(LC_1.x_1,LC_1.y_1,LC_1.x_2,LC_1.y_2); Line(LC_2.x_1,LC_2.y_1,LC_2.x_2,LC_2.y_2); Line(LC_3.x_1,LC_3.y_1,LC_3.x_2,LC_3.y_2); Line(LC_4.x_1,LC_4.y_1,LC_4.x_2,LC_4.y_2); Line(LC_5.x_1,LC_5.y_1,LC_5.x_2,LC_5.y_2); Line(LC_6.x_1,LC_6.y_1,LC_6.x_2,LC_6.y_2);

char Key=NULL;

do { Key=getch( ); } while(Key!='C' && Key!='c');

settextstyle(0,0,1);

setcolor(0); outtextxy(163,450," Press 'C' to see the Clipped Lines. ");

setcolor(15); outtextxy(165,450,"------

-------");

setcolor(12); outtextxy(213,450," Press any Key to exit. ");

setcolor(10);

if(clip_line(WC,LC_1)) Line(LC_1.x_1,LC_1.y_1,LC_1.x_2,LC_1.y_2);

if(clip_line(WC,LC_2)) Line(LC_2.x_1,LC_2.y_1,LC_2.x_2,LC_2.y_2);

if(clip_line(WC,LC_3)) Line(LC_3.x_1,LC_3.y_1,LC_3.x_2,LC_3.y_2);

if(clip_line(WC,LC_4)) Line(LC_4.x_1,LC_4.y_1,LC_4.x_2,LC_4.y_2);

if(clip_line(WC,LC_5)) Line(LC_5.x_1,LC_5.y_1,LC_5.x_2,LC_5.y_2);

if(clip_line(WC,LC_6))

Line(LC_6.x_1,LC_6.y_1,LC_6.x_2,LC_6.y_2);

getch( ); return 0; }

/*************************************************************************/ /*************************************************************************/ //------------------------ Funcion Definitions ------------------------// /*************************************************************************/ /*************************************************************************/

/*************************************************************************/ //--------------------------- clip_line( ) ----------------------------// /*************************************************************************/

const int clip_line(const WindowCoordinates wc,LineCoordinates &lc) { RegionCode rc1,rc2,rc;

rc1.get_region_code(wc,lc.x_1,lc.y_1); rc2.get_region_code(wc,lc.x_2,lc.y_2); rc.get_logical_AND(rc1,rc2);

if(rc1.equal_zero( ) && rc2.equal_zero( )) { lc.x_1=(int)(lc.x_1+0.5);

lc.y_1=(int)(lc.y_1+0.5); lc.x_2=(int)(lc.x_2+0.5); lc.y_2=(int)(lc.y_2+0.5);

return 1; }

else if(!rc.equal_zero( )) return 0;

else { calculate_intersecting_points(wc,lc); clip_line(wc,lc); }

return 1; }

/*************************************************************************/ //----------------- calculate_intersecting_points( ) ------------------// /*************************************************************************/

void calculate_intersecting_points(const WindowCoordinates wc, LineCoordinates &lc) { RegionCode rc1,rc2,rc;

rc1.get_region_code(wc,lc.x_1,lc.y_1); rc2.get_region_code(wc,lc.x_2,lc.y_2);

if(!rc1.equal_zero( )) { float m; float x=lc.x_1; float y=lc.y_1;

int dx=(lc.x_2-lc.x_1);

if(dx!=0) m=((lc.y_2-lc.y_1)/(lc.x_2-lc.x_1));

if(rc1.bit_1==1) { x=wc.x_min; y=(lc.y_1+(m*(x-lc.x_1))); }

else if(rc1.bit_2==1) { x=wc.x_max; y=(lc.y_1+(m*(x-lc.x_1))); }

else if(rc1.bit_3==1) { y=wc.y_min;

if(dx!=0) x=(lc.x_1+((y-lc.y_1)/m)); }

else if(rc1.bit_4==1) { y=wc.y_max;

if(dx!=0) x=(lc.x_1+((y-lc.y_1)/m)); }

lc.x_1=x; lc.y_1=y; }

if(!rc2.equal_zero( )) { float m; float x=lc.x_2; float y=lc.y_2;

int dx=(lc.x_2-lc.x_1);

if(dx!=0) m=((lc.y_2-lc.y_1)/(lc.x_2-lc.x_1));

if(rc2.bit_1==1) { x=wc.x_min; y=(lc.y_2+(m*(x-lc.x_2))); }

else if(rc2.bit_2==1) { x=wc.x_max; y=(lc.y_2+(m*(x-lc.x_2))); }

else if(rc2.bit_3==1) { y=wc.y_min;

if(dx!=0) x=(lc.x_2+((y-lc.y_2)/m)); }

else if(rc2.bit_4==1) { y=wc.y_max;

if(dx!=0) x=(lc.x_2+((wc.y_max-lc.y_2)/m)); }

lc.x_2=x; lc.y_2=y; } }

/*************************************************************************/ //--------------------------- Rectangle( ) ----------------------------// /*************************************************************************/

void Rectangle(const int x_1,const int y_1,const int x_2,const int y_2) { Line(x_1,y_1,x_2,y_1); Line(x_2,y_1,x_2,y_2); Line(x_2,y_2,x_1,y_2); Line(x_1,y_2,x_1,y_1); }

/*************************************************************************/ //------------------------------- Line( ) -----------------------------// /*************************************************************************/

void Line(const int x_1,const int y_1,const int x_2,const int y_2)

{ int color=getcolor( );

int x1=x_1; int y1=y_1;

int x2=x_2; int y2=y_2;

if(x_1>x_2) { x1=x_2; y1=y_2;

x2=x_1; y2=y_1; }

int dx=abs(x2-x1); int dy=abs(y2-y1); int inc_dec=((y2>=y1)?1:-1);

if(dx>dy) { int two_dy=(2*dy); int two_dy_dx=(2*(dy-dx)); int p=((2*dy)-dx);

int x=x1; int y=y1;

putpixel(x,y,color);

while(x<x2) { x++;

if(p<0) p+=two_dy;

else { y+=inc_dec; p+=two_dy_dx; }

putpixel(x,y,color); } }

else { int two_dx=(2*dx); int two_dx_dy=(2*(dx-dy));

int p=((2*dx)-dy);

int x=x1; int y=y1;

putpixel(x,y,color);

while(y!=y2) { y+=inc_dec;

if(p<0) p+=two_dx;

else { x++; p+=two_dx_dy; }

putpixel(x,y,color); } } }

/*************************************************************************/ //-------------------------- show_screen( ) ---------------------------//

/*************************************************************************/

void show_screen( ) { setfillstyle(1,1); bar(145,26,480,38);

settextstyle(0,0,1); setcolor(15); outtextxy(5,5,"****************************************************************** ************"); outtextxy(5,17,"***************************************************************************-*"); outtextxy(5,29,"*---------------

----------------*");

outtextxy(5,41,"***************************************************************************-*"); outtextxy(5,53,"***************************************************************************-*");

setcolor(11); outtextxy(152,29,"Cohen-Sutherland Line Clipping Algorithm");

setcolor(15);

for(int count=0;count<=30;count++) outtextxy(5,(65+(count*12)),"*-*

*-*");

outtextxy(5,438,"***************************************************************************-*"); outtextxy(5,450,"*-------------------

------------------*");

outtextxy(5,462,"**************************************************************** **************");

setcolor(12); outtextxy(163,450," Press 'C' to see the Clipped Lines. "); }

/*************************************************************************/ /*************************************************************************/ //----------------------------- THE END -------------------------------// /*************************************************************************/ /*************************************************************************/

CÀI ĐẶT THUẬT TOÁN LIANG_BARSKY /*************************************************************************/ /*************************************************************************

A C++ program to show the implementation of Liang-Barsky Line Clipping Algorithm.

*************************************************************************/ /*************************************************************************/

/************************************************************************* *************************************************************************/

/*************************************************************************/ /*************************************************************************/ //--------------------------- Header Files ----------------------------// /*************************************************************************/ /*************************************************************************/

# include # include # include



# include

<math.h>

/*************************************************************************/ /*************************************************************************/ //----------------- Class Declarations & Definitions ------------------// /*************************************************************************/ /*************************************************************************/

/*************************************************************************/ //--------------------------- LineCoordinates -------------------------// /*************************************************************************/

class LineCoordinates { public:

float x_1; float y_1; float x_2; float y_2;

LineCoordinates(const float x1,const float y1, const float x2,const float y2) { x_1=x1; y_1=y1; x_2=x2; y_2=y2; } };

/*************************************************************************/ //------------------------- WindowCoordinates -------------------------// /*************************************************************************/

class WindowCoordinates { public: float x_min; float y_min; float x_max; float y_max;

WindowCoordinates(const float x1,const float y1, const float x2,const float y2) { x_min=x1; y_min=y1; x_max=x2; y_max=y2; } };

/*************************************************************************/ /*************************************************************************/ //----------------------- Function Prototypes -------------------------// /*************************************************************************/ /*************************************************************************/

void show_screen( );

const int clip_line(const WindowCoordinates,LineCoordinates&); const int check_line(const float,const float,float&,float&);

void Rectangle(const int,const int,const int,const int); void Line(const int,const int,const int,const int);

/*************************************************************************/ /*************************************************************************/ //------------------------------ main( ) ------------------------------//

/*************************************************************************/ /*************************************************************************/

int main( ) { int driver=VGA; int mode=VGAHI;

initgraph(&driver,&mode,"C:\\TC\\BGI");

show_screen( );

WindowCoordinates WC(180,140,470,340);

setcolor(15); Rectangle(WC.x_min,WC.y_min,WC.x_max,WC.y_max);

LineCoordinates LC_1(150,160,120,320); LineCoordinates LC_2(250,150,200,200); LineCoordinates LC_3(160,200,490,260); LineCoordinates LC_4(300,300,400,380); LineCoordinates LC_5(550,300,450,400); LineCoordinates LC_6(440,110,400,370);

setcolor(7); Line(LC_1.x_1,LC_1.y_1,LC_1.x_2,LC_1.y_2); Line(LC_2.x_1,LC_2.y_1,LC_2.x_2,LC_2.y_2);

Line(LC_3.x_1,LC_3.y_1,LC_3.x_2,LC_3.y_2); Line(LC_4.x_1,LC_4.y_1,LC_4.x_2,LC_4.y_2); Line(LC_5.x_1,LC_5.y_1,LC_5.x_2,LC_5.y_2); Line(LC_6.x_1,LC_6.y_1,LC_6.x_2,LC_6.y_2);

char Key=NULL;

do { Key=getch( ); } while(Key!='C' && Key!='c');

settextstyle(0,0,1); setcolor(0); outtextxy(163,450," Press 'C' to see the Clipped Lines. ");

setcolor(15); outtextxy(163,450,"------

-------");

setcolor(12); outtextxy(213,450," Press any Key to exit. ");

setcolor(10);

if(clip_line(WC,LC_1)) Line(LC_1.x_1,LC_1.y_1,LC_1.x_2,LC_1.y_2);

if(clip_line(WC,LC_2)) Line(LC_2.x_1,LC_2.y_1,LC_2.x_2,LC_2.y_2);

if(clip_line(WC,LC_3)) Line(LC_3.x_1,LC_3.y_1,LC_3.x_2,LC_3.y_2);

if(clip_line(WC,LC_4)) Line(LC_4.x_1,LC_4.y_1,LC_4.x_2,LC_4.y_2);

if(clip_line(WC,LC_5)) Line(LC_5.x_1,LC_5.y_1,LC_5.x_2,LC_5.y_2);

if(clip_line(WC,LC_6)) Line(LC_6.x_1,LC_6.y_1,LC_6.x_2,LC_6.y_2);

getch( ); return 0; }

/*************************************************************************/ /*************************************************************************/ //------------------------ Funcion Definitions ------------------------// /*************************************************************************/ /*************************************************************************/

/*************************************************************************/

//--------------------------- clip_line( ) ----------------------------// /*************************************************************************/

const int clip_line(const WindowCoordinates wc,LineCoordinates &lc) { float u_1=0; float u_2=1;

float dx=(lc.x_2-lc.x_1); float dy=(lc.y_2-lc.y_1);

float p1=(-dx); float p2=dx; float p3=(-dy); float p4=dy;

float q1=(lc.x_1-wc.x_min); float q2=(wc.x_max-lc.x_1); float q3=(lc.y_1-wc.y_min); float q4=(wc.y_max-lc.y_1);

if(check_line(p1,q1,u_1,u_2) && check_line(p2,q2,u_1,u_2) && check_line(p3,q3,u_1,u_2) && check_line(p4,q4,u_1,u_2)) { if(u_2<1) { lc.x_2=(lc.x_1+(u_2*dx));

lc.y_2=(lc.y_1+(u_2*dy)); }

if(u_1>0) { lc.x_1+=(u_1*dx); lc.y_1+=(u_1*dy); }

lc.x_1=(int)(lc.x_1+0.5); lc.y_1=(int)(lc.y_1+0.5); lc.x_2=(int)(lc.x_2+0.5); lc.y_2=(int)(lc.y_2+0.5);

return 1; }

return 0; }

/*************************************************************************/ //------------------------------ check_line( ) ------------------------// /*************************************************************************/

const int check_line(const float p,const float q,float &u_1,float &u_2) { int flag=1;

float r=(q/p);

if(p<0) { if(r>u_2) flag=0;

else if(r>u_1) u_1=r; }

else if(p>0) { if(r
else if(r
else { if(q<0) flag=0; }

return flag; }

/*************************************************************************/ //--------------------------- Rectangle( ) ----------------------------// /*************************************************************************/

void Rectangle(const int x_1,const int y_1,const int x_2,const int y_2) { Line(x_1,y_1,x_2,y_1); Line(x_2,y_1,x_2,y_2); Line(x_2,y_2,x_1,y_2); Line(x_1,y_2,x_1,y_1); }

/*************************************************************************/ //-------------------------- Line( ) ------------------------// /*************************************************************************/

void Line(const int x_1,const int y_1,const int x_2,const int y_2) { int color=getcolor( );

int x1=x_1; int y1=y_1;

int x2=x_2;

int y2=y_2;

if(x_1>x_2) { x1=x_2; y1=y_2;

x2=x_1; y2=y_1; }

int dx=abs(x2-x1); int dy=abs(y2-y1); int inc_dec=((y2>=y1)?1:-1);

if(dx>dy) { int two_dy=(2*dy); int two_dy_dx=(2*(dy-dx)); int p=((2*dy)-dx);

int x=x1; int y=y1;

putpixel(x,y,color);

while(x<x2)

{ x++;

if(p<0) p+=two_dy;

else { y+=inc_dec; p+=two_dy_dx; }

putpixel(x,y,color); } }

else { int two_dx=(2*dx); int two_dx_dy=(2*(dx-dy)); int p=((2*dx)-dy);

int x=x1; int y=y1;

putpixel(x,y,color);

while(y!=y2) { y+=inc_dec;

if(p<0) p+=two_dx;

else { x++; p+=two_dx_dy; }

putpixel(x,y,color); } } }

/*************************************************************************/ //-------------------------- show_screen( ) ---------------------------// /*************************************************************************/

void show_screen( ) { setfillstyle(1,1); bar(165,26,470,38);

settextstyle(0,0,1); setcolor(15); outtextxy(5,5,"****************************************************************** ************"); outtextxy(5,17,"***************************************************************************-*"); outtextxy(5,29,"*------------------

------------------*");

outtextxy(5,41,"***************************************************************************-*"); outtextxy(5,53,"***************************************************************************-*");

setcolor(11); outtextxy(174,29,"Liang-Barsky Line Clipping Algorithm");

setcolor(15);

for(int count=0;count<=30;count++) outtextxy(5,(65+(count*12)),"*-*

*-*");

outtextxy(5,438,"***************************************************************************-*"); outtextxy(5,450,"*-------------------

------------------*");

outtextxy(5,462,"**************************************************************** **************");

setcolor(12); outtextxy(163,450," Press 'C' to see the Clipped Lines. ");

}

/*************************************************************************/ /*************************************************************************/ //----------------------------- THE END -------------------------------// /*************************************************************************/ /*************************************************************************/

THUẬT TOÁN CLIPPING 2 ĐA GIÁC (SUTHERLAND – HOGMAN) Bài toán clipping 2 đa giác là sự mở rộng của bài toán clipping đường thẳng với đa giác ( thuật toán cyrus beck) .Để clipping đa giác p với một đa giác q , phải thực hiện các bước sau : –

Chuyển p đa giác thành đa giác lồi.

–

Xét lần lượt từng cạnh của đa giác q với từng cạnh của đa giác p , ứng với từng cạnh của q , chúng ta sẽ gọi lại thuật toán cyrus-beck để tìm phần của cạnh của q với đa giác p , cứ tiếp tục như thế cho đến hết các cạnh của q.

–

Kết qủa khi clipping 2 đa giác là một đa giác nằm trong đa giác p (nếu có)

/*************************************************************************/ /*************************************************************************

A C++ program to show the implementation of Sutherland-Hodgeman Polygon Clipping Algorithm.

*************************************************************************/ /*************************************************************************/

/*************************************************************************

*************************************************************************/

/*************************************************************************/ /*************************************************************************/ //--------------------------- Header Files ----------------------------// /*************************************************************************/ /*************************************************************************/

# include # include # include



# include

<math.h>

/*************************************************************************/ /*************************************************************************/ //----------------- Class Declarations & Definitions ------------------// /*************************************************************************/ /*************************************************************************/

/*************************************************************************/ //-------------------------- PointCoordinates -------------------------// /*************************************************************************/

class PointCoordinates { public: float x;

float y;

PointCoordinates( ) { x=0; y=0; } };

/*************************************************************************/ //--------------------------- LineCoordinates -------------------------// /*************************************************************************/

class LineCoordinates { public: float x_1; float y_1; float x_2; float y_2;

LineCoordinates( ) { x_1=0; y_1=0; x_2=0; y_2=0;

}

LineCoordinates(const float x1,const float y1, const float x2,const float y2) { x_1=x1; y_1=y1; x_2=x2; y_2=y2; } };

/*************************************************************************/ //------------------------- WindowCoordinates -------------------------// /*************************************************************************/

class WindowCoordinates { public: float x_min; float y_min; float x_max; float y_max;

WindowCoordinates(const float x1,const float y1, const float x2,const float y2) {

x_min=x1; y_min=y1; x_max=x2; y_max=y2; } };

/*************************************************************************/ /*************************************************************************/ //----------------------- Function Prototypes -------------------------// /*************************************************************************/ /*************************************************************************/

void show_screen( );

void clip_polygon(const WindowCoordinates,const int,const int []);

const int check_line(const LineCoordinates,const LineCoordinates); const int check_point(const LineCoordinates,const float,const float);

const PointCoordinates get_intersection_point(LineCoordinates, LineCoordinates);

void Polygon(const int,const int []); void Rectangle(const int,const int,const int,const int); void Line(const int,const int,const int,const int);

/*************************************************************************/ /*************************************************************************/ //------------------------------ main( ) ------------------------------// /*************************************************************************/ /*************************************************************************/

int main( ) { int driver=VGA; int mode=VGAHI;

initgraph(&driver,&mode,"C:\\TC\\BGI");

show_screen( );

WindowCoordinates WC(180,140,470,340);

setcolor(15); Rectangle(WC.x_min,WC.y_min,WC.x_max,WC.y_max);

int n=10;

int polygon_vertices[20]={ 100,240 , 180,370 , 210,310 , 380,375 , 520,310 , 480,260 , 510,80 , 280,180 , 210,90 , 100,240 };

setcolor(7);

Polygon(n,polygon_vertices);

setcolor(15); settextstyle(0,0,1); outtextxy(300,240,"Window"); outtextxy(80,240,"Polygon");

char Key=NULL;

do { Key=getch( ); } while(Key!='C' && Key!='c');

settextstyle(0,0,1); setcolor(0); outtextxy(163,450," Press 'C' to see the Clipped Polygon. ");

setcolor(15); outtextxy(163,450,"------

---------");

setcolor(12); outtextxy(213,450," Press any Key to exit. ");

clip_polygon(WC,n,polygon_vertices);

setcolor(15); settextstyle(0,0,1); outtextxy(280,155,"Clipped Polygon");

getch( ); return 0; }

/*************************************************************************/ /*************************************************************************/ //------------------------ Funcion Definitions ------------------------// /*************************************************************************/ /*************************************************************************/

/*************************************************************************/ //-------------------------- clip_polygon( ) --------------------------// /*************************************************************************/

void clip_polygon(const WindowCoordinates wc,const int n, const int polygon_edges[]) { int edges_counter; int number_of_edges=n;

int *edges=new int[(n*4)]; int *clipped_edges=new int[(n*4)];

for(int count_1=0;count_1<(n*2);count_1++) edges[count_1]=polygon_edges[count_1];

LineCoordinates window_line;

for(int count_2=1;count_2<=4;count_2++) { edges_counter=1;

for(int count_3=0;count_3<(number_of_edges*4);count_3++) clipped_edges[count_3]=0;

if(count_2==1) { window_line.x_1=wc.x_min; window_line.y_1=wc.y_max; window_line.x_2=wc.x_max; window_line.y_2=wc.y_max; }

else if(count_2==2) { window_line.x_1=wc.x_max; window_line.y_1=wc.y_max; window_line.x_2=wc.x_max; window_line.y_2=wc.y_min; }

else if(count_2==3) { window_line.x_1=wc.x_max; window_line.y_1=wc.y_min; window_line.x_2=wc.x_min; window_line.y_2=wc.y_min; }

else if(count_2==4) { window_line.x_1=wc.x_min; window_line.y_1=wc.y_min; window_line.x_2=wc.x_min; window_line.y_2=wc.y_max; }

int rule_no;

PointCoordinates point;

for(int count_4=1;count_4
rule_no=check_line(window_line,line);

switch(rule_no) { case 1 : clipped_edges[(edges_counter*2)]= (int)(line.x_2+0.5); clipped_edges[((edges_counter*2)+1)]= (int)(line.y_2+0.5); edges_counter++; break;

case 2 : break;

case 3 : point= get_intersection_point(window_line,line);

clipped_edges[(edges_counter*2)]= (int)(point.x+0.5); clipped_edges[((edges_counter*2)+1)]= (int)(point.y+0.5); edges_counter++; break;

case 4 : point= get_intersection_point(window_line,line);

clipped_edges[(edges_counter*2)]= (int)(point.x+0.5); clipped_edges[((edges_counter*2)+1)]= (int)(point.y+0.5); edges_counter++;

clipped_edges[(edges_counter*2)]= (int)(line.x_2+0.5); clipped_edges[((edges_counter*2)+1)]= (int)(line.y_2+0.5); edges_counter++; break; } }

clipped_edges[0]=clipped_edges[((edges_counter*2)-2)]; clipped_edges[1]=clipped_edges[((edges_counter*2)-1)];

for(int count_5=0;count_5<(edges_counter*2);count_5++) edges[count_5]=0;

number_of_edges=edges_counter;

for(int count_6=0;count_6<(edges_counter*2);count_6++) edges[count_6]=clipped_edges[count_6]; }

setcolor(10); Polygon(number_of_edges,edges);

delete edges; delete clipped_edges; }

/*************************************************************************/ //---------------------------- check_line( ) --------------------------// /*************************************************************************/

const int check_line(const LineCoordinates line,const LineCoordinates edge) { int rule_number=0; int point_1=check_point(line,edge.x_1,edge.y_1); int point_2=check_point(line,edge.x_2,edge.y_2);

if(point_1==1 && point_2==1) rule_number=1;

else if(point_1!=1 && point_2!=1) rule_number=2;

else if(point_1==1 && point_2!=1) rule_number=3;

else if(point_1!=1 && point_2==1)

rule_number=4;

return rule_number; }

/*************************************************************************/ //---------------------------- check_point( ) -------------------------// /*************************************************************************/

const int check_point(const LineCoordinates lc,const float x,const float y) { float c=(((lc.x_2-lc.x_1)*(y-lc.y_1))-((lc.y_2-lc.y_1)*(x-lc.x_1)));

if(c<=0) return 1;

else return 0; }

/*************************************************************************/ //---------------------- get_intersection_point( ) --------------------// /*************************************************************************/

const PointCoordinates get_intersection_point(LineCoordinates lc1, LineCoordinates lc2) {

float x_min=lc1.x_1; float x_max=lc1.x_2; float y_min=lc1.y_1; float y_max=lc1.y_2;

if(lc1.x_1==lc1.x_2) { if(lc2.y_2>=lc2.y_1 && lc2.y_2>y_max) y_max=lc2.y_2;

else if(lc2.y_1>lc2.y_2 && lc2.y_1>y_max) y_max=lc2.y_1;

if(lc2.y_1<=lc2.y_2 && lc2.y_1
else if(lc2.y_2
else if(lc1.y_1==lc1.y_2) { if(lc2.x_2>=lc2.x_1 && lc2.x_2>x_max) x_max=lc2.x_2;

else if(lc2.x_2x_max) x_max=lc2.x_1;

if(lc2.x_1<=lc2.x_2 && lc2.x_1<x_min) x_min=lc2.x_1;

else if(lc2.x_2
float x_mid; float y_mid;

if(lc2.y_1>y_max) { while(lc2.y_1!=y_max) { x_mid=((lc2.x_1+lc2.x_2)/2); y_mid=((lc2.y_1+lc2.y_2)/2);

if(y_mid>=y_max) { lc2.x_1=x_mid; lc2.y_1=y_mid; }

else { lc2.x_2=x_mid;

lc2.y_2=y_mid; } } }

else if(lc2.y_1
if(y_mid<=y_min) { lc2.x_1=x_mid; lc2.y_1=y_mid; }

else { lc2.x_2=x_mid; lc2.y_2=y_mid; } } }

if(lc2.x_1>x_max)

{ while(lc2.x_1!=x_max) { x_mid=((lc2.x_1+lc2.x_2)/2); y_mid=((lc2.y_1+lc2.y_2)/2);

if(x_mid>=x_max) { lc2.x_1=x_mid; lc2.y_1=y_mid; }

else { lc2.x_2=x_mid; lc2.y_2=y_mid; } } }

else if(lc2.x_1<x_min) { while(lc2.x_1!=x_min) { x_mid=((lc2.x_1+lc2.x_2)/2); y_mid=((lc2.y_1+lc2.y_2)/2);

if(x_mid<=x_min) { lc2.x_1=x_mid; lc2.y_1=y_mid; }

else { lc2.x_2=x_mid; lc2.y_2=y_mid; } } }

PointCoordinates ipt;

ipt.x=lc2.x_1; ipt.y=lc2.y_1;

return ipt; }

/*************************************************************************/ //--------------------------- Rectangle( ) ----------------------------// /*************************************************************************/

void Rectangle(const int x_1,const int y_1,const int x_2,const int y_2) { Line(x_1,y_1,x_2,y_1); Line(x_2,y_1,x_2,y_2); Line(x_2,y_2,x_1,y_2); Line(x_1,y_2,x_1,y_1); }

/*************************************************************************/ //----------------------------- Polygon( ) ----------------------------// /*************************************************************************/

void Polygon(const int n,const int coordinates[]) { if(n>=2) { Line(coordinates[0],coordinates[1], coordinates[2],coordinates[3]);

for(int count=1;count<(n-1);count++) Line(coordinates[(count*2)],coordinates[((count*2)+1)], coordinates[((count+1)*2)], coordinates[(((count+1)*2)+1)]); } }

/*************************************************************************/

//-------------------------- Line( ) ------------------------// /*************************************************************************/

void Line(const int x_1,const int y_1,const int x_2,const int y_2) { int color=getcolor( );

int x1=x_1; int y1=y_1;

int x2=x_2; int y2=y_2;

if(x_1>x_2) { x1=x_2; y1=y_2;

x2=x_1; y2=y_1; }

int dx=abs(x2-x1); int dy=abs(y2-y1); int inc_dec=((y2>=y1)?1:-1);

if(dx>dy)

{ int two_dy=(2*dy); int two_dy_dx=(2*(dy-dx)); int p=((2*dy)-dx);

int x=x1; int y=y1;

putpixel(x,y,color);

while(x<x2) { x++;

if(p<0) p+=two_dy;

else { y+=inc_dec; p+=two_dy_dx; }

putpixel(x,y,color); } }

else { int two_dx=(2*dx); int two_dx_dy=(2*(dx-dy)); int p=((2*dx)-dy);

int x=x1; int y=y1;

putpixel(x,y,color);

while(y!=y2) { y+=inc_dec;

if(p<0) p+=two_dx;

else { x++; p+=two_dx_dy; }

putpixel(x,y,color); } }

}

/*************************************************************************/ //-------------------------- show_screen( ) ---------------------------// /*************************************************************************/

void show_screen( ) { setfillstyle(1,1); bar(125,26,510,38);

settextstyle(0,0,1); setcolor(15); outtextxy(5,5,"****************************************************************** ************"); outtextxy(5,17,"***************************************************************************-*"); outtextxy(5,29,"*-------------

-------------*");

outtextxy(5,41,"***************************************************************************-*"); outtextxy(5,53,"***************************************************************************-*");

setcolor(11); outtextxy(134,29,"Sutherland-Hodgeman Polygon Clipping Algorithm");

setcolor(15);

for(int count=0;count<=30;count++) outtextxy(5,(65+(count*12)),"*-*

*-*");

outtextxy(5,438,"***************************************************************************-*"); outtextxy(5,450,"*-------------------

----------------*");

outtextxy(5,462,"**************************************************************** **************");

setcolor(12); outtextxy(163,450," Press 'C' to see the Clipped Polygon. "); }

/*************************************************************************/ /*************************************************************************/ //----------------------------- THE END -------------------------------// /*************************************************************************/ /*************************************************************************/