مخطط فورونوي: ارسم منطقة أقرب نقطة بثلاثة مواقع

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

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

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

• في مثالنا، حد التعادل بين A وB يقع على x=5، لكن الجزء الفعلي منه ينتهي عند y=17/4.
• خطا التعادل الآخران هما 2x+4y=27 و−2x+4y=7. لا نحتفظ بكل امتدادهما.
• النقطة V=(5,17/4) متساوية البعد عن المواقع الثلاثة، ومربع كل مسافة منها 225/16.
• النقطة (5,6) متساوية البعد عن A وB، لكنها داخل خلية C: مربعات المسافات هي 25،25،4.
• تحقق حساب كسري مستقل من مطابقة التصنيف المباشر لشروط الخلايا عند 1681 نقطة. الخريطة تصف قربًا هندسيًا، ولا تقيس زمن الطريق.

حدد المواقع والمسافة وإطار الرسم

نختار A=(2,2) وB=(8,2) وC=(5,8). جميع الإحداثيات بوحدة طول واحدة، ونرسم الجزء الموجود داخل المربع 0≤x≤10، 0≤y≤10. هذه أعداد من إعداد المقال، وليست مواقع مدارس أو مستشفيات حقيقية.

المسافة المطلوبة هي طول القطعة المستقيمة في المستوى. لنقطة فحص P=(x,y) نستخدم مربعات المسافات: dA²=(x−2)²+(y−2)²، وdB²=(x−8)²+(y−2)²، وdC²=(x−5)²+(y−8)². المقارنة بين المربعات تكفي لأن المسافات غير سالبة، والجذر التربيعي يحفظ ترتيبها.

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

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

استخرج ثلاثة شروط بالمقارنة الجبرية

المقارنة بين A وB

اطرح مربع بعد B من مربع بعد A. تلغى حدود y المشتركة، فنحصل على dA²−dB²=12x−60. إذن A لا يزيد بعدًا على B عندما x≤5، ويتساويان عند x=5. بعد اجتياز هذا المستقيم جهة اليمين تصبح B أقرب من A، دون أن نحسم موقع C بعد.

المقارنة بين A وC

بتوسيع المربعين وطرح الحدود نجد dA²−dC²=6x+12y−81. الشرط dA²≤dC² يساوي 2x+4y≤27. لذلك خلية A تحتاج الشرطين معًا: أن تكون النقطة يسار x=5، وألا تتجاوز الخط 2x+4y=27 إلى جهة C.

المقارنة بين B وC

هذه المرة dB²−dC²=−6x+12y−21، ومنها −2x+4y≤7 لتكون B أقرب أو مساوية لـC. اجمعها مع x≥5 للحصول على خلية B. أما C فتحتاج عكس المقارنتين اللتين دخلت فيهما، أي أن تكون على الجهة العليا من الخطين المائلين أو عليهما.

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

اختر الأجزاء التي تصبح حدودًا فعلية

نعوض x=5 في 2x+4y=27، فنحصل على y=17/4=4.25. التعويض في الخط الآخر يعطي القيمة نفسها. نسمي نقطة الاجتماع V. داخل المربع، يبقى حد A/B من (5,0) إلى V فقط.

لتحديد حد A/C نحتاج مساواتهما مع عدم تفوق B عليهما. في مثالنا يتحقق ذلك على الجزء الذي فيه x≤5. عند الحافة اليسرى للمربع، x=0 يعطي y=27/4=6.75. إذن الحد المرسوم قطعة من (0,27/4) إلى V.

وبالتناظر في أرقامنا، حد B/C يمتد من V إلى (10,27/4). ليس التناظر بديلًا عن الحساب: تعويض x=10 في −2x+4y=7 يعيد y=27/4. أما الأجزاء الأخرى من خطي التعادل فتخسر أمام الموقع الثالث.

تساوي المسافتين وحده لا يصنع حدًا

قارن نقطتين لهما الإحداثي الأفقي نفسه: P=(5,1) وQ=(5,6). عند P نجد dA²=dB²=10 وdC²=49؛ الموقعان المتعادلان هما الأقرب بالفعل. وعند Q نحصل على 25،25،4 بالترتيب؛ الموقع C يتفوق عليهما.

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

دوّن رؤوس الخلايا وافحص المساحة

رؤوس خلية A داخل المربع هي (0,0)، (5,0)، (5,17/4)، (0,27/4). وبالمثل، خلية B لها الرؤوس (5,0)، (10,0)، (10,27/4)، (5,17/4). خلية C هي ما فوق الحدين المائلين إلى أعلى المربع.

في خلية A ضلعان رأسيان متوازيان بطولي 27/4 و17/4، والمسافة الأفقية بينهما 5. مساحة شبه المنحرف هي 5×(27/4+17/4)/2=55/2=27.5. لخلية B المساحة نفسها، فيبقى لـC مقدار 100−55=45 وحدة مربعة.

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

ماذا اختبر الحساب فعلًا؟

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

الشبكة تشمل الإحداثيات من صفر إلى عشرة مع الطرفين، أي 41×41=1681 نقطة. احتُفظ بجميع المواقع المتعادلة بدل اختيار أول اسم في القائمة. أضيفت ثماني حالات محددة تشمل تعادلات ثنائية والتعادل الثلاثي والنقطة التي تتساوى فيها مسافتان دون أن تكونا الأصغر.

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

لا تستبدل زمن الرحلة بخط مستقيم

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

كذلك لا نساوي هذا النشاط بتصنيف أقرب الجيران: هنا نحدد أقرب موقع من ثلاثة، ولا نجمع أصوات عدة جيران أو نقيس دقة تنبؤ. تستطيع متابعة الفرق في شرح خوارزمية أقرب الجيران. وللتدرب، غيّر موضع C ثم أعد المقارنتين اللتين تدخل فيهما؛ لا تحرّك اللون وحده وتفترض أن الحدود القديمة ما زالت صحيحة.

المصادر

1. Brown University — Introduction to Voronoi Diagrams، محاضرة روبرتو تاماسيا، الصفحات 1–3: تعريف الخلايا واتفاق تضمين الحدود.
2. David M. Mount — CMSC 754 Computational Geometry، جامعة ميريلاند، الصفحتان 53–54: أنصاف المستويات والخلايا الإقليدية. النسخة مستضافة لدى جامعة كارنيغي ميلون.

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