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

يُكتب معادلة الخط المستقيم بصيغة الميل والمقطع كما يلي:

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

أين${\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{محاذاة}}}$

بجعل هذه المعادلة الأخيرة دالة لـ${\displaystyle x}$و${\displaystyle y}$، ويمكن كتابتها على النحو التالي

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

حيث الثوابت هي

• ${\displaystyle A=\Delta 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}$يتم تعريفها على أنها أعداد صحيحة.

على سبيل المثال، السطر${\textstyle y={\frac {1}{2}}x+1}$ويمكن كتابة ذلك على النحو التالي${\displaystyle f(x,y)=x-2y+2}$النقطة (2،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}})}$

إذا كانت قيمة هذا موجبة، فإن الخط المثالي يقع أسفل نقطة المنتصف وأقرب إلى النقطة المرشحة.${\displaystyle (x_{0}+1,y_{0}+1)}$أي أن الإحداثي y يجب أن يزداد. وإلا، فإن الخط المثالي يمر عبر نقطة المنتصف أو فوقها، ويجب أن يبقى الإحداثي y كما هو؛ وفي هذه الحالة تكون النقطة${\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 ص = ص + 1 D = D + (2 * (dy - dx)) آخر D = D + 2*dy نهاية الشرط

تشغيل هذه الخوارزمية لـ${\displaystyle f(x,y)=x-2y+2}$ينتج عن الانتقال من (0,1) إلى (6,4) الفروق التالية مع dx=6 و dy=3:

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 yi = 1 إذا كانت قيمة dy أقل من 0 yi = -1 dy = -dy نهاية الشرط D = (2 * dy) - dx y = y0 لكل قيمة x من x0 إلى x1 plot(x, y) إذا كانت D > 0 ص = ص + صي D = D + (2 * (dy - dx)) آخر D = D + 2*dy نهاية الشرط

عن طريق تبديل المحورين السيني والصادي، يمكن كتابة تطبيق للمنحدرات الحادة الموجبة أو السالبة على النحو التالي

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 وعكس إحداثيات الإدخال قبل الرسم، وبالتالي

ارسم الخط (x0، y0، x1، y1) إذا كانت القيمة المطلقة لـ (y1 - y0) أقل من القيمة المطلقة لـ (x1 - x0) إذا كانت x0 أكبر من x1 plotLineLow(x1, y1, x0, y0) آخر plotLineLow(x0, y0, x1, y1) نهاية الشرط، وإلا إذا كان y0 > y1 plotLineHigh(x1, y1, x0, y0) آخر plotLineHigh(x0, y0, x1, y1) نهاية الشرط نهاية الشرط

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

تستخدم بعض الإصدارات مبادئ بريسنهام للخطأ التزايدي الصحيح لإجراء جميع عمليات رسم الخطوط الثمانية، مع موازنة الخطأ الموجب والسالب بين إحداثيات 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 نهاية الشرط نهاية الحلقة