مخطط فورونوي
مناطق فورونوي لمجموعة من النقاط
حول هذه الآلة الحاسبة
تقسّم حاسبة مخطط فورونوي المستوى حول مجموعة من النقاط (المواقع) إلى مناطق، حيث يكون كل موضع في منطقةٍ أقرب إلى موقعها الخاص منه إلى أي موقع آخر. وتحسب كل منطقة كمضلّع محدَّب دقيق عبر تقاطع أنصاف المستويات لمنصّفات القطع العمودية، وتُبلّغ عن مساحة كل منطقة وأيّ المواقع متجاورة، وترسم مخططًا مُرمَّزًا بالألوان. مفيدة في تحليل الجار الأقرب، ومسائل تحديد المواقع والتغطية، ودراسة الهندسة الحاسوبية، والفن التوليدي.
أمثلة شائعة
- نقطتان (0,0) و(2,0) → ينقسم المستوى على طول x = 1 إلى نصفي منطقتين متساويتين يتشاركان ضلعًا واحدًا
- زوايا مربّع 0,0 2,0 2,2 0,2 → أربعة أرباع متساوية تلتقي عند المركز، 4 أضلاع فورونوي
- مربّع مع مركز 1,1 5,1 5,5 1,5 3,3 → المركز يجاور جميع الزوايا الأربع (8 أضلاع في المجموع)
- ثلاث نقاط على استقامة واحدة 0,0 1,0 2,0 → ثلاثة شرائط متوازية يفصلها ضلعان
الأسئلة الشائعة
ما هو مخطط فورونوي؟
بمعلومية مجموعة من النقاط تُسمّى المواقع، يقسّم مخطط فورونوي المستوى إلى منطقة واحدة لكل موقع. كل موضع داخل منطقة موقعٍ ما يكون أقرب إلى ذلك الموقع منه إلى أي موقع آخر. وتقع الحدود بين المناطق على منصّفات القطع العمودية للمواقع المتجاورة.
لماذا تُعرَض المناطق داخل صندوق؟
المناطق التابعة للمواقع الواقعة على الحافة الخارجية لمجموعة النقاط غير محدودة — فهي تمتد إلى ما لا نهاية. ولعرضها وقياسها، تقصّ الحاسبة كل منطقة داخل صندوق حدود محشوٍّ حول نقاطك، بحيث تكون المساحات المُبلَّغ عنها هي المساحات ضمن ذلك الصندوق.
كيف تُحسَب كل منطقة؟
كل منطقة هي تقاطع أنصاف المستويات: لكل موقع آخر، احتفظ بالجانب الأقرب من منصّف القطعة العمودي إلى الموقع الحالي. ويعطي تقاطع أنصاف المستويات هذه (مع صندوق الحدود) مضلّعًا محدَّبًا دقيقًا، فتتجمّع مساحات المناطق لتساوي مساحة الصندوق كاملةً.