الگوریتم بستهبندی هدیه
در هندسه محاسباتی، بستهبندی هدیه (به انگلیسی: Gift Wrapping) الگوریتمی برای محاسبه پوش محدبِ مجموعهای از نقاط است.
حالت دوبُعدی
در حالت دوبُعدی این الگوریتم به راهپیمایی جارویس نیز مشهور است. جارویس در سال ۱۹۷۳، در مقالهای این الگوریتم را به چاپ رساند. علت انتخاب نام بستهبندی هدیه برای این الگوریتم به این دلیل است که در فضای دوبُعدی نحوه عملکرد این روش مانند پیچاندان کاغذ کادو به دور مجموعه نقاط و احاطه کردن آنها توسط اضلاعی است که به ترتیب به عنوان خروجی الگوریتم حاصل میشوند.
الگوریتم
در نهابت خروجی الگوریتم دنبالهای به صورت
شبه کد
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) |
پیمایش گراهام | O(nlogn) |
الگوریتم چان | O(nlogh) |
منابع
- 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.