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

انیمیشن الگوریتم بسته‌بندی هدیه. خطوط قرمز اضلاع پوش محدب هستند که تا این لحظه توسط خروجی الگوریتم مشخص شده‌اند. خط سیاه، بهترین حدس الگوریتم در این مرحله از اجرا و خط سبز نیز حدس بعدی است.
در هندسه محاسباتی، بسته‌بندی هدیه الگوریتمی برای محاسبه پوش محدب مجموعه‌ای از نقاط است.
حالت دوبعدی
در حالت دوبعدی این الگوریتم به راه‌پیمایی جارویس نیز مشهور است. جارویس در سال ۱۹۷۳، در مقاله‌ای این الگوریتم را به چاپ رساند. علت انتخاب نام بسته‌بندی هدیه برای این الگوریتم به این دلیل است که در فضای دوبعدی نحوه عملکرد این روش مانند پیچاندان کاغذ کادو به دور مجموعه نقاط و احاطه کردن آن‌ها توسط اضلاعی است که به ترتیب به عنوان خروجی الگوریتم حاصل می‌شوند.
الگوریتم
در نهابت خروجی الگوریتم دنباله‌ای به صورت است که هر عضو این دنباله، یکی از رئوس پوش محدب را تشکیل دهد. در ابتدا پایین‌ترین نقطه مجموعه را که از وجود آن در پوش محدب اطمینان داریم، به عنوان نقطه p 0 انتخاب می‌کنیم. راس بعدی انتخاب شده که p 1 نام دارد بایستی کوچکترین زاویه در مختصات قطبی نسبت به نقطه p 0 را داشته باشد. (در صورتی که چند نقطه در این شرایط صدق کردند دورترین نقطه را انتخاب کنیم) به طور مشابه نقطه p 2 کوچکترین زاویه قطبی را نسبت به p 1 دارد. زمانی که با تکرار این روند، به راس p k که بالاترین راس است رسیدیم، زنجیره راست پوش محدب ساخته شده است. در شرایط مساوی، p k را دورترین نقطه انتخاب می‌کنیم. اکنون برای ساختن زنجیره چپ، می‌بایستی با شروع از p k ، راس p k+1 را طوری انتخاب کنیم که کوچکترین زاویه قطبی را از محور منفی X نسبت به p k داشته باشد. این روند را آن‌قدر ادامه می‌دهیم تا مجددا به p 0 برسیم و پوش محدب کامل شود. البته این الگوریتم را بدون ساختن زنجیره راست و چپ نیز می‌توان پیاده‌سازی کرد، ولی مزیت پیاده‌سازی به وسیله ساختن زنجیره‌های چپ و راست این است که نیازی به محاسبه دقیق زاویه‌های قطبی نبست و به روش ساده‌ای می‌توان زوایا را با هم تنها مقایسه کرد.
پیاده‌سازی بدون زنجیره‌های چپ و راست بدین صورت است: نقطه شروع را به طریق مشابه بالا انتخاب می‌کنیم. سپس با فرض اینکه تا این مرحله، آخرین نقطه انتخاب‌شده p i است، نقطه p i+1 را طوری انتخاب می‌کنیم که همه نقاط دیگر در یک سمت خط p i p i+1 باشند. این نقطه با عملیات، به وسیله مقایسه مختصات قطبی نقاط با p i مشخص می‌شود. این عملیات را آنقدر تکرار می‌کنیم تا به p 0 = p h برسیم.
شبه کد
Jarvis(s)
pointOnHull = leftmost point in S
i = 0
repeat
Pi = pointOnHull
endpoint = S0 // initial endpoint for a candidate edge on the hull
for j from 1 to |S|
if (endpoint == pointOnHull) or (Sj is on left of line from Pi to endpoint)
endpoint = Sj // found greater left turn, update endpoint
i = i+1
pointOnHull = endpoint
until endpoint == P0 // wrapped around to first hull point
پیچیدگی
اگر تعداد نقاط مجموعه برابر با n و تعداد نقاط روی پوش محدب برابر با h باشد، پیچیدگی زمانی این الگوریتم از است؛ زیرا برای هر نقطه p که عضو پوش محدب باشد باید زاویه قطبی راس دیگر نسبت به p، با هم مقایسه شوند که هر هر عملیات مقایسه از است. چون h نقطه روی پوش محدب قرار دارند بنابراین زمان اجرا از است.
این الگوریتم در صورتی از لحاظ زمانی کارا خواهد بود که n عددی بزرگ نباشد یا اینکه h نسبت به n کوچک باشد. به عبارت دقیق‌تر اگر ، این الگوریتم از الگوریتم پیمایش گراهام سریع‌تر است. در غیر این‌صورت این الگوریتم در مقایسه با سایر روش‌ها به طور مجانبی کندتر خواهد بود که در نتیجه از الگوریتم‌های مشابه که زمان اجرای کمتری دارند استفاده می‌شود؛ مانند الگوریتم چان که زمان اجرای آن از است.
+ الگوریتم‌های یافتن پوش محدب
نام الگوریتم
مرتبه زمانی اجرا
بسته‌بندی هدیه
پیمایش گراهام
الگوریتم چان
فرایند اجرای الگوریتم Jarviss march به وسیله ساختن زنجیره‌های چپ و راست