خوارزمية بريزنهام: ارسم خطا على شبكة بكسلات

خوارزمية بريزنهام ترسم تقريبًا لخط مستقيم بالبكسلات عبر التقدم في الاتجاه الأطول وتجميع أثر الميل. [1]

سنرسم القطعة من (1,1) إلى (10,5) على شبكة نعد مراكز خلاياها نقاطًا صحيحة الإحداثيات. لن نقيس سرعة مكتبة رسوم، ولن نختبر شاشة فعلية؛ سنختار المراكز ونحسب موضع كل قرار، ثم نراجع النتائج بطريقة عددية مستقلة.

الخلاصة السريعة

• في مثالنا يزيد x تسع وحدات ويزيد y أربعًا؛ نحصل على عشرة مراكز لأن الطرفين محسوبان.
• قيمة القرار تبدأ عند −1: أول انتقال أفقي، ثم يتغير القرار إلى 7 فتكون الخطوة التالية قطرية.
• القيمة صفر تحتاج اتفاقًا معلنًا؛ برنامجنا يزيد الإحداثي الثانوي عند التعادل.
• فحصنا 2401 زوج من النهايات الصحيحة، بما فيها النقطة الواحدة والخطوط الرأسية والمائلة والسالبة.
• تطابقت النواتج مع استيفاء كسري مستقل، ونجح اختبار عكس اتجاه القراءة في النسخة التي رتبنا نهاياتها داخليًا.

حدد ما تعنيه الخانة قبل رسمها

المربع الصغير في الشكل يمثل خلية مركزها عند تقاطع إحداثيين صحيحين. نزيد x يمينًا وy إلى الأعلى في هذا المثال. لذلك تنتمي النقطة (3,2) إلى مركز الخلية ذات هذين الرقمين، لا إلى زاويتها. هذا اتفاق الرسم الذي سنفحصه؛ لا نخلط معه اتفاق صورة يبدأ صفها صفر من أعلى.

ارسم على ورق مربعات نقطتي البداية والنهاية، ثم صلهما بمسطرة. عند العمود x=2، يقع الخط عند y=1+4/9؛ أقرب مركز رأسي له هو y=1. وعند x=3 يصبح y=1+8/9، فيكون المركز y=2 أقرب. المطلوب اختيار الصف في كل عمود، لا تقريب الميل نفسه إلى عدد صحيح.

حوّل الاختيار إلى قرار متراكم

للحالة 0≤dy≤dx نبدأ القرار D=2dy−dx. إن كان سالبًا نزيد x فقط ثم نضيف 2dy إلى D؛ وإلا نزيد y أيضًا ونضيف 2dy−2dx. الكود أدناه ينفذ هذه الحالة مع إدراج الطرفين. [2]

def line(dx, dy):
    if not (type(dx) is int and type(dy) is int
            and 0 <= dy <= dx):
        raise ValueError("need 0 <= dy <= dx")
    y, D = 0, 2*dy-dx
    points = []
    for x in range(dx+1):
        points.append((x, y))
        if x == dx:
            break
        if D >= 0:
            y += 1
            D -= 2*dx
        D += 2*dy
    return points

الكود يعمل أولًا حول الأصل؛ استدعاء line(9,4) ينتج إزاحات نضيف إليها (1,1) للحصول على شكلنا. كلمة «قرار» أدق من وصف D بأنه مسافة بالبكسل؛ قيمته −1 هنا ناتجة من ضرب فروق الإحداثيات، بينما الانحراف الرأسي الفعلي عند العمود التالي هو كسر من وحدة.

راجع الأرقام عند كل انتقال

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

لنتحقق من صفين يدويًا: من −1 نضيف 8 فنحصل على 7، دون زيادة y. ومن 7 نضيف 8−18=−10 فنحصل على −3، مع زيادة y. القفز إلى 15 بدل −3 يعني أنك نسيت طرح 18 في الفرع القطري، ويغيّر مواضع المراكز التالية.

اختبر التعادل بدل إخفائه في الرسم

اخترنا مثالًا ثانيًا من (0,0) إلى (6,3). عند x=1 يمر الخط عند y=0.5، فيبتعد المركزان y=0 وy=1 المقدار نفسه. شرط D≥0 يختار الأعلى في هذا الاتجاه؛ أما استبداله بشرط D>0 فيختار الأسفل في مواضع التعادل.

أعطى الاتفاق الأول قيم y: 0,1,1,2,2,3,3، والثاني 0,0,1,1,2,2,3. الاختلاف لا تثبته نظرة إلى نعومة الخط؛ نحتاج قاعدة القرار. لهذا لا نختبر برنامجنا بمقارنة صورة واحدة فقط، ولا نفترض أن نسختين تختاران البكسلات نفسها إذا لم تتفقا على معالجة الصفر.

وسّع الاتجاهات مع حفظ اتفاقك

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

في نسختنا العامة نختار المحور ذا الفرق المطلق الأكبر؛ ونختار x عند تساوي الفرقين. نرتب الطرفين داخليًا بحيث يزداد هذا المحور، ونطبق النواة على الفروق المطلقة، ثم نعيد إشارة المحور الثاني. وإذا عكسنا ترتيب الطرفين في البداية، نعكس قائمة النواتج في النهاية. هذا الترتيب يثبت اتفاق التعادل عند إعادة قراءة القطعة من الطرف الآخر.

اختبرنا قطعة أشد ميلًا من (2,1) إلى (5,9). فرق y يساوي 8 وفرق x يساوي 3، فتنتج تسعة مراكز. بدايتها (2,1),(2,2),(3,3)، ونهايتها (4,7),(5,8),(5,9). زيادة x في كل خطوة هنا كانت ستجعلنا نحاول تطبيق نواة المجال الخاطئ.

قارن بمسار حساب مستقل

أخذنا جميع النهايات الصحيحة داخل المربع من −3 إلى 3 على كل محور: 49 نقطة و2401 زوج مرتب. المرجع المستقل لا يحدث D؛ بل يحسب الموضع الكسري الدقيق عند كل خطوة على المحور الأكبر ثم يقرب مقدار الإزاحة، مع دفع التعادل إلى الوحدة التالية. استعملنا كسورًا صحيحة البسط والمقام كي لا يغير تقريب عشري قرار نصف الوحدة.

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

اختيار مراكز قريبة لا يساوي حصر كل الخلايا التي تقطعها القطعة؛ يشير NIST إلى خوارزمية تغطية أوسع لهذا الغرض. [1]

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

المصادر

1. NIST — Bresenham’s algorithm
2. Bresenham — Algorithm for computer control of a digital plotter (1965)

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