อัลกอริทึมการสร้างเส้น

เส้นเชื่อมต่อสองจุด มันเป็นองค์ประกอบพื้นฐานในกราฟิก ในการลากเส้นคุณต้องมีจุดสองจุดเพื่อลากเส้น ในสามอัลกอริทึมต่อไปนี้เราอ้างถึงจุดหนึ่งของบรรทัดเป็น $ X_ {0}, Y_ {0} $ และจุดที่สองของบรรทัดเป็น $ X_ {1}, Y_ {1} $

อัลกอริทึม DDA

อัลกอริทึม Digital Differential Analyzer (DDA) เป็นอัลกอริธึมการสร้างเส้นอย่างง่ายซึ่งอธิบายทีละขั้นตอนที่นี่

Step 1 - รับอินพุตของจุดสิ้นสุดสองจุด $ (X_ {0}, Y_ {0}) $ และ $ (X_ {1}, Y_ {1}) $

Step 2 - คำนวณความแตกต่างระหว่างสองจุดสิ้นสุด

dx = X₁ - X₀
dy = Y₁ - Y₀

Step 3- จากความแตกต่างที่คำนวณได้ในขั้นตอนที่ 2 คุณต้องระบุจำนวนขั้นตอนในการใส่พิกเซล ถ้า dx> dy คุณต้องมีขั้นตอนเพิ่มเติมในพิกัด x มิฉะนั้นในพิกัด y

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

Step 4 - คำนวณการเพิ่มขึ้นของพิกัด x และพิกัด y

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

Step 5 - ใส่พิกเซลโดยเพิ่มพิกัด x และ y ให้สำเร็จตามลำดับและวาดเส้นให้เสร็จสมบูรณ์

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Line Generation ของ Bresenham

อัลกอริทึม Bresenham เป็นอีกหนึ่งอัลกอริทึมการแปลงการสแกนที่เพิ่มขึ้น ข้อได้เปรียบที่สำคัญของอัลกอริทึมนี้คือใช้การคำนวณจำนวนเต็มเท่านั้น การเคลื่อนที่ข้ามแกน x ในช่วงเวลาของหน่วยและในแต่ละขั้นตอนให้เลือกระหว่างพิกัด y สองพิกัดที่ต่างกัน

ตัวอย่างเช่นดังที่แสดงในภาพประกอบต่อไปนี้จากตำแหน่ง (2, 3) คุณต้องเลือกระหว่าง (3, 3) และ (3, 4) คุณต้องการจุดที่ใกล้กับเส้นเดิมมากขึ้น

ที่ตำแหน่งตัวอย่าง $ X_ {k} + 1 $ การแยกแนวตั้งจากเส้นคณิตศาสตร์จะมีข้อความกำกับว่า $ d_ {upper} $ และ $ d_ {lower} $

จากภาพประกอบด้านบนพิกัด y บนเส้นคณิตศาสตร์ที่ $ x_ {k} + 1 $ คือ -

Y = m ($ X_ {k} $ + 1) + b

ดังนั้น $ d_ {upper} $ และ $ d_ {lower} $ จะได้รับดังนี้ -

$$ d_ {lower} = y-y_ {k} $$

$$ = m (X_ {k} + 1) + b - Y_ {k} $$

และ

$$ d_ {upper} = (y_ {k} + 1) - y $$

$ = Y_ {k} + 1 - ม. (X_ {k} + 1) - b $

คุณสามารถใช้สิ่งเหล่านี้เพื่อตัดสินใจง่ายๆว่าพิกเซลใดอยู่ใกล้เส้นคณิตศาสตร์มากขึ้น การตัดสินใจง่ายๆนี้ขึ้นอยู่กับความแตกต่างระหว่างตำแหน่งพิกเซลทั้งสอง

$$ d_ {lower} - d_ {upper} = 2m (x_ {k} + 1) - 2y_ {k} + 2b - 1 $$

ให้เราแทนที่mด้วยdy / dxโดยที่dxและdyคือความแตกต่างระหว่างจุดสิ้นสุด

$$ dx (d_ {lower} - d_ {upper}) = dx (2 \ frac {\ mathrm {d} y} {\ mathrm {d} x} (x_ {k} + 1) - 2y_ {k} + 2b - 1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + 2dy + 2dx (2b-1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

ดังนั้นพารามิเตอร์การตัดสินใจ $ P_ {k} $ สำหรับขั้นตอนที่kตามบรรทัดจะถูกกำหนดโดย -

$$ p_ {k} = dx (d_ {lower} - d_ {upper}) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

เครื่องหมายของพารามิเตอร์การตัดสินใจ $ P_ {k} $ เหมือนกับของ $ d_ {lower} - d_ {upper} $

หาก $ p_ {k} $ เป็นค่าลบให้เลือกพิกเซลที่ต่ำกว่าหรือเลือกพิกเซลบน

โปรดจำไว้ว่าการเปลี่ยนแปลงพิกัดเกิดขึ้นตามแกน x ในหน่วยขั้นตอนดังนั้นคุณสามารถทำทุกอย่างได้ด้วยการคำนวณจำนวนเต็ม ในขั้นตอนที่ k + 1 พารามิเตอร์การตัดสินใจถูกกำหนดเป็น -

$$ p_ {k +1} = 2dy.x_ {k + 1} - 2dx.y_ {k + 1} + C $$

ลบ $ p_ {k} $ จากสิ่งนี้เราได้ -

$$ p_ {k + 1} - p_ {k} = 2dy (x_ {k + 1} - x_ {k}) - 2dx (y_ {k + 1} - y_ {k}) $$

แต่ $ x_ {k + 1} $ เหมือนกับ $ (xk) + 1 $ ดังนั้น -

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx (y_ {k + 1} - y_ {k}) $$

โดยที่ $ Y_ {k + 1} - Y_ {k} $ เป็น 0 หรือ 1 ขึ้นอยู่กับเครื่องหมายของ $ P_ {k} $

พารามิเตอร์การตัดสินใจแรก $ p_ {0} $ ได้รับการประเมินที่ $ (x_ {0}, y_ {0}) $ ได้รับเป็น -

$$ p_ {0} = 2dy - dx $$

ตอนนี้โปรดทราบถึงประเด็นข้างต้นและการคำนวณทั้งหมดนี่คืออัลกอริทึม Bresenham สำหรับความชัน m <1 -

Step 1 - ป้อนจุดสิ้นสุดสองจุดของบรรทัดโดยจัดเก็บจุดปลายด้านซ้ายใน $ (x_ {0}, y_ {0}) $

Step 2 - พล็อตจุด $ (x_ {0}, y_ {0}) $

Step 3 - คำนวณค่าคงที่ dx, dy, 2dy และ (2dy - 2dx) และรับค่าแรกสำหรับพารามิเตอร์การตัดสินใจเป็น -

$$ p_ {0} = 2dy - dx $$

Step 4 - ในแต่ละ $ X_ {k} $ ตลอดแนวเริ่มต้นที่ k = 0 ให้ทำการทดสอบต่อไปนี้ -

ถ้า $ p_ {k} $ <0 จุดต่อไปที่จะลงจุดคือ $ (x_ {k} +1, y_ {k}) $ และ

$$ p_ {k + 1} = p_ {k} + 2dy $$ มิฉะนั้น

$$ (x_ {k}, y_ {k} +1) $$

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx $$

Step 5 - ทำซ้ำขั้นตอนที่ 4 (dx - 1) ครั้ง

สำหรับ m> 1 ให้ค้นหาว่าคุณต้องเพิ่ม x ในขณะที่เพิ่ม y ทุกครั้งหรือไม่

หลังจากแก้แล้วสมการสำหรับพารามิเตอร์การตัดสินใจ $ P_ {k} $ จะใกล้เคียงกันมากเพียงแค่ x และ y ในสมการได้รับการแลกเปลี่ยนกัน

อัลกอริทึมจุดกึ่งกลาง

อัลกอริทึมจุดกึ่งกลางเกิดจาก Bresenham ซึ่งแก้ไขโดย Pitteway และ Van Aken สมมติว่าคุณได้ใส่จุด P ไว้ที่พิกัด (x, y) แล้วและความชันของเส้นคือ 0 ≤ k ≤ 1 ดังแสดงในภาพประกอบต่อไปนี้

ตอนนี้คุณต้องตัดสินใจว่าจะวางจุดต่อไปที่ E หรือ N ซึ่งสามารถเลือกได้โดยระบุจุดตัดกัน Q ใกล้กับจุด N หรือ E มากที่สุดหากจุดตัดกัน Q อยู่ใกล้กับจุด N มากที่สุดดังนั้น N จะถือว่าเป็น จุดต่อไป; มิฉะนั้น E.

ก่อนอื่นให้คำนวณจุดกลาง M (x + 1, y + ½) หากจุดตัดกัน Q ของเส้นที่มีเส้นแนวตั้งเชื่อมต่อ E และ N อยู่ต่ำกว่า M ให้ใช้ E เป็นจุดถัดไป มิฉะนั้นจะใช้ N เป็นจุดถัดไป

ในการตรวจสอบสิ่งนี้เราต้องพิจารณาสมการนัย -

F (x, y) = mx + b - y

สำหรับม. บวกที่ X ที่กำหนด

ถ้า y อยู่บนเส้นแล้ว F (x, y) = 0
ถ้า y อยู่เหนือเส้นแล้ว F (x, y) <0
ถ้า y อยู่ต่ำกว่าเส้นแล้ว F (x, y)> 0