الگوریتم بسته‌بندی هدیه

انیمیشن الگوریتم بسته‌بندی هدیه. خطوط قرمز اضلاع پوش محدب هستند که تا این لحظه توسط خروجی الگوریتم مشخص شده‌اند. خط سیاه، بهترین حدس الگوریتم در این مرحله از اجرا و خط سبز نیز حدس بعدی است.

در هندسه محاسباتی، بسته‌بندی هدیه (به انگلیسی: Gift Wrapping) الگوریتمی برای محاسبه پوش محدبِ مجموعه‌ای از نقاط است.

حالت دوبُعدی

در حالت دوبُعدی این الگوریتم به راه‌پیمایی جارویس نیز مشهور است. جارویس در سال ۱۹۷۳، در مقاله‌ای این الگوریتم را به چاپ رساند. علت انتخاب نام بسته‌بندی هدیه برای این الگوریتم به این دلیل است که در فضای دوبُعدی نحوه عملکرد این روش مانند پیچاندان کاغذ کادو به دور مجموعه نقاط و احاطه کردن آن‌ها توسط اضلاعی است که به ترتیب به عنوان خروجی الگوریتم حاصل می‌شوند.

الگوریتم

در نهابت خروجی الگوریتم دنباله‌ای به صورت $<p_{0},p_{1},\ldots ,p_{h-1}>$ است که هر عضو این دنباله، یکی از رئوس پوش محدب را تشکیل دهد. در ابتدا پایین‌ترین نقطه مجموعه را که از وجود آن در پوش محدب اطمینان داریم، به عنوان نقطه p₀ انتخاب می‌کنیم. راًس بعدی انتخاب شده که p₁ نام دارد بایستی کوچکترین زاویه در مختصات قطبی نسبت به نقطه p₀ را داشته باشد. (در صورتی که چند نقطه در این شرایط صدق کردند دورترین نقطه را انتخاب کنیم) به‌طور مشابه نقطه p₂ کوچکترین زاویه قطبی را نسبت به p₁ دارد. زمانی که با تکرار این روند، به راًس p_k که بالاترین راًس است رسیدیم، زنجیره راستِ پوش محدب ساخته شده‌است. در شرایط مساوی، p_k را دورترین نقطه انتخاب می‌کنیم. اکنون برای ساختن زنجیره چپ، می‌بایستی با شروع از p_k، راًس p_k+1 را طوری انتخاب کنیم که کوچکترین زاویه قطبی را از محور منفی X نسبت به p_k داشته باشد. این روند را آن‌قدر ادامه می‌دهیم تا مجدداً به p₀ برسیم و پوش محدب کامل شود. البته این الگوریتم را بدون ساختن زنجیره راست و چپ نیز می‌توان پیاده‌سازی کرد، ولی مزیت پیاده‌سازی به وسیله ساختن زنجیره‌های چپ و راست این است که نیازی به محاسبه دقیق زاویه‌های قطبی نبست و به روش ساده‌ای می‌توان زوایا را با هم تنها مقایسه کرد. پیاده‌سازی بدون زنجیره‌های چپ و راست بدین صورت است: نقطه شروع را به طریق مشابه بالا انتخاب می‌کنیم. سپس با فرض اینکه تا این مرحله، آخرین نقطه انتخاب‌شده p_i است، نقطه p_i+1 را طوری انتخاب می‌کنیم که همه نقاط دیگر در یک سمتِ خط p_ip_i+1 باشند. این نقطه با $O(n)$ عملیات، به وسیله مقایسه مختصات قطبی نقاط با p_i مشخص می‌شود. این عملیات را آنقدر تکرار می‌کنیم تا به p₀ = p_h برسیم.

شبه کد

  Jarvis(s)
      pointOnHull = leftmost point in S
      i = 0
      repeat
            P[i] = pointOnHull
            endpoint = S[0]         // initial endpoint for a candidate edge on the hull
            for j from 1 to |S|
                if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint)
                    endpoint = S[j]   // found greater left turn, update endpoint
            i = i+1
            pointOnHull = endpoint
      until endpoint == P[0]      // wrapped around to first hull point

پیچیدگی

اگر تعداد نقاط مجموعه برابر با n و تعداد نقاط روی پوش محدب برابر با h باشد، پیچیدگی زمانی این الگوریتم از $O(nh)$ است؛ زیرا برای هر نقطه p که عضو پوش محدب باشد باید زاویه قطبی $O(n)$ راًس دیگر نسبت به p، با هم مقایسه شوند که هر هر عملیات مقایسه از $O(1)$ است. چون h نقطه روی پوش محدب قرار دارند بنابراین زمان اجرا از $O(nh)$ است. این الگوریتم در صورتی از لحاظ زمانی کارا خواهد بود که n عددی بزرگ نباشد یا اینکه h نسبت به n کوچک باشد. به عبارت دقیق‌تر اگر $h\in o(logn)$، این الگوریتم از الگوریتم پیمایش گراهام سریع تر است. در غیر این‌صورت این الگوریتم در مقایسه با سایر روش‌ها به‌طور مجانبی کُندتر خواهد بود که در نتیجه از الگوریتم‌های مشابه که زمان اجرای کمتری دارند استفاده می‌شود؛ مانند الگوریتم چان که زمان اجرای آن از $O(nlogh)$ است.

الگوریتم‌های یافتن پوش محدب

نام الگوریتم	مرتبه زمانی اجرا
بسته‌بندی هدیه	O(nh)
پیمایش گراهام	O(nlogn)
الگوریتم چان	O(nlogh)

فرایند اجرای الگوریتم Jarvis's march به وسیله ساختن زنجیره‌های چپ و راست

منابع

• H.Cormen, Thomas; E.Leiserson, Charles; L.Rivest, Ronald; Stein, Clifford (2009). "Computational Geometry". Introduction to Algorithms (به انگلیسی). The MIT Press.
• Jarvis, R. A. (1973). "On the identification of the convex hull of a finite set of points in the plane". 2: 18–21. doi:10.1016/0020-0190(73)90020-3. {{cite journal}}: Cite journal requires |journal= (help)