منحنى هيلبرت: رقّم خلايا الشبكة وافحص اتصال المسار

يمر التقريب الشبكي لمنحنى هيلبرت بمركز كل خلية مرة واحدة، على شبكة طول ضلعها قوة للعدد 2. [1] سنبني ترتيبًا صغيرًا ونفحص معنيين مختلفين للقرب: قرب الخطوة التالية، وقرب رقمي خليتين متجاورتين.

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

• في نموذجنا ذي الرتبة 2 توجد 16 خلية و15 وصلة، من (0,0) إلى (3,0).
• كل خطوة في القائمة تغيّر إحداثيًا واحدًا بمقدار وحدة؛ لا توجد قفزة قطرية.
• الخليتان (1,0) و(2,0) متجاورتان، لكن رقمي زيارتهما 1 و14.
• تقسيم القائمة إلى كتل من أربع زيارات يعيد المربعات الأربعة المرسومة.
• اختبرنا الرتب من صفر إلى سبع: 21845 نقطة و29124 كتلة عبر مستوياتها.

حدد معنى الخلية ورقم الزيارة

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

الإحداثيات في البرنامج عناوين صحيحة للخلايا. عند عرضها نضع النقطة في مركز مربع الخلية. أول زوج في القائمة يأخذ d=0، وآخر زوج يأخذ d=15. إذا بدأت العد من واحد فستحصل على الأرقام 1 إلى 16؛ لن يتغير المسار، لكن يجب تعديل كل طلب فهرسة وفق الاتفاق الذي اخترته.

ابنِ الرتبة التالية من أربع نسخ

يعرض البناء التكراري أربع نسخ من الرتبة السابقة، مع تغيير اتجاه نسختين وثلاث وصلات تجمعها. [2] نثبت هنا اتجاهًا واحدًا ونكتب تحويلاته بالإحداثيات كي يصبح الرسم قابلًا للفحص.

نبدأ بقائمة واحدة [(0,0)] للرتبة صفر. إذا كان طول ضلع الشبكة السابقة m، فنحوّل كل نقطة قديمة (x,y) إلى أربع قوائم، ثم نلصق القوائم بهذا الترتيب:

عند m=1، تتحول النقطة الوحيدة إلى (0,0)، (0,1)، (1,1)، (1,0). هذه هي الرتبة الأولى. للرتبة الثانية يصبح m=2؛ تتحول نقاط النسخة الأولى إلى (0,0)، (1,0)، (1,1)، (0,1). نهايتها (0,1) تجاور بداية النسخة الثانية (0,2)، فتصل بينهما خطوة رأسية واحدة.

تصل النسخة الثانية في النهاية إلى (1,2)، ثم يبدأ المربع التالي عند (2,2). وآخر نقطة في المربع الثالث (3,2) تليها (3,1). هذه الوصلات الثلاث هي سبب اهتمامنا باتجاه النسخ؛ نقل أربع نسخ بلا مراعاة اتجاهها لن يعطي تلقائيًا القائمة نفسها أو وصلات بطول وحدة.

اقرأ شبكة الأرقام في الاتجاه الصحيح

اكتب الصف الأعلى أولًا عند نسخ الجدول التالي، لكنه يمثل y=3. أسفل الجدول هو y=0. تقرأ الأرقام المتتابعة عبر المربعات لا من يسار السطر إلى يمينه دائمًا.

مثلًا d=8 يعيد (2,2)، وd=13 يعيد (2,1). والعكس: ابحث عن (1,3) فتجد d=6. كتابة 16 كفهرس في هذا المثال خطأ؛ عدد الخلايا 16، لكن أكبر فهرس 15. احتفظنا في الاختبار بقائمة متوقعة من 16 زوجًا ثم قارنا بها البناء، لكي لا تكفي صورة تبدو متعرجة للحكم على صحة الترتيب.

نفّذ البناء واختبر المدخل

def hilbert(n):
    if type(n) is not int or not 0 <= n <= 8:
        raise ValueError('integer order from 0 to 8 required')
    points=[(0,0)]
    for level in range(n):
        m=2**level
        points=([(y,x) for x,y in points]
             + [(x,y+m) for x,y in points]
             + [(x+m,y+m) for x,y in points]
             + [(2*m-1-y,m-1-x) for x,y in points])
    return points

جرب hilbert(2) ثم اقرأ العنصر ذي الفهرس 8، أي التاسع في القائمة. الدالة تبني القائمة في الذاكرة، وتضع حدًا تعليميًا للرتبة عند 8. هذا الحد اختيار في المثال، لا خاصية رياضية للمنحنى. عنده تتكون 65536 نقطة، في حين تعيد الرتبة صفر نقطة واحدة بلا وصلة.

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

فرّق بين قرب الزيارة وقرب الخلايا

لنحسب المسافة الشبكية بين خليتين بجمع فرق x المطلق وفرق y المطلق. في قائمتنا تساوي هذه المسافة واحدًا بين كل زيارتين متتاليتين. لكن الخليتين (1,0) و(2,0) يفصل بينهما ضلع واحد، بينما الفرق بين فهرسيهما 14−1=13. قرب المكان لم يضمن قرب الفهرس.

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

إذن ترتيب هيلبرت لا يفوز في كل مقياس اخترناه. ما نراه أيضًا أن الزيارات 0–3 تملأ مربعًا صغيرًا كاملًا، ثم 4–7 مربعًا ثانيًا، وهكذا. حفظ هذه الكتل التكرارية سؤال مختلف عن تقليل أكبر فرق فهرسة بين كل الجيران. لم نقس زمن ذاكرة مخبئية أو نسبة ضغط ملف، فلا نستنتج أداء برنامج من هذا الجدول الهندسي.

راجع التغطية والاتصال والكتل

فحص البرنامج ثماني رتب، من صفر إلى سبع، بإجمالي 101962 تحققًا. قارن مجموعة النقاط بجميع إحداثيات الشبكة، وتأكد من البداية والنهاية والمسافة بين كل زيارتين. وقارن الإحداثيات بمحول مستقل الأسلوب يقرأ الفهرس رقميًا، مستند إلى طريقة التحويل المنشورة في مرجع البرمجية. [1]

ولكل مستوى داخل كل رتبة، فحصنا كتلًا متتابعة بأحجام 1 و4 و16 وهكذا، وتأكدنا من أنها تغطي مربعات مصطفة مع الشبكة دون فقد خلية. لهذا لا يعتمد الاختبار على جمع عدد النقاط فقط؛ قائمة فيها تكرار ونقطة مفقودة قد تملك العدد الصحيح.

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

المصادر

1. John Burkardt، FSU: Hilbert curve؛ شفرة التحويل
2. Cornell: More Recursion، الشرائح 32–34

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