אלגוריתם זה משמש לסריקה להמרת קו. זה פותח על ידי Bresenham. זוהי שיטה יעילה מכיוון שהיא כוללת רק פעולות חיבור, חיסורים וכפל שלמים. פעולות אלו יכולות להתבצע במהירות רבה כך שניתן ליצור קווים במהירות.

בשיטה זו, הפיקסל הבא שנבחר הוא זה שיש לו את המרחק הקטן ביותר מהקו האמיתי.

השיטה פועלת באופן הבא:

נניח פיקסל P ₁ '(איקס ₁ ',ו ₁ '), ולאחר מכן בחר פיקסלים עוקבים תוך כדי עבודה עד הלילה, מיקום פיקסל אחד בכל פעם בכיוון האופקי לכיוון P ₂ '(איקס ₂ ',ו ₂ ').

פעם אחת פיקסל בבחירה בכל שלב

הפיקסל הבא הוא

1. או זה שמימין לו (גבול תחתון לקו)
2. אחד למעלה מימין ומעלה (גבול עליון לקו)

הקו מוערך בצורה הטובה ביותר לפי אותם פיקסלים הנופלים במרחק הקטן ביותר מהנתיב בין P ₁ ',פ ₂ '.

כדי לבחור את הבא בין הפיקסל התחתון S לפיקסל העליון T.
אם נבחר S
יש לנו x _i+1 =x _אני +1 ו-y _i+1 =y _אני
אם נבחר T
יש לנו x _i+1 =x _אני +1 ו-y _i+1 =y _אני +1

קואורדינטות ה-y בפועל של הישר ב-x = x _i+1 הוא
y=mx _i+1 +ב

המרחק מ-S לקו האמיתי בכיוון y
s = y-y _אני

המרחק מ-T לקו האמיתי בכיוון y
t = (י _אני +1)-y

כעת שקול את ההבדל בין 2 ערכי המרחק הללו
רחוב

מתי (s-t) <0 ⟹ s < t < p>

הפיקסל הקרוב ביותר הוא S

כאשר (s-t) ≧0 ⟹ s

הפיקסל הקרוב ביותר הוא T

ההבדל הזה הוא
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

מחליף מ על ידי והכנסת משתנה החלטה
ד _אני =△x (s-t)
ד _אני =△x (2 (איקס _אני +1)+2b-2y _אני -1)
=2△xy _אני -2△y-1△x.2b-2y _אני △x-△x
ד _אני =2△y.x _אני -2△x.y _אני +c

כאשר c= 2△y+△x (2b-1)

נוכל לכתוב את משתנה ההחלטה ד _i+1 להחלקה הבאה
ד _i+1 =2△y.x _i+1 -2△x.y _i+1 +c
ד _i+1 -ד _אני =2△y.(x _i+1 -איקס _אני )- 2△x(y _i+1 -ו _אני )

מאז x_(i+1)=x _אני +1, יש לנו
ד _i+1 +d _אני =2△y.(x _אני +1-x _אני )- 2△x(y _i+1 -ו _אני )

מקרים מיוחדים

אם הפיקסל שנבחר נמצא בפיקסל העליון T (כלומר, ד _אני ≧0)⟹ ו _i+1 =y _אני +1
ד _i+1 =ד _אני +2△y-2△x

אם הפיקסל שנבחר נמצא בפיקסל התחתון T (כלומר, ד _אני <0)⟹ y _{i+1=y אני
ד i+1 =ד אני +2△y}

לבסוף, אנו מחשבים את ד ₁
ד ₁ =△x[2m(x ₁ +1)+2b-2y ₁ -1]
ד ₁ =△x[2(mx ₁ +b-y ₁ )+2m-1]

מאז mx ₁ +b-y _אני =0 ו-m = , יש לנו
ד ₁ =2△y-△x

יתרון:

1. זה כולל רק אריתמטיקה של מספרים שלמים, אז זה פשוט.

2. זה מונע יצירת נקודות כפולות.

3. ניתן ליישם אותו באמצעות חומרה כי הוא אינו משתמש בכפל וחילוק.

4. זה מהיר יותר בהשוואה ל-DDA (Digital Differential Analyzer) מכיוון שהוא לא כולל חישובי נקודה צפה כמו אלגוריתם DDA.

חִסָרוֹן:

1. אלגוריתם זה מיועד לשרטוט קווים בסיסי בלבד האתחול אינו חלק מאלגוריתם הקו של ברסנהאם. אז כדי לצייר קווים חלקים, כדאי שתרצה לבדוק אלגוריתם אחר.

אלגוריתם הקו של ברסנהאם:

שלב 1: התחל אלגוריתם

שלב 2: הכרזה על משתנה x ₁ ,איקס ₂ ,ו ₁ ,ו ₂ ,ד,י ₁ ,אני ₂ ,dx,dy

שלב 3: הזן את הערך של x ₁ ,ו ₁ ,איקס ₂ ,ו ₂
איפה x ₁ ,ו ₁ הן קואורדינטות של נקודת ההתחלה
וגם x ₂ ,ו ₂ הן קואורדינטות של נקודת הסיום

שלב 4: חשב את dx = x ₂ -איקס ₁
חשב dy = y ₂ -ו ₁
חשב את i ₁ =2*אתה
חשב את i ₂ =2*(dy-dx)
חשב את d=i ₁ -dx

שלב 5: שקול (x, y) כנקודת התחלה ו-x _סוֹף כערך מקסימלי אפשרי של x.
אם dx <0
ואז x = x ₂
y = y ₂
איקס _סוֹף =x ₁
אם dx > 0
ואז x = x ₁
y = y ₁
איקס _סוֹף =x ₂

שלב 6: צור נקודה בקואורדינטות (x,y).

שלב 7: בדוק אם הקו שלם נוצר.
אם x > = x _סוֹף
תפסיק.

שלב 8: חשב את הקואורדינטות של הפיקסל הבא
אם ד <0
ואז d = d + i ₁
אם d ≧ 0
ואז d = d + i ₂
הגדל את y = y + 1

שלב 9: הגדל את x = x + 1

שלב 10: צייר נקודה עם הקואורדינטות האחרונות (x, y).

שלב 11: עבור לשלב 7

שלב 12: סוף האלגוריתם

דוגמא: מיקום ההתחלה והסיום של הקו הם (1, 1) ו- (8, 5). מצא נקודות ביניים.

פִּתָרוֹן: איקס ₁ =1
ו ₁ =1
איקס ₂ =8
ו ₂ =5
dx= x ₂ -איקס ₁ =8-1=7
אתה=י ₂ -ו ₁ =5-1=4
אני ₁ =2* ∆y=2*4=8
אני ₂ =2*(∆y-∆x)=2*(4-7)=-6
ד = אני ₁ -∆x=8-7=1

תוכנית ליישום אלגוריתם ציור קווים של ברסנהאם:

 #include #include void drawline(int x0, int y0, int x1, int y1) { int dx, dy, p, x, y; dx=x1-x0; dy=y1-y0; x=x0; y=y0; p=2*dy-dx; while(x=0) { putpixel(x,y,7); y=y+1; p=p+2*dy-2*dx; } else { putpixel(x,y,7); p=p+2*dy;} x=x+1; } } int main() { int gdriver=DETECT, gmode, error, x0, y0, x1, y1; initgraph(&gdriver, &gmode, 'c:\turboc3\bgi'); printf('Enter co-ordinates of first point: '); scanf('%d%d', &x0, &y0); printf('Enter co-ordinates of second point: '); scanf('%d%d', &x1, &y1); drawline(x0, y0, x1, y1); return 0; }  

תְפוּקָה:

הבדיל בין אלגוריתם DDA לבין אלגוריתם הקו של Bresenham: