الأغلفة المحدبة والمقعّرة
خوارزميات وتطبيقات
الأغلفة المحدبة والمقعّرة
الغلاف المحدب في المستوى
الغلاف المحدب في المستوى هو أصغر مضلع محدب يحيط بمجموعة من النقاط ثنائية الأبعاد. يُستخدم هذا الغلاف بكثرة في معالجة الصور، التحليل الهندسي، وتحديد حدود الأشكال والنقاط في الفضاء.
خوارزمية مسح غراهام لإيجاد الغلاف المحدب
خوارزمية مسح غراهام هي طريقة مرتبة وفعّالة لإيجاد الغلاف المحدب لمجموعة من النقاط في المستوى. تقوم هذه الطريقة بفرز النقاط حسب الزاوية حول نقطة الأصل ثم بناء الغلاف المحدب تدريجياً بالانتقال بين النقاط بحيث تحافظ على خاصية التحدب.
- تعقيدها الزمني: لوغاريتمي خطي
- تعتبر من أشهر الطرق لاستخراج الغلاف المحدب في بعدين.
كيف تعمل الخوارزمية؟
تتبع الخوارزمية الخطوات التالية:
- 1تحديد النقطة ذات أقل إحداثي صادي (وفي حال التساوي أقل إحداثي سيني).
- 2فرز جميع النقاط حسب الزاوية مع النقطة المختارة.
- 3الانتقال بين النقاط المرتبة وبناء الغلاف بإضافة كل نقطة، وحذف أي نقطة تكسر التحدب.
ملاحظة حول تعقيد الخوارزميات
تعقيد الخوارزمية هو مقياس يصف كمية الموارد المطلوبة (مثل الزمن أو الذاكرة) لتنفيذ خوارزمية ما بالنسبة لحجم البيانات المدخلة. يُستخدم عادةً لوصف الأداء باستخدام رموز مثل تعقيد(ن) أو تعقيد(ن لوغ ن). فهم تعقيد الخوارزميات مهم جداً لاختيار الحلول الأكثر كفاءة، خاصة عند التعامل مع بيانات ضخمة أو تطبيقات تتطلب سرعة عالية.
أمثلة على تعقيد الخوارزميات
فيما يلي بعض الأنواع الشائعة لتعقيد الخوارزميات مع أمثلة توضيحية:
- تعقيد(1): زمن ثابت لا يعتمد على حجم البيانات. مثال: الوصول إلى عنصر في مصفوفة مباشرةً عبر الفهرس، يستغرق نفس الزمن مهما كان حجم المصفوفة.
- تعقيد(ن): زمن خطي يزداد مع عدد العناصر. مثال: البحث عن عنصر في قائمة يتطلب المرور على جميع العناصر في أسوأ الحالات.
- تعقيد(ن لوغ ن): زمن شبه خطي يزداد أسرع من الخطي وأبطأ من التربيعي. مثال: خوارزميات الفرز السريعة مثل الفرز السريع أو الفرز الدمجي، حيث يتم تقسيم البيانات ثم معالجتها.
- تعقيد(ن²): زمن تربيعي يزداد بشكل كبير مع زيادة عدد العناصر. مثال: خوارزميات الفرز البسيطة مثل الفرز بالاختيار أو الفرز الفقاعي، حيث تتم مقارنة كل عنصر مع جميع العناصر الأخرى.
كلما كان تعقيد الخوارزمية أقل، كانت أكثر كفاءة عند التعامل مع كميات كبيرة من البيانات. اختيار الخوارزمية المناسبة يوفر الوقت والموارد بشكل كبير.
الغلاف المحدب في الفضاء الثلاثي الأبعاد
في الفضاء الثلاثي الأبعاد، يُمثل الغلاف المحدب أصغر شكل ثلاثي الأبعاد محدب يحيط بجميع النقاط المعطاة. واحدة من أكثر الطرق استخداماً لإيجاد هذا الغلاف هي خوارزمية التقسيم السريع للفضاء، حيث تُقسم المجموعة وتُبنى الأوجه المحدبة تدريجياً.
خوارزمية التقسيم السريع
- تعمل غالباً بتعقيد زمني لوغاريتمي خطي.
- تتميز بسرعتها وفعاليتها في البيانات ثلاثية الأبعاد.
كيف تعمل الخوارزمية؟
تتبع الخوارزمية الخطوات التالية:
- 1اختيار نقاط عشوائية لتشكيل سطح مبدئي.
- 2توزيع باقي النقاط على جوانب السطح.
- 3تكرار عملية التوسع على الجهة الخارجية لكل سطح عبر إضافة أقصى نقطة خارجية، وتحديث السطح.
- 4استمرار التوسع حتى تشمل جميع النقاط.
مثال تطبيقي: الغلاف المقعر لشكل الهلال
يوضح هذا المثال كيف يمكن لطريقة الغلاف المقعر بمعامل التقعر تمثيل الأشكال المعقدة مثل شكل الهلال بدقة، بخلاف الغلاف المحدب الذي يتجاهل التفاصيل والانحناءات الداخلية. كما يظهر في الصورة التالية، الغلاف المحدب يفشل في تغطية الشكل بالكامل.
ما هي طريقة الغلاف المقعر بمعامل التقعر؟
تعتمد هذه الطريقة على تحليل مجموعة من النقاط وربطها عبر مثلثات تُنشأ باستخدام خوارزمية التثليث، ومن ثم تصفية هذه المثلثات بناءً على نصف قطر دائرة التمحور لكل منها. إذا كان نصف القطر أكبر من قيمة معينة (معامل التقعر)، يتم استبعاده لتجنب تمثيل المناطق غير الواقعية في الشكل.
باستخدام معامل التقعر يمكن التحكم في درجة تفصيل الغلاف الناتج. كلما كانت القيمة أصغر، زادت قدرة الغلاف على تتبع التفاصيل الدقيقة للشكل مثل الحواف والانحناءات.
- مثالية لتمثيل الأشكال غير المنتظمة مثل الهلال، الأحرف، أو الأجسام المعمارية.
- تعتمد الدقة على قيمة معامل التقعر المستخدمة أثناء التثليث.
في المثال التالي، نُطبّق هذه الطريقة على شكل مستطيل، حيث يظهر كيف يمكن للطريقة الحفاظ على الزوايا والانحناءات الداخلية بدقة.
كيف تعمل الخوارزمية؟
تعتمد خوارزمية الغلاف المقعر بمعامل التقعر على تحليل البنية الهندسية للنقاط عبر تثليثها، ثم استبعاد الأجزاء التي لا تتماشى مع الشكل الحقيقي. الخطوات الأساسية تشمل:
- 1إنشاء تثليث لجميع النقاط المدخلة.
- 2حساب دائرة التمحور لكل مثلث ناتج.
- 3استبعاد المثلثات التي يتجاوز نصف قطر دائرتها قيمة "معامل التقعر".
- 4دمج المثلثات المتبقية لاشتقاق حدود الشكل النهائي.
في المثال التالي، نُطبّق هذه الطريقة على شكل الهلال، حيث يظهر كيف يمكن للطريقة الحفاظ على الزوايا والانحناءات الداخلية بدقة.
نلاحظ أن اختيار معامل التقعر يؤثر بشكل كبير على دقة الغلاف المقعر. في الصور المتحركة التالية، نرى كيف يتغير شكل الغلاف المقعر مع اختلاف قيمة معامل التقعر:
