يتم استخدام هذه الخوارزمية لمسح تحويل الخط. تم تطويره بواسطة بريسنهام. إنها طريقة فعالة لأنها تتضمن فقط عمليات الجمع والطرح والضرب للأعداد الصحيحة. يمكن تنفيذ هذه العمليات بسرعة كبيرة بحيث يمكن إنشاء الخطوط بسرعة.

في هذه الطريقة، البكسل التالي المحدد هو البكسل الذي لديه أقل مسافة من الخط الحقيقي.

الطريقة تعمل كالتالي:

افترض بكسل P₁'(خ₁'،و₁')، ثم حدد وحدات البكسل اللاحقة أثناء عملنا حتى الليل، موضع بكسل واحد في كل مرة في الاتجاه الأفقي نحو P₂'(خ₂'،و₂').

بمجرد اختيار بكسل في أي خطوة

قم بإيقاف تشغيل وضع المطور

البكسل التالي هو

1. إما الذي على يمينه (الحد الأدنى للخط)
2. واحد أعلى يمينه وأعلى (الحد العلوي للخط)

يتم تقريب الخط بشكل أفضل بواسطة وحدات البكسل التي تقع على أقل مسافة من المسار بين P₁'، ص₂'.

لاختيار البيكسل التالي بين البكسل السفلي S والبكسل العلوي T.
إذا تم اختيار S
لدينا س_أنا+1=س_أنا+1 و ص_أنا+1=y_أنا
إذا تم اختيار T
لدينا س_أنا+1=س_أنا+1 و ص_أنا+1=y_أنا+1

إحداثيات y الفعلية للخط عند x = x_أنا+1يكون
ص=مكس_أنا+1+ب

المسافة من S إلى الخط الفعلي في اتجاه y
ق = ص-ص_أنا

المسافة من T إلى الخط الفعلي في اتجاه y
ر = (ص_أنا+1)-ص

الآن فكر في الفرق بين قيمتي المسافة هاتين
شارع

عندما (ق-ر)<0 ⟹ s < t< p>

أقرب بكسل هو S

عندما (s-t) ≧0 ⟹ ث

أقرب بكسل هو T

هذا الفرق
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

استبدال م ب وإدخال متغير القرار
د_أنا=△x (s-t)
د_أنا=△س (2 (x_أنا+1)+2b-2y_أنا-1)
=2△xy_أنا-2△y-1△x.2b-2y_أنا△س-△س
د_أنا=2△y.x_أنا-2△x.y_أنا+ج

حيث ج= 2△ص+△س (2ب-1)

يمكننا كتابة متغير القرار د_أنا+1للانزلاق التالي
د_أنا+1=2△y.x_أنا+1-2△x.y_أنا+1+ج
د_أنا+1-د_أنا=2△ص.(س_أنا+1-x_أنا)- 2△x(ص_أنا+1-و_أنا)

بما أن x_(i+1)=x_أنا+1، لدينا
د_أنا+1+د_أنا=2△ص.(س_أنا+1-س_أنا)- 2△x(ص_أنا+1-و_أنا)

حالات خاصة

إذا كان البكسل المختار في أعلى البكسل T (أي d_أنا≧0)⟹ و_أنا+1=y_أنا+1
د_أنا+1=د_أنا+2△ص-2△س

إذا كان البكسل المختار موجودًا في البكسل السفلي T (أي d_أنا<0)⟹ y_{أنا+1=صأنا
دأنا+1=دأنا+2△ص}

وأخيراً نحسب د₁
د₁=△س[2م(س₁+1)+2b-2y₁-1]
د₁=△س[2(مكس₁+ب-ذ₁)+2m-1]

منذ م₁+ب-ذ_أنا=0 و م = ، لدينا
د₁=2△ص-△س

ميزة:

1. إنها تتضمن فقط العمليات الحسابية الصحيحة، لذا فهي بسيطة.

2. يتجنب توليد النقاط المكررة.

3. يمكن تنفيذها باستخدام الأجهزة لأنها لا تستخدم الضرب والقسمة.

4. إنه أسرع بالمقارنة مع DDA (المحلل التفاضلي الرقمي) لأنه لا يتضمن حسابات الفاصلة العائمة مثل خوارزمية DDA.

العيب:

1. هذه الخوارزمية مخصصة لرسم الخطوط الأساسية فقط. التهيئة ليست جزءًا من خوارزمية خط بريسنهام. لذا، لرسم خطوط ناعمة، يجب أن تبحث في خوارزمية مختلفة.

خوارزمية خط بريسنهام:

الخطوة 1: بدء الخوارزمية

الخطوة 2: أعلن المتغير x₁،x₂،و₁،و₂، د، ط₁،أنا₂،دكس،دي

الخطوه 3: أدخل قيمة x₁،و₁،x₂،و₂
حيث س₁،و₁هي إحداثيات نقطة البداية
وx₂،و₂هي إحداثيات نقطة النهاية

الخطوة 4: احسب دكس = س₂-x₁
احسب دى = ص₂-و₁
احسب ط₁=2*أنت
احسب ط₂=2*(دي-دكس)
احسب د=ط₁-dx

الخطوة 5: اعتبر (x، y) كنقطة بداية وx_نهايةأقصى قيمة ممكنة لـ x.
إذا دي إكس<0
ثم س = س₂
ص = ص₂
س_نهاية=س₁
إذا كان dx> 0
ثم س = س₁
ص = ص₁
س_نهاية=س₂

الخطوة 6: إنشاء نقطة عند الإحداثيات (x,y).

الخطوة 7: تحقق مما إذا تم إنشاء الخط بأكمله.
إذا س > = س_نهاية
قف.

الخطوة 8: حساب إحداثيات البكسل التالي
إذا د<0
ثم د = د + ط₁
إذا د ≧ 0
ثم د = د + ط₂
زيادة ص = ص + 1

الخطوة 9: الزيادة س = س + 1

الخطوة 10: ارسم نقطة بأحدث الإحداثيات (x، y).

الخطوة 11: انتقل إلى الخطوة 7

جافا العودية

الخطوة 12: نهاية الخوارزمية

مثال: موضع البداية والنهاية للخط هو (1، 1) و (8، 5). البحث عن نقاط وسيطة.

حل: س₁=1
و₁=1
س₂=8
و₂=5
دكس = س₂-x₁=8-1=7
أنت=ص₂-و₁=5-1=4
أنا₁=2* ∆ص=2*4=8
أنا₂=2*(∆y-∆x)=2*(4-7)=-6
د = أنا₁-∆س=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 وخوارزمية خط بريسنهام: