Cac Tt Xen Hinh

CÁC THUẬT TOÁN XÉN HÌNH

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

1.Giới thiệu: o Thao tác loại bỏ các phần hình ảnh nằm ngoài một vùng cho trước được gọi là xén hình. o Vùng được dùng để xén hình gọi là cửa sổ xén (clip window).

2.Các thuật toán xén điểm, đoạn thẳng: o Giả sử cửa sổ xén ( Clip window) là cửa sổ hình chữ nhật được định nghĩa bởi 2 điểm: • Điểm dưới bên trái(xmin, ymin) • Điểm trên bên phải(xmax, ymax) o Một điểm P(x,y) thuộc Clip window nếu:

o Xét bài toán xén đoạn thẳng được cho bởi 2 điểm P1(x1,y1) và P2(x2,y2) vào cửa sổ hình chữ nhật trên.

o Yêu cầu của bài toán xén đoạn thẳng: Loại bỏ phần đoạn thẳng nằm ngoài cửa sổ xén.

o Các nhận xét: 1. Các đoạn thẳng có 2 điểm hoàn toàn nằm trong cửa sổ thì cả đoạn thẳng nằm trong cửa sổ nên không cần xén.

2. Các đoạn thẳng có 2 điểm cùng nằm ngoài về một phía của cửa sổ xén thì cả đoạn thẳng sẽ nằm ngoài cửa sổ và sẽ bị xén mất.

TOP

LEFT

RIGHT

BOTTOM

3. Với các đoạn thẳng cắt biên cửa sổ xén, chúng ta phải tìm giao điểm của đoạn thẳng với biên cửa sổ để chọn phần nằm bên trong cửa sổ.

a. Thuật toán Cohen-Sutherland: + KN mã vùng (area code) Kéo dài các biên của cửa sổ, ta chia mặt phẳng thành chín vùng gồm cửa sổ xén và tám vùng xung quanh nó.

o Một con số 4 bit nhị phân gọi là mã vùng sẽ được gán mỗi vùng để mô tả vị trí tương đối của vùng đó so với cửa sổ. o Các vùng nằm ngoài biên trái (LEFT) của cửa sổ xén có bit 1 bằng 1. Các vùng còn lại có bit 1 bằng 0. o Tương tự cho các bit từ 2 đến 4: bit 2: RIGHT; bit 3: TOP; bit 4: BOTTOM.

+ Mã vùng của điểm: 0110

P(x,y)

int Encode(Point p) { int code = 0; if (p.x < xmin) if (p.x > xmax) if (p.y > ymax) if (p.y < ymin) return code; }

code |= LEFT; code |= RIGHT; code |= TOP; code | =BOTTOM;

Các giá trị của bit trong mã vùng được tính bằng cách so sánh giá trị tọa độ của điểm P(x,y) với các biên của cửa sổ. Ví dụ, bit 1 được đặt là 1 nếu x < xmin, bit 1 được đặt là 0 nếu x >= xmin.

+ Thuật toán: Gán mã vùng tương ứng cho các điểm đầu cuối của P1 và P2 của đoạn thẳng cần xén là c1 và c2. Dựa vào giá trị của c1 và c2, ta có các trường hợp sau: 1. Các đoạn thẳng nằm hoàn toàn bên trong cửa sổ sẽ có c1 == c2 == 0000, các đoạn thẳng này sau khi xén sẽ là chính nó nên thuật toán dừng tại đây.

0000

0000

2. Các đoạn thẳng nằm ngoài biên cửa sổ sẽ có đặc điểm sau: Tồn tại bit thứ k (k=1,..,4) sao cho c1 và c2 cùng có giá trị 1 tại bit thứ k. Ví dụ, nếu k = 1 thì đoạn thẳng sẽ nằm ngoài biên trái của cửa sổ. Đoạn thẳng này sẽ bị loại bỏ sau khi xén, cho nên thuật toán dừng tại đây. Khi cài đặt, chúng ta chỉ cần sử dụng phép toán AND của bit đối với c1 và c2. Nếu kết quả khác 0, đoạn thẳng sẽ nằm ngoài biên cửa sổ.

0110 AND 1010 -----0010 ≠0

3. Nếu c1 và c2 không thuộc hai trường hợp trên, chắc chắn rằng đoạn thẳng sẽ cắt biên cửa sổ. Chúng ta sẽ xác định giao điểm này. Trong trường hợp này, sẽ có ít nhất 1 đầu đoạn thẳng nằm ngoài cửa sổ, không mất tính tổng quát chúng ta giả sử đó là P1. Giả sử P’1 là giao điểm của đoạn thẳng với biên cửa sổ. Lúc này, đoạn thẳng ban đầu sẽ được xén thành P’1P2. Bây giờ, chúng ta xem P’1P2 là đoạn thẳng mới và sẽ áp dụng các thao tác xén trong các trường hợp trên để xén đoạn thẳng này cho tới khi đoạn thẳng được xén nằm hoàn toàn bên trong cửa sổ hay nằm ngoài biên cửa sổ.

P2 P1

+ Lưu đồ:

+ Xác định giao điểm của đoạn thẳng và cửa sổ xén: o Bằng cách xét mã vùng c1 của P1 , ta xác định đoạn thẳng cắt biên nào và tiến hành xác định giao điểm P’1 của đoạn thẳng với biên đó.

Giao điểm của đoạn thẳng với biên trái (c1 & LEFT != 0): m = (P2.y – P1.y) / (P2.x – P1.x) P’1.y = P1.y + m (xmin – P1.x) P’1.x = xmin

Giao điểm của đoạn thẳng với biên phải (c1 & RIGHT != 0): m = (P2.y – P1.y) / (P2.x – P1.x) P’1.y = P1.y + m (xmax – P1.x) P’1.x = xmax

Giao điểm của đoạn thẳng với biên trên (c1 & TOP != 0): m = (P2.x – P1.x) / (P2.y – P1.y) P’1.x = P1.x + m (ymax – P1.y) P’1.y = ymax

Giao điểm của đoạn thẳng với biên dưới(c1&BOTTOM!= 0): m = (P2.x – P1.x) / (P2.y – P1.y) P’1.x = P1.x + m (ymin – P1.y) P’1.y = ymin

+ Ví dụ:

1001

1000

0001

0000

0101

0100

1010

0010

01110

+ Cài đặt minh họa thuật toán Cohen-Sutherland:

/*************************************************************************/ /************************************************************************* 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 -------------------------------// /*************************************************************************/ /*************************************************************************/

b. Thuật toán Liang-Barsky: o Được phát triển dựa trên dạng tham số của đường thẳng:

o Ứng với mỗi giá trị t, ta có một điểm P tương ứng thuộc đường thẳng •Nếu t ≥ 1, điểm P thuộc tia P2x •Nếu t ≤ 0, điểm P thuộc tia P1x’ P2(x2,y2) •Nếu 0 ≤ t ≤ 1, điểm P thuộc P1 P2 P1(x1,y1) X’ t<0

t=0

t=1

X t>1

o Tập

hợp các điểm thuộc về phần giao của đoạn thẳng và cửa sổ xén ứng với các giá trị t thoả mãn hệ bpt:

o Đặt p1= - Dx, q1 = x1 – xmin p2= Dx, q2 = xmax – x1 p3= - Dy, q3 = y1 – ymin p4= Dy, q4 = ymax – y1 oTa được hệ:

o Có 2 trường hợp xảy ra: • Hệ bất phương trình vô nghiệm, đường thẳng bị loại. • Hệ bất phương trình có nghiệm, tập nghiệp thoả

o Ta xét các TH: • Nếu tồn tại k thuộc {1,2,3,4}: (pk =0) hoặc (qk<0) thì bpt ứng với k trên là vô nghiệm, do đó hệ vô nghiệm.

• Nếu với mọi k thuộc {1,2,3,4}: (pk ≠ 0 hoặc (qk≥0) thì với các bpt mà ứng với pk=0 là các bpt hiển nhiên, lúc này hệ bpt cần giải tương đương với hệ bpt có pk ≠ 0. • Với các bpt pkt≤ qk mà pk<0, ta có t≥qk/pk . • Với các bpt pkt≤ qk mà pk >0, ta có t≤ qk/pk .

o Cài đặt minh hoạ 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
/*************************************************************************/ //-------------------------- 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;

x++; p+=two_dx_dy; }

else {

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 -------------------------------// /*************************************************************************/ /*************************************************************************/

3. Thuật toán xén đa giác:

Thuật toán Sutherland-Hodgeman:  Nếu tất cả các đỉnh của đa giác đều nằm trong hình chữ nhật thì hình cần xén chính là đa giác.

 Trường hợp ngược lại: - Xuất phát từ 1 đỉnh nằm ngoài hình chữ nhật, ta chạy theo dọc biên của đa giác. Với mỗi cạnh của đa giác, ta có các TH: • Nếu cả 2 đỉnh đều nằm ngoài hình chữ nhật: Nếu Ma(Ai)and Ma(Ai+1+ ) khác 0000 thì không lưu đỉnh. Ngược lại thì lưu 2 giao điểm. • Ai ngoài, Ai+1+ trong : lưu giao điểm P và Ai+1 . • Cả 2 đỉnh đều nằm trong hình chữ nhật : lưu Ai và Ai+1. • Ai trong, Ai+1 ngoài : lưu Ai và giao điểm P. - Sau khi duyệt qua tất cả các cạnh của đa giác, thì ta có được 1 dãy các đỉnh mới phát sinh: B1B2Bn • Nếu trong dãy các đỉnh mới này có hai đỉnh liên tiếp không nằm trên cùng một cạnh của hình chữ nhật, giả sử hai đỉnh đó là Bi và Bi+1 thì ta đi dọc các cạnh của hình chữ nhật từ Bi đếnBi+1 đ ể tìm tất cả các đỉnh của hcn nằm trong đa gi ác rồi bổ sung chúng vào giữa Bi và Bj.

• Tập đỉnh mới tìm được chính là đa giác xén được. - Nếu tập đỉnh mới này là rỗng: Nếu có một đỉnh của hình chữ nhật nằm trong đa giác thì hình xén được chính là toàn bộ hcn. Ngược lại, hình xén được là rỗng. o Cài đặt thuật toán Sutherland-Hodgeman: /*************************************************************************/ /************************************************************************* 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
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);

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=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(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 -------------------------------// /*************************************************************************/ /*************************************************************************/