3.1 เส้นตรง (Line)

            สมการในการคำนวณหาเส้นตรงคือ

                        Y = mX + b

            โดย m คือ ความชันของเส้นตรง หาได้ จาก

                        m = (Y2 – Y1) / (X2 – X1)

            และ b คือจุดตัดของเส้นตรงบนแกน Y หาได้จาก

                        b = Y1 – mX1

            จากสมการดังกล่าวได้มีการพัฒนา Algorithm สำหรับการวาดเส้นตรงขึ้นหลาย Algorithm แต่ในที่นี้จะกล่าวถึง 2 Algorithm คือ DDA Algorithm และ Bresenham’s Line Algorithm

 

          3.1.1 DDA(Digital  Differential  Analyzer)  Algorithm

1.      Input จุด 2 จุดสำหรับการวาดเส้นตรง คือ (X1,Y1) และ (X2,Y2)

2.      คำนวณหา dx,dy,steps,x_icrement,y_increment

dx = X2 – X1

dy = Y2 – Y1

IF | dx | > | dy | then

      steps = | dx |

Else

      stepts = | dy|

x_increment = dx / steps

y_increment = dy / steps

3.      plot จุดแรก คือ (Xk,Yk) = (X1,Y1)

4.      คำนวณหาจุดที่จะ plot ต่อไป จาก

Xk+1 = Xk + x_increment

Yk+1 = Yk + y_increment

5.      plot จุด ( Xk+1,Yk+1)

6.      ทำซ้ำ ข้อ 4,5 เป็นจำนวน steps ครั้ง

 

 

            จาก Algorithm สังเกตได้ว่าจุดที่จะ plot นั้นให้ค่าเป็นเลขจุดทศนิยม ซึ่งในทางปฏิบัติแล้วไม่สามารถ plot ได้ เนื่องจาก pixel บนจอภาพไม่ได้มีค่าเป็นเลขจุดทศนิยมแต่เป็นจำนวนเต็ม ดังนั้นก่อนที่จะ plot จุดลงบนจอภาพจะต้องทำการปัดเศษเสียก่อนจึงจะสามารถ plot ลงบนจอภาพได้

 

          3.1.2 Bresenham’s Line Algorithm

1.      Input จุด 2 จุดสำหรับการวาดเส้นตรง คือ (X0,Y0) และ (X1,Y1) และเก็บ (X0,Y0) ไว้สำหรับคำนวณ

2.      plot (X0,Y0) เป็นจุดแรก

3.      คำนวณหา dx,dy,2dx,2dy,2dy-2dx และค่าเริ่มต้นสำหรับการตัดสินใจในการคำนวณหาจุดที่จะ plot ต่อไป ดังนี้  P0 = 2dy - dx

4.      ที่แต่ละ Xk ตลอดเส้น เริ่มที่ k = 0

IF  Pk < 0  then

    จุดต่อไปที่จะ plot คือ (Xk + 1,Yk) และ Pk+1 = Pk +2dy

Else

    จุดต่อไปที่จะ plot คือ (Xk + 1,Yk + 1) และ Pk+1 = Pk +2dy-2dx

5.      ทำซ้ำ ข้อ 3,4 เป็นจำนวน dx ครั้ง

 

 

            Bresenham]s Line Algorithm นี้ใช้ได้สำหรับเส้นตรงที่มีความชันเป็นบวกและน้อยกว่า 1 เท่านั้น

 

Back  Next