🗺️ ابنِ مخطط فورونوي الخاص بك
كل نقطة (بذرة) تسيطر على منطقة البكسلات الأقرب إليها منها إلى أي بذرة أخرى. انقر على الخريطة لإضافة بذرة.
انقر في أي مكان لإضافة بذرة. شاهد المجالات وهي تُعاد رسمها فورًا.
🗺️ خريطة مقسّمة إلى مجالات
تخيّل عدة مستشفيات منتشرة في منطقة ما. يُطرح سؤال طبيعي: إذا تعرّضت لحادث، إلى أي مستشفى تذهب؟ الأقرب، بطبيعة الحال. لكن إذًا، لكل مكان على الخريطة يقابله مستشفى «مرجعي» — الأقرب إلى ذلك المكان. بتلوين كل نقطة من الخريطة حسب أقرب مستشفى إليها، تنقسم المنطقة طبيعيًا إلى مناطق. هذا بالضبط هو مخطط فورونوي.
تُسمّى المستشفيات البذور (أو المواقع). وكل منطقة خلية. والسحر هو أن هذا التركيب الذي يبدو طفوليًا يولّد أشكالًا ذات جمال أخّاذ، ويحل مشكلات ملموسة جدًا.
📜 ديكارت وفورونوي والكوليرا
الفكرة قديمة. منذ سنة 1644، رسم رينيه ديكارت في كتابه مبادئ الفلسفة تقسيمات للسماء إلى مناطق نفوذ حول النجوم — وهو حدس قريب جدًا. لكن عالم الرياضيات الأوكراني جورجي فورونوي (1868-1908) هو من قدّم سنة 1908 التعريف الدقيق والعام في أي بُعد كان. ويحمل المخطط اليوم اسمه.
ومع ذلك، فإن أحد أجمل الاستعمالات التاريخية أسبق. ففي سنة 1854، في لندن، كان الطبيب جون سنو يتعقّب وباء الكوليرا. سجّل على خريطة كل وفاة، وموقع مضخّات الماء في الحي. وبرسمه — دون أن يدري — خلايا فورونوي حول المضخّات (منطقة المنازل الأقرب إلى كل مضخّة)، لاحظ أن الوفيات تتركّز بكثافة في خلية مضخّة واحدة، مضخّة برود ستريت. فأُغلقت: فتراجع الوباء. إنها لحظة ميلاد علم الأوبئة الحديث.
📐 التعريف الرياضي
لنأخذ مجموعة منتهية من البذور p1، p2، …، pn في المستوى. خلية فورونوي للبذرة pi هي مجموعة كل نقاط المستوى الأقرب إلى pi منها إلى أي بذرة أخرى:
خلية فورونوي
Cell(pi) = مجموعة النقاط x بحيث، لأي بذرة أخرى pj:
dist(x, pi) ≤ dist(x, pj)
حيث تدل dist على المسافة الإقليدية المعتادة. إذا كان x = (x1, x2) و p = (a, b)، فإن:
dist(x, p) = √( (x1 − a)2 + (x2 − b)2 )
ملاحظة مفيدة للحسابات: مقارنة مسافتين تكافئ مقارنة مربعيهما. وبما أن الجذر التربيعي دالة متزايدة، فإن dist(x, pi) ≤ dist(x, pj) تكافئ dist(x, pi)2 ≤ dist(x, pj)2. يمكن إذًا الاستغناء عن الـ √، مما يسرّع الحساب كثيرًا — وهذا بالضبط ما تفعله المحاكاة أعلاه لتلوين الخريطة في الزمن الحقيقي.
✂️ لماذا تكون الحدود مستقيمة؟
خذ بذرتين فقط A و B. النقاط الأقرب إلى A منها إلى B تقع في جهة؛ والنقاط الأقرب إلى B تقع في الجهة الأخرى. الحدّ هو مجموعة النقاط المتساوية البعد عن A و B — أي بعبارة أخرى الواسط العمودي للقطعة [AB]! إنه مستقيم.
مع n بذرة، كل خلية هي تقاطع أنصاف المستويات المعرّفة بالوسائط العمودية مع كل البذور الأخرى. وتقاطع أنصاف المستويات هو دائمًا مضلّع محدّب. لهذا يشبه مخطط فورونوي دائمًا فسيفساء من المضلّعات ذات الأضلاع المستقيمة. كل ضلع هو جزء من واسط عمودي؛ وكل رأس متساوي البعد عن ثلاث بذور (ومن ثَمّ فهو مركز الدائرة المارة بهذه البذور الثلاث).
🔺 التوأم الخفي: تثليث ديلوني
لكل مخطط فورونوي يقابله كائن ثنوي: تثليث ديلوني. القاعدة بسيطة: نصل بين بذرتين بقطعة إذا وفقط إذا كانت خليتا فورونوي الخاصتان بهما متجاورتين (تتقاسمان ضلعًا). فنحصل عندئذٍ على شبكة من المثلثات.
لهذا الثنوي خاصية مميزة: من بين كل طرق تثليث سحابة نقاط، فإن تثليث ديلوني يعظّم أصغر الزوايا — أي يتجنّب قدر الإمكان المثلثات «المسحوقة». لهذا السبب يتربّع على عرش الإعلاميات الرسومية والمحاكاة: لشبكنة تضاريس، أو نمذجة جسم ثلاثي الأبعاد، أو حل معادلة بالعناصر المنتهية، نريد مثلثات متناسبة جيدًا. فورونوي وديلوني وجهان لعملة واحدة: أحدهما يقسّم الفضاء، والآخر يربطه.
🌍 تطبيقات في كل مكان
- علم الأوبئة: لا تزال طريقة جون سنو تُستعمل لربط حالات المرض بمصدرها الأرجح (بئر، هوائي، مصنع).
- الشبكات والاتصالات: يتصل هاتفك بأقرب هوائي. وخريطة تغطية المشغّل هي مخطط فورونوي بذوره هي الهوائيات.
- علم الأحياء الخلوي: لتحليل نسيج تحت المجهر، نمذّج كل خلية بنواتها (البذرة) ونعيد بناء حدودها بفورونوي.
- الروبوتيك وتخطيط المسار: يتبع الروبوت أضلاع المخطط، لأنها المسارات التي تبقى أبعد ما يمكن عن العوائق.
- التعمير واللوجستيك: أين نضع مدرسة جديدة، أو ثكنة، أو مستودعًا لتقليص مسافة السكان؟ نستدل بخلايا فورونوي.
- الأرصاد الجوية: لتقدير المطر الساقط على منطقة انطلاقًا من بضع محطات، تنسب طريقة مضلّعات ثيسن (اسم آخر لفورونوي) لكل محطة خليتها.
- ألعاب الفيديو والصور التركيبية: يولّد فورونوي بطريقة إجرائية نسائج من الحجر، أو جلد الزواحف، أو البلاط، أو خرائط المجالات والمناطق الحيوية.
🎓 الرابط مع برنامجك الدراسي
أنت تتعامل بالفعل مع كل مكوّنات فورونوي في الثانوي التأهيلي:
- المسافة في المستوى (الهندسة التحليلية، الأولى بكالوريا): الصيغة √((x2 − x1)2 + (y2 − y1)2) هي جوهر كل شيء.
- الواسط العمودي لقطعة: هو، بالتعريف، مجموعة النقاط المتساوية البعد عن نقطتين — أي حدّ من حدود فورونوي.
- المتراجحات وأنصاف المستويات: كل خلية هي تقاطع أنصاف مستويات، وهي الأداة نفسها كما في البرمجة الخطية.
- الدائرة المحيطة: كل رأس من المخطط هو مركز الدائرة المحيطة بمثلث ديلوني.