تقريب الغلاف المقعر من إحداثيات النقاط

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

اختاروا الإحداثيات والعتبة المناسبتين

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

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

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

افهموا طريقة تنقيح الحد

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

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

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

وتتبع أطوال الحواف الترتيب الدوري نفسه. قد تُحذف النقاط الخارجية الواقعة على استقامة واحدة ما لم تصبح لاحقاً مفيدة في التنقيح.

راجعوا القيود قبل الاعتماد على المضلع

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

قارنوا بين الأساليب إذا كانت للطوبولوجيا آثار قانونية أو علمية أو متعلقة بالسلامة. تخص المساحة والمحيط المضلع المستوي الناتج ويستخدمان نظام الإحداثيات الذي قدمتموه، وليسا قياسين جيوديسيين. ارسموا الغلاف المرتب فوق نقاط المصدر لتتحققوا من أن العتبة المختارة تمثل التجمعات والتجاويف المقصودة.

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