خوارزمية تغليف الهدايا

في الهندسة الحسابية ، تعتبر خوارزمية تغليف الهدايا خوارزمية لحساب الغلاف المحدب لمجموعة معينة من النقاط.

في الحالة ثنائية الأبعاد، تُعرف الخوارزمية أيضًا باسم مسيرة جارفيس ، نسبةً إلى آر. إيه. جارفيس الذي نشرها عام ١٩٧٣؛ وتتميز بتعقيد زمني من رتبة O ( nh ) ، حيث n هو عدد النقاط و h هو عدد النقاط على الغلاف المحدب. ويُعدّ أداؤها في الواقع العملي أفضل من خوارزميات الغلاف المحدب الأخرى عندما تكون n صغيرة أو عندما يُتوقع أن تكون h صغيرة جدًا بالنسبة إلى n . في الحالات العامة، تتفوق عليها العديد من الخوارزميات الأخرى (انظر خوارزميات الغلاف المحدب ).

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

_تبدأ خوارزمية تغليف الهدايا بنقطة i = 0 ونقطة p₀ معروفة بأنها تقع على الغلاف المحدب، مثلاً، النقطة الموجودة في أقصى اليسار، ثم تختار النقطة _pᵢ₊₁ بحيث تقع جميع النقاط على يمين الخط pᵢ _- pᵢ₊₁ . يمكن إيجاد هذه النقطة في زمن O ( n ) بمقارنة الزوايا القطبية لجميع النقاط بالنسبة للنقطة pᵢ _التي تُعتبر مركز الإحداثيات القطبية . بجعل i = i + 1، وتكرار العملية حتى الوصول إلى _pᵢ₊₁ = p₀ مرة _{أخرى ،} نحصل على الغلاف المحدب في h خطوة. في بُعدين، تُشبه خوارزمية تغليف الهدايا عملية لف خيط (أو ورق تغليف) حول مجموعة النقاط.

يمكن توسيع هذا النهج ليشمل أبعادًا أعلى.

خوارزمية jarvis(S) هي // S هي مجموعة النقاط // ستكون P مجموعة النقاط التي تشكل الغلاف المحدب. حجم المجموعة النهائي هو i. pointOnHull := أقصى نقطة يسارية في S // والتي يُضمن أنها جزء من CH(S) i := 0 يكرر P[i] := نقطة على الهيكل endpoint := S[0] // نقطة النهاية الأولية لحافة مرشحة على الهيكل لكل j من 0 إلى |S | // يُعدّ تطابق نقطة النهاية مع نقطة على الهيكل حالة نادرة، ولا يمكن أن تحدث إلا عندما يكون j == 1 ولم يتم بعد تحديد نقطة نهاية أفضل للحلقة. إذا كانت ( نقطة النهاية == نقطة على الهيكل) أو (S[j] على يسار الخط من P[i] إلى نقطة النهاية) endpoint := S[j] // تم العثور على منعطف يساري أكبر، قم بتحديث نقطة النهاية i := i + 1 نقطة على الهيكل := نقطة النهاية حتى نقطة النهاية == P[0] // التف حول نقطة الهيكل الأولى

تتحقق الحلقة الداخلية من كل نقطة في المجموعة S ، وتتكرر الحلقة الخارجية لكل نقطة على الهيكل. وبالتالي، يكون إجمالي وقت التشغيل هو${\displaystyle O(nh)}$يعتمد وقت التشغيل على حجم المخرجات، لذا فإن مسيرة جارفيس هي خوارزمية حساسة للمخرجات .

ومع ذلك، ولأن وقت التشغيل يعتمد خطيًا على عدد رؤوس الهيكل، فإنه أسرع من ${\displaystyle O(n\log n)}$تُستخدم خوارزميات مثل مسح غراهام عندما يكون عدد رؤوس الغلاف h أصغر من log n . وتجمع خوارزمية تشان ، وهي خوارزمية أخرى للغلاف المحدب، بين الاعتماد اللوغاريتمي لمسح غراهام وحساسية الإخراج لخوارزمية تغليف الهدايا، مما يحقق زمن تشغيل تقاربي.  ${\displaystyle O(n\log h)}$ وهذا يُحسّن كلاً من مسح غراهام وتغليف الهدايا.

• خوارزميات الغلاف المحدب