อัลกอริทึม เส้นตรงของเบรเซนแฮม (Bresenham's line algorithm)เป็นอัลกอริทึมการวาดเส้นที่กำหนดจุดในแรสเตอร์nมิติที่ควรเลือกเพื่อสร้างเส้นตรงที่ใกล้เคียงที่สุดระหว่างสองจุดโดยทั่วไปแล้วจะใช้ในการวาดเส้นตรงพื้นฐานในภาพบิตแมป (เช่น บนหน้าจอคอมพิวเตอร์ ) เนื่องจากใช้เพียงการบวกการลบและการเลื่อนบิตซึ่งเป็นการดำเนินการที่ประหยัดมากในสถาปัตยกรรมคอมพิวเตอร์ที่ใช้กันทั่วไปในอดีต เป็นอัลกอริทึมที่มีข้อผิดพลาดเพิ่มขึ้นและเป็นหนึ่งในอัลกอริทึมแรกๆ ที่พัฒนาขึ้นในสาขากราฟิก คอมพิวเตอร์ ส่วนขยายของอัลกอริทึมดั้งเดิมที่เรียกว่าอัลกอริทึมวงกลมจุดกึ่งกลาง (midpoint circle algorithm)อาจใช้สำหรับการวาด วงกลม

แม้ว่าอัลกอริทึมต่างๆ เช่นอัลกอริทึมของ Wuจะถูกใช้บ่อยในกราฟิกคอมพิวเตอร์สมัยใหม่ เนื่องจากสามารถรองรับการลดรอยหยัก (antialiasing) ได้แต่อัลกอริทึมเส้นของ Bresenham ก็ยังคงมีความสำคัญเนื่องจากความเร็วและความเรียบง่าย อัลกอริทึมนี้ถูกใช้ในฮาร์ดแวร์ เช่นเครื่องพลอตเตอร์และในชิปกราฟิกของการ์ดกราฟิก สมัยใหม่ นอกจากนี้ยังพบได้ในไลบรารีซอฟต์แวร์กราฟิก จำนวนมาก เนื่องจากอัลกอริทึมนั้นง่ายมาก จึงมักถูกนำไปใช้ในเฟิร์มแวร์หรือฮาร์ดแวร์กราฟิกของการ์ด กราฟิก สมัยใหม่

ปัจจุบัน คำว่า "Bresenham" ถูกนำมาใช้เรียกกลุ่มอัลกอริทึมที่ต่อยอดหรือดัดแปลงมาจากอัลกอริทึมดั้งเดิมของ Bresenham

อัลกอริทึมเส้นของเบรเซนแฮมตั้งชื่อตามแจ็ค เอลตัน เบรเซนแฮมผู้พัฒนาอัลกอริทึมนี้ในปี 1962 ที่IBMในปี 2001 เบรเซนแฮมเขียนว่า: ^{[ 1 ]}

ผมทำงานอยู่ในห้องปฏิบัติการคำนวณของศูนย์พัฒนาซอฟต์แวร์ IBM ที่ซานโฮเซเครื่องพลอตเตอร์ของ Calcompถูกต่อเข้ากับเครื่องIBM 1401ผ่านทางคอนโซลเครื่องพิมพ์ดีด 1407 [อัลกอริทึม] ถูกนำไปใช้งานจริงในช่วงฤดูร้อนปี 1962 อาจจะก่อนหน้านั้นประมาณหนึ่งเดือน ในสมัยนั้นโปรแกรมต่างๆ ถูกแลกเปลี่ยนกันอย่างอิสระระหว่างบริษัทต่างๆ ดังนั้น Calcomp (จิม นิวแลนด์ และแคลวิน เฮฟเต) จึงมีสำเนาอยู่ เมื่อผมกลับไปที่สแตนฟอร์ดในฤดูใบไม้ร่วงปี 1962 ผมได้นำสำเนาไปไว้ในห้องสมุดศูนย์คอมพิวเตอร์ของสแตนฟอร์ด คำอธิบายของขั้นตอนการวาดเส้นได้รับการยอมรับให้เสนอในงาน ประชุมระดับชาติ ของ ACM ปี 1963 ที่เดนเวอร์ รัฐโคโลราโด ปีนั้นไม่มีการตีพิมพ์รายงานการประชุม มีเพียงวาระการประชุมและหัวข้อต่างๆ ในวารสาร Communications of the ACM เท่านั้น หลังจากที่ผมนำเสนอเสร็จแล้ว มีคนจาก IBM Systems Journal ถามผมว่าพวกเขาสามารถตีพิมพ์บทความได้หรือไม่ ผมยินดีตอบตกลง และพวกเขาก็ได้ตีพิมพ์ในปี 1965

จะใช้หลักเกณฑ์ต่อไปนี้:

• มุมบนซ้ายคือ (0,0) โดยที่พิกเซลพิกัดจะเพิ่มขึ้นในทิศทางขวาและลง (เช่น พิกเซลที่ (7,4) อยู่เหนือพิกเซลที่ (7,5) โดยตรง) และ
• จุดศูนย์กลางของพิกเซลมีพิกัดเป็นจำนวนเต็ม

จุดปลายของเส้นตรงคือพิกเซลที่และโดยที่พิกเซลแรกของคู่คือคอลัมน์ และพิกเซลที่สองคือแถว ${\displaystyle (x_{0},y_{0})}$${\displaystyle (x_{1},y_{1})}$

ในขั้นต้น อัลกอริทึมจะถูกนำเสนอเฉพาะสำหรับอ็อกแทนต์ที่ส่วนของเส้นตรงทอดลงและไปทางขวา ( และ) และการฉายภาพในแนวนอนยาวกว่าการฉายภาพในแนวตั้ง(เส้นตรงมีความชัน เป็นบวก น้อยกว่า 1) ในอ็อกแทนต์นี้ สำหรับแต่ละคอลัมน์xระหว่างและจะมีแถวy เพียงหนึ่งแถว (คำนวณโดยอัลกอริทึม) ที่มีพิกเซลของเส้นตรง ในขณะที่แต่ละแถวระหว่างและอาจมีพิกเซลที่ถูกแปลงเป็นภาพแรสเตอร์หลายพิกเซล ${\displaystyle x_{0}\leq x_{1}}$${\displaystyle y_{0}\leq y_{1}}$${\displaystyle x_{1}-x_{0}}$${\displaystyle y_{1}-y_{0}}$${\displaystyle x_{0}}$${\displaystyle x_{1}}$${\displaystyle y_{0}}$${\displaystyle y_{1}}$

อัลกอริทึมของเบรเซนแฮมจะเลือกจำนวนเต็มyที่สอดคล้องกับจุดศูนย์กลางของพิกเซล ซึ่งใกล้เคียงกับค่า yในอุดมคติ (เศษส่วน) มากที่สุดสำหรับค่าx เดียวกัน ในคอลัมน์ถัดไป ค่า yอาจคงที่หรือเพิ่มขึ้นทีละ 1 สมการทั่วไปของเส้นตรงที่ลากผ่านจุดปลายมีดังนี้:

${\displaystyle {\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}}}$.

เนื่องจากเรารู้ค่าคอลัมน์x แล้ว ค่าแถว yของพิกเซลจึงได้มาจากการปัดเศษค่านี้ให้เป็นจำนวนเต็มที่ใกล้ที่สุด:

${\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}}$.

ความชันขึ้นอยู่กับพิกัดจุดปลายเท่านั้นและสามารถคำนวณล่วงหน้าได้ และสามารถคำนวณ ค่า y ที่เหมาะสม สำหรับค่าx ที่เป็นจำนวนเต็มที่ต่อเนื่องกันได้ โดยเริ่มจาก ค่า y และเพิ่มค่าความชันซ้ำๆ ${\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})}$${\displaystyle y_{0}}$

ในทางปฏิบัติ อัลกอริทึมจะไม่ติดตามพิกัด y ซึ่งจะเพิ่มขึ้นm = ∆y/∆xทุกครั้งที่xเพิ่มขึ้นหนึ่งหน่วย แต่จะเก็บขอบเขตข้อผิดพลาดไว้ในแต่ละขั้นตอน ซึ่งแสดงถึงค่าลบของระยะทางจาก (a) จุดที่เส้นออกจากพิกเซลไปยัง (b) ขอบบนสุดของพิกเซล ค่านี้จะถูกกำหนดไว้ที่(เนื่องจากใช้พิกัดศูนย์กลางของพิกเซล) ก่อน และจะเพิ่มขึ้นmทุกครั้งที่ พิกัด xเพิ่มขึ้นหนึ่งหน่วย หากข้อผิดพลาดมากกว่า0.5เราจะรู้ว่าเส้นได้เคลื่อนขึ้นไปหนึ่งพิกเซล และเราต้องเพิ่ม พิกัด y ของเรา และปรับข้อผิดพลาดใหม่เพื่อแสดงระยะทางจากด้านบนของพิกเซลใหม่ ซึ่งทำได้โดยการลบหนึ่งออกจากข้อผิดพลาด^{[ 2 ]}${\displaystyle y_{0}-0.5}$

ในการสร้างอัลกอริทึมของเบรเซนแฮม ต้องดำเนินการสองขั้นตอน ขั้นตอนแรกคือการแปลงสมการเส้นตรงจากรูปแบบความชัน-จุดตัดแกน y ทั่วไป ให้เป็นสมการโดยปริยายที่มีสัมประสิทธิ์เป็นจำนวนเต็ม และขั้นตอนที่สองคือการใช้สมการใหม่นี้ในการวาดเส้นตรงโดยอาศัยแนวคิดเรื่องการสะสมของข้อผิดพลาด

รูปแบบสมการเส้นตรงแบบความชัน-จุดตัดแกน y เขียนได้ดังนี้

${\displaystyle y=f(x)=mx+b}$

โดยที่คือความชัน และคือจุดตัดแกน yเนื่องจากสมการนี้ขึ้นอยู่กับ เพียงอย่างเดียวจึงไม่สามารถแสดงเส้นตรงแนวตั้งได้ ดังนั้น การเขียนสมการนี้ให้เป็นฟังก์ชันของทั้งและจะช่วยให้สามารถวาดเส้นตรงที่ทำมุมใดๆ ก็ได้ มุม (หรือความชัน) ของเส้นตรงสามารถเขียนได้ว่า "ระยะเพิ่มขึ้นหารด้วยระยะวิ่ง" หรือจากนั้นใช้การจัดการทางพีชคณิต ${\displaystyle m}$${\displaystyle b}$${\displaystyle x}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \Delta y/\Delta x}$

${\displaystyle {\begin{aligned}y&=mx+b\\y&={\frac {\Delta y}{\Delta x}}x+b\\(\Delta x)y&=(\Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{aligned}}}$

ถ้าให้สมการสุดท้ายนี้เป็นฟังก์ชันของและก็สามารถเขียนได้ดังนี้ ${\displaystyle x}$${\displaystyle y}$

${\displaystyle f(x,y):=Ax+By+C=0}$

โดยที่ค่าคงที่คือ

• ${\displaystyle A=\เดลต้า y=y_{1}-y_{0}}$
• ${\displaystyle B=-\Delta x=-(x_{1}-x_{0})}$
• ${\displaystyle C=(\Delta x)b=(x_{1}-x_{0})b}$

เส้นตรงนั้นถูกกำหนดขึ้นสำหรับค่าคงที่, , และที่ใดก็ตามนั่นคือ สำหรับจุดใดๆที่ไม่ได้อยู่บนเส้นตรงนั้นรูปแบบนี้เกี่ยวข้องเฉพาะจำนวนเต็มก็ต่อเมื่อและเป็นจำนวนเต็มเท่านั้น เนื่องจากค่าคงที่, , และถูกกำหนดให้เป็นจำนวนเต็ม ${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle f(x,y)=0}$${\displaystyle (x,y)}$${\displaystyle f(x,y)\neq 0}$${\displaystyle x}$${\displaystyle y}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$

ตัวอย่างเช่น เส้นตรงนี้สามารถเขียนได้ดังนี้จุด (2,2) อยู่บนเส้นตรงนี้ ${\textstyle y={\frac {1}{2}}x+1}$${\displaystyle f(x,y)=x-2y+2}$

${\displaystyle f(2,2)=x-2y+2=(2)-2(2)+2=2-4+2=0}$

และจุด (2,3) ไม่อยู่บนเส้น

${\displaystyle f(2,3)=(2)-2(3)+2=2-6+2=-2}$

และไม่ใช่ประเด็นเช่นกัน (2,1)

${\displaystyle f(2,1)=(2)-2(1)+2=2-2+2=2}$

โปรดสังเกตว่าจุด (2,1) และ (2,3) อยู่คนละด้านของเส้นตรงและมีค่าเป็นบวกหรือลบ เส้นตรงแบ่งระนาบออกเป็นสองส่วนเท่าๆ กัน ครึ่งระนาบที่มีค่าเป็นลบเรียกว่าครึ่งระนาบลบ และอีกครึ่งระนาบเรียกว่าครึ่งระนาบบวก ข้อสังเกตนี้มีความสำคัญมากในการพิสูจน์ส่วนที่เหลือ ${\displaystyle f(x,y)}$${\displaystyle f(x,y)}$

จุดเริ่มต้นอยู่บนเส้น

${\displaystyle f(x_{0},y_{0})=0}$

เนื่องจากเส้นนั้นถูกกำหนดให้เริ่มต้นและสิ้นสุดที่พิกัดจำนวนเต็ม (ถึงแม้ว่าการต้องการวาดเส้นที่มีจุดปลายไม่ใช่จำนวนเต็มก็เป็นเรื่องที่สมเหตุสมผลเช่นกัน)

เมื่อพิจารณาว่าความชันมีค่าสูงสุดเพียงค่าเดียวปัญหาที่เกิดขึ้นคือจุดถัดไปควรอยู่ที่หรือโดยสัญชาตญาณแล้ว จุดถัดไปควรเลือกจากจุดที่อยู่ใกล้เส้นตรงที่ มากกว่าถ้าอยู่ใกล้จุดแรกมากกว่า ก็ให้รวมจุดแรกไว้บนเส้นตรง ถ้าอยู่ใกล้จุดหลังมากกว่า ก็ให้รวมจุดหลัง เพื่อตอบคำถามนี้ ให้ประเมินฟังก์ชันเส้นตรงที่จุดกึ่งกลางระหว่างสองจุดนี้: ${\displaystyle 1}$${\displaystyle (x_{0}+1,y_{0})}$${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle x_{0}+1}$

${\displaystyle f(x_{0}+1,y_{0}+{\tfrac {1}{2}})}$

ถ้าค่าของฟังก์ชันเส้นตรงนี้เป็นบวก แสดงว่าเส้นตรงในอุดมคติอยู่ต่ำกว่าจุดกึ่งกลางและอยู่ใกล้กับจุดที่ต้องการเลือกมากขึ้นกล่าวคือ ค่าพิกัด y ควรเพิ่มขึ้น ในทางกลับกัน ถ้าค่าของฟังก์ชันเส้นตรงเป็นบวก แสดงว่าเส้นตรงในอุดมคติผ่านหรืออยู่เหนือจุดกึ่งกลาง และค่าพิกัด y ควรคงที่ ซึ่งในกรณีนี้จะเลือกจุดนั้น ค่าของฟังก์ชันเส้นตรง ณ จุดกึ่งกลางนี้เป็นตัวกำหนดเพียงอย่างเดียวว่าควรเลือกจุดใด ${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle (x_{0}+1,y_{0})}$

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

อีกทางเลือกหนึ่งคือ สามารถใช้ผลต่างระหว่างจุดแทนการประเมินค่า f(x,y) ที่จุดกึ่งกลาง วิธีการทางเลือกนี้อนุญาตให้ใช้การคำนวณแบบจำนวนเต็มเท่านั้น ซึ่งโดยทั่วไปจะเร็วกว่าการใช้การคำนวณแบบจุดลอยตัวเพื่อหาที่มาของวิธีการอื่น ให้กำหนดผลต่างดังนี้:

${\displaystyle D_{i}=f(x_{i}+1,y_{i}+{\tfrac {1}{2}})-f(x_{0},y_{0})}$

สำหรับการตัดสินใจครั้งแรก สูตรนี้เทียบเท่ากับวิธีจุดกึ่งกลาง เนื่องจากณ จุดเริ่มต้น การลดรูปนิพจน์นี้จะได้ผลลัพธ์ดังนี้: ${\displaystyle f(x_{0},y_{0})=0}$

${\displaystyle {\begin{array}{rclcl}D_{0}&=&\left[A(x_{0}+1)+B\left(y_{0}+{\frac {1}{2}}\right)+C\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&\left[Ax_{0}+By_{0}+C+A+{\frac {1}{2}}B\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&A+{\frac {1}{2}}B=\Delta y-{\frac {1}{2}}\Delta x\end{array}}}$

เช่นเดียวกับวิธีจุดกึ่งกลาง ถ้าค่าเป็นบวก ให้เลือกมิฉะนั้นให้เลือก ${\displaystyle D_{0}}$${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle (x_{0}+1,y_{0})}$

หากเลือกตัวเลือกนี้ การเปลี่ยนแปลงในค่าจะเป็นดังนี้: ${\displaystyle (x_{0}+1,y_{0})}$${\displaystyle D_{i}}$

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {1}{2}})-f(x_{0}+1,y_{0}+{\tfrac {1}{2}})&=&A&=&\Delta y\\\end{array}}}$

หากเลือกตัวเลือกนี้ การเปลี่ยนแปลงในค่าจะเป็นดังนี้: ${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle D_{i}}$

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {3}{2}})-f(x_{0}+1,y_{0}+{\tfrac {1}{2}})&=&A+B&=&\Delta y-\Delta x\end{array}}}$

ถ้าค่า D ใหม่เป็นบวกจะเลือกค่านี้ มิฉะนั้นจะเลือกค่าอื่นการตัดสินใจนี้สามารถสรุปได้โดยการสะสมข้อผิดพลาดในแต่ละจุดถัดไป ${\displaystyle (x_{0}+2,y_{0}+1)}$${\displaystyle (x_{0}+2,y_{0})}$

การคำนวณหาที่มาของอัลกอริทึมทั้งหมดเสร็จสมบูรณ์แล้ว ปัญหาด้านประสิทธิภาพอย่างหนึ่งคือค่า 1/2 ในค่าเริ่มต้นของ D เนื่องจากทั้งหมดนี้เกี่ยวข้องกับเครื่องหมายของผลต่างสะสม ดังนั้นทุกอย่างจึงสามารถคูณด้วย 2 ได้โดยไม่มีผลกระทบใดๆ

ผลลัพธ์ที่ได้คืออัลกอริทึมที่ใช้เฉพาะการคำนวณเลขจำนวนเต็มเท่านั้น

plotLine(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 D = 2*dy - dx y = y0 สำหรับ x ตั้งแต่ x0 ถึง x1 plot(x, y) ถ้า D > 0 y = y + 1 D = D + (2 * (dy - dx)) อื่น D = D + 2*dy จบถ้า

เมื่อรันอัลกอริทึมนี้ตั้งแต่ (0,1) ถึง (6,4) จะได้ความแตกต่างดังต่อไปนี้ โดยที่ dx=6 และ dy=3: ${\displaystyle f(x,y)=x-2y+2}$

D=2*3-6=0 วนลูปจาก 0 ถึง 6 * x=0: plot(0, 1) , D≤0: D=0+6=6 * x=1: plot(1, 1) , D>0: D=6-12=-6, y=1+1=2, D=-6+6=0 * x=2: plot(2, 2) , D≤0: D=0+6=6 * x=3: plot(3, 2) , D>0: D=6-12=-6, y=2+1=3, D=-6+6=0 * x=4: plot(4, 3) , D≤0: D=0+6=6 * x=5: plot(5, 3) , D>0: D=6-12=-6, y=3+1=4, D=-6+6=0 * x=6: plot(6, 4) , D≤0: D=0+6=6 

ผลลัพธ์ของกราฟนี้แสดงอยู่ทางด้านขวา สามารถดูกราฟได้โดยการพล็อตที่จุดตัดของเส้น (วงกลมสีน้ำเงิน) หรือเติมสีลงในช่องพิกเซล (สี่เหลี่ยมสีเหลือง) ไม่ว่าจะวิธีใด ผลลัพธ์ของกราฟก็เหมือนกัน

อย่างไรก็ตาม ดังที่กล่าวไว้ข้างต้น วิธีนี้ใช้ได้เฉพาะกับ อ็อกแทนต์ ศูนย์เท่านั้น นั่นคือเส้นที่เริ่มต้นจากจุดกำเนิดโดยมีความชันระหว่าง 0 ถึง 1 โดยที่ x เพิ่มขึ้นทีละ 1 ในแต่ละรอบ และ y เพิ่มขึ้นทีละ 0 หรือ 1

สามารถขยายอัลกอริธึมนี้ให้ครอบคลุมค่าความชันระหว่าง 0 ถึง -1 ได้โดยการตรวจสอบว่าค่า y จำเป็นต้องเพิ่มขึ้นหรือลดลง (เช่น dy < 0)

plotLineLow(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 ยี่ = 1 ถ้า dy < 0 yi = -1 dy = -dy จบถ้า D = (2 * dy) - dx y = y0 สำหรับ x ตั้งแต่ x0 ถึง x1 plot(x, y) ถ้า D > 0 y = y + yi D = D + (2 * (dy - dx)) อื่น D = D + 2*dy จบถ้า

โดยการสลับแกน x และ y สามารถเขียนการใช้งานสำหรับความชันสูงบวกหรือลบได้ดังนี้

plotLineHigh(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 xi = 1 ถ้า dx < 0 xi = -1 dx = -dx จบถ้า D = (2 * dx) - dy x = x0 สำหรับ y ตั้งแต่ y0 ถึง y1 plot(x, y) ถ้า D > 0 x = x + xi D = D + (2 * (dx - dy)) อื่น D = D + 2*dx จบถ้า

วิธีแก้ปัญหาที่สมบูรณ์จะต้องตรวจสอบว่า x1 > x0 หรือ y1 > y0 หรือไม่ และกลับค่าพิกัดอินพุตก่อนที่จะวาด ดังนั้น

plotLine(x0, y0, x1, y1) if abs(y1 - y0) < abs(x1 - x0) if x0 > x1 plotLineLow(x1, y1, x0, y0) อื่น plotLineLow(x0, y0, x1, y1) จบเงื่อนไขมิเช่นนั้นถ้า y0 > y1 plotLineHigh(x1, y1, x0, y0) อื่น plotLineHigh(x0, y0, x1, y1) จบถ้าจบถ้า

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

บางเวอร์ชันใช้หลักการของ Bresenham เกี่ยวกับข้อผิดพลาดที่เพิ่มขึ้นเป็นจำนวนเต็มเพื่อดำเนินการวาดเส้นอ็อกแทนต์ทั้งหมด โดยปรับสมดุลข้อผิดพลาดบวกและลบระหว่างพิกัด x และ y ^{[ 3 ]}

plotLine(x0, y0, x1, y1) dx = abs(x1 - x0) sx = x0 < x1 ? 1 : -1 dy = -abs(y1 - y0) sy = y0 < y1 ? 1 : -1 ข้อผิดพลาด = dx + dy ในขณะที่เป็นความจริง plot(x0, y0) e2 = 2 * ข้อผิดพลาด ถ้า e2 >= dy ถ้า x0 == x1 ให้หยุด ข้อผิดพลาด = ข้อผิดพลาด + dy x0 = x0 + sx จบเงื่อนไข ถ้าe2 <= dx ถ้า y0 == y1 หยุด ข้อผิดพลาด = ข้อผิดพลาด + dx y0 = y0 + sy จบถ้าจบในขณะที่

อัลกอริทึมของเบรเซนแฮมสามารถตีความได้ว่าเป็นตัววิเคราะห์ความแตกต่างแบบดิจิทัลที่ ได้รับการดัดแปลงเล็กน้อย (โดยใช้ค่าเกณฑ์ความคลาดเคลื่อน 0.5 แทนที่จะเป็น 0 ซึ่งจำเป็นสำหรับการสร้างภาพแรสเตอร์ของรูปหลายเหลี่ยมที่ไม่ทับซ้อนกัน)

หลักการของการใช้ข้อผิดพลาดที่เพิ่มขึ้นแทนการดำเนินการหารมีแอปพลิเคชันอื่น ๆ ในด้านกราฟิก สามารถใช้เทคนิคนี้ในการคำนวณพิกัด U,Vระหว่างการสแกนแรสเตอร์ของรูปหลายเหลี่ยมที่แมปพื้นผิว^{[ 4 ]}เอ็น จิ้นการเรนเดอร์ซอฟต์แวร์แผนที่ ความสูงแบบว็อกเซล ที่พบในเกมพีซีบางเกมก็ใช้หลักการนี้เช่นกัน

Bresenham ยังได้เผยแพร่อัลกอริธึมการคำนวณ Run-Slice ด้วย: ในขณะที่อัลกอริธึม Run-Length ที่อธิบายไว้ข้างต้นจะวนลูปบนแกนหลัก รูปแบบ Run-Slice จะวนลูปในทิศทางตรงกันข้าม^{[ 5 ]} วิธีนี้ได้รับการนำเสนอในสิทธิบัตรของสหรัฐอเมริกาหลายฉบับ:

• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5815163 "วิธีการและอุปกรณ์สำหรับวาดเส้นแบ่งส่วนระหว่างการคำนวณ" 
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5740345 "วิธีการและอุปกรณ์สำหรับแสดงข้อมูลกราฟิกคอมพิวเตอร์ที่จัดเก็บในรูปแบบบีบอัดด้วยระบบจัดทำดัชนีสีที่มีประสิทธิภาพ" 
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5657435 "เครื่องมือวาดเส้นแบ่งส่วนแบบรันที่มีความสามารถในการปรับขนาดแบบไม่เชิงเส้น" 
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5627957 "เครื่องมือวาดเส้นแบ่งส่วนแบบรันที่มีความสามารถในการประมวลผลขั้นสูง" 
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5627956 "โปรแกรมวาดเส้นแบ่งส่วนแบบใช้การยืดขยาย" 
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5617524 "โปรแกรมวาดเส้นแบ่งส่วนพร้อมความสามารถในการแรเงา" 
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5611029 "เครื่องมือวาดเส้นแบ่งส่วนแบบรันที่มีความสามารถในการแรเงาแบบไม่เชิงเส้น" 
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5604852 "วิธีการและอุปกรณ์สำหรับแสดงเส้นโค้งพาราเมตริกบนจอแสดงผลวิดีโอ" 
• สิทธิบัตรสหรัฐอเมริกาหมายเลข 5600769 "ใช้งานเครื่องมือวาดเส้นแบ่งส่วนด้วยเทคนิคการตัดที่ได้รับการปรับปรุง" 

อัลกอริทึมได้รับการขยายเพิ่มเติมเป็น:

• วาดเส้นที่มีความหนาตามอำเภอใจ ซึ่งเป็นอัลกอริทึมที่สร้างโดย Alan Murphy ที่ IBM ^{[ 6 ]}
• วาดเส้นโค้งหลายประเภท (วงกลม วงรี ลูกบาศก์ กำลังสอง และ เส้นโค้งเบซิเยร์เชิงตรรกะ) และเส้นและเส้นโค้งแบบแอนตี้เอเลียส ชุดอัลกอริธึมโดย Alois Zingl ^{[ 3 ]}

• ตัววิเคราะห์เชิงอนุพันธ์ดิจิทัล (อัลกอริทึมกราฟิก)วิธีการที่เรียบง่ายและทั่วไปสำหรับการแปลงเส้นและสามเหลี่ยมให้เป็นภาพแรสเตอร์
• อัลกอริทึมการวาดเส้นของ Xiaolin Wuเป็นวิธีการวาดเส้นที่รวดเร็วและมีการลดรอยหยัก (antialiasing) เช่นเดียวกัน
• อัลกอริทึมจุดกึ่งกลางวงกลมซึ่งเป็นอัลกอริทึมที่คล้ายกับอัลกอริทึมสำหรับการวาดวงกลม

• วิทยานิพนธ์ของแพทริค-กิลเลสบันดาประกอบด้วยส่วนขยายของอัลกอริทึมการวาดเส้นของเบรเซนแฮมเพื่อทำการลบเส้นที่ซ่อนอยู่แบบ 3 มิติ
  • ตีพิมพ์ในรายงานการประชุม MICAD '87 เรื่อง CAD/CAM และกราฟิกคอมพิวเตอร์ หน้า 591 - ISBN 2-86601-084-1.
• การเพิ่มความหนาของเส้นโดยการดัดแปลงอัลกอริทึมของ Bresenham โดย AS Murphy, IBM Technical Disclosure Bulletin, Vol. 20, No. 12, พฤษภาคม 1978
• Bresenham, Jack (กุมภาพันธ์ 1977). "อัลกอริทึมเชิงเส้นสำหรับการแสดงผลดิจิทัลแบบเพิ่มทีละขั้นของส่วนโค้งวงกลม". Communications of the ACM . 20 (2): 100– 106. doi : 10.1145/359423.359432 .– รวมถึงรายงานทางเทคนิค 1964 27 ม.ค. -11- อัลกอริทึมวงกลม TR-02-286 ห้องปฏิบัติการ IBM ซานโฮเซ

วิกิมีเดียคอมมอนส์มีสื่อเกี่ยวกับอัลกอริธึมเบรเซนแฮม

• หนังสือ Graphics Programming Black Book ฉบับพิเศษของ Michael Abrash: บทที่ 35: Bresenham เร็ว และเร็วคือสิ่งที่ดี
• อัลกอริทึมการวาดเส้นแบบเบรเซนแฮมโดย โคลิน แฟลนาแกน
• หน้าเว็บของสถาบันมาตรฐานและเทคโนโลยีแห่งชาติเกี่ยวกับอัลกอริทึมของเบรเซนแฮม
• ข้อมูลเกี่ยวกับเครื่องพิมพ์พล็อตเตอร์แบบเพิ่มทีละขั้น Calcomp 563
• อัลกอริทึม Bresenham ในภาษาโปรแกรมหลายภาษา
• ความงดงามของอัลกอริทึมของเบรเซนแฮม — การใช้งานอย่างง่ายเพื่อวาดเส้นตรง วงกลม วงรี และเส้นโค้งเบซิเยร์