خوارزمية بريزنهام لرسم مستقيم

خوارزمية بريزنهام لرسم مستقيم هي خوارزمية تحدد أي النقاط في الفضاء من البعد n يجب أن يرسم من أجل الحصول على تقريب مناسب للخط المستقيم بين نقطتين معرفتين.^[1] تعتبر واحدة من خوارزميات رسم المستقيم التي تستخدم هذه الخوارزمية عادة في الرسم على شاشة الحاسب، وذلك لأنها تعتمد على عمليات لا تستهلك الكثير من قدرات الحاسب، كجمع الأعداد الصحيحة، وطرحها وعمليات نقل البتات. وتعتبر هذه الخوارزمية واحدة من أوائل الخوارزميات التي تم تطويرها في الرسوميات الحاسوبية.

تاريخ

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

الخوارزمية

رسم توضيحي لنتيجة خوارزمية بريزنهام

سيستخدم افتراض أن قيمة إحداثيات النقاط تزداد بالاتجاه نحو الأسفل واليمين، وسوف يستخدم الإحداثيات الصحيحة لهذه النقاط. نعرف إحداثيات نقطتي المستقيم على الشكل (x₀, y₀) و(x₁, y₁) حيث الإحداثية الأولى من الثنائية تمثل الأعمدة والثانية تمثل الصفوف.

سوف تعرف الخوارزمية بالبداية من أجل ثمانية يكون فيها قطعة الخط المستقيم تتجه باتجاه الأسفل واليمين (x₀≤x₁ and y₀≤y₁)، ويكون مسقطها الأفقي ${\displaystyle x_{1}-x_{0}}$ أطول من مسقطها العمودي ${\displaystyle y_{1}-y_{0}}$ (أو أن ميل المستقيم يكون أقل من 1 وأكبر من 0). في هذه الثمانية فإنه من أجل أي عمود x بين ${\displaystyle x_{0}}$ و${\displaystyle x_{1}}$، يوجد عمود وحيد y (يتم حسابه من قبل الخوارزمية) يحتوي النقطة الواقعة على المستقيم، بينما كل صف بين ${\displaystyle y_{0}}$ و${\displaystyle y_{1}}$ ربما يحتوي على بضعة نقاط مرسومة.

تختار الخوارزمية قيمة y الصحيحة المقابلة لمركز النقطة الأقل إلى أقرب كسر y من أجل قيمة مساوية ل x، وبهذا وعند العمود التالي من الممكن لقيمة y أن تبقى على حالها أو أن تزيد بمقدار 1. وتكون المعادلة العامة للمستقيم بدلالة نقطتي النهاية معطاة بالعلاقة:

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

وعلى اعتبار أننا نعرف العمود x يعطى صف النقطة y بتدوير الكمية التالية إلى أقرب عدد صحيح:

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

يعتمد الميل ${\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})}$ على إحدثيات نقاط النهاية فقط ومن الممكن إعادة حسابه بشكل مسبق، والقيم المثالية ل y بشكل تتابع من الممكن حسابها بالبدء عند ${\displaystyle y_{0}}$ وإضافة الميل بشكل متكرر.

في الكود البرمجي التالي، يقوم التابع plot(x,y) برسم النقاط وتعطي abs القيمة المطلقة:

انظر أيضاً

• خوارزمية رسم مستقيم

مراجع

موسوعات ذات صلة :

• موسوعة صور رقمية
• موسوعة خوارزميات
• موسوعة رياضيات
• موسوعة علم الحاسوب