אלגוריתם זה משמש לסריקה להמרת קו. זה פותח על ידי 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:

תור עדיפות