غلاف محدب: تفاوت میان نسخه‌ها

در ریاضیات، پوشش محدب(Convex hull) یا لفاف محدب مجموعه از نقاط در صفحه اقلیدسی یا فضای اقلیدسی، کوچکترین مجموعه محدبی است که شامل این مجموعه می باشدمی‌باشد. به عنوان مثال، هنگامی که X یک زیر مجموعه محدود از نقاط در صفحه است، پوشش محدب ممکن است به شکل نواری نشان داده شود که در اطراف X کشیده شده استشده‌است. برای این که تصور بهتری از پوش محدب به دست آورید، نقاط صفحه را مانند میخ هاییمیخ‌هایی در نظر بگیرید که به دیوار کوبیده شده اندشده‌اند.حال کش تنگی را درنظر بگیرید که همه میخ‌ها را احاطه کرده استکرده‌است. در این صورت پوش محدب نقاط شکلی خواهد بود که کش به خود می‌گیرد.

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

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

مجموعه نقاط ورودی را Q در نظر بگیرید.الگوریتم پیمایش گراهام{{انگلیسی|Grham's Scan}} با در نظر گرفتن یک پشته از نقاط کاندید، پوش محدب را پیدا می‌کند(ما این پشته راs می نامیم).در این روش همه نقاط یک بار در پشته اضافه می‌شوند و نقاطی که بر روی محیط پوش محدب قرار ندارند در نهایت از پشته حذف می‌شوند ودرو در نتیجه در پایان الگوریتم مجموعه نقاطی که در s قرار دارند همان رئوس پوش محدب است.

شبه کد زیر الگوریتم پیمایش گراهام را پیاده سازیپیاده‌سازی می‌کند.

در خط 1 این کد ابتدا از بین نقاط Q نقطه‌ای را که کمترین مختصه y را دارد انتخاب می‌کند و آن را <math>p_0</math> می نامد. و سپس در خط 2 نقاط باقی‌مانده را نسبت به زاویهٔ قطبی آن‌ها نسبت به <math>p_0</math> مرتب می‌کند. در این مرتب سازیمرتب‌سازی در صورتی که دو نقطه زاویه برابری داشتند آن نقطه‌ای را که فاصله کمتری تا <math>p_0</math> دارد را حذف می‌کند و در پایان نقاط مرتب شده را درآرایهٔ p قرار می‌دهد و نقاط <math>p_0</math> و <math>p_1</math> و <math>p_2</math> را به پشته s اضافه می‌کند. در خطوط 6 تا 10 که در واقع قسمت اصلی الگوریتم است یک بار کل نقاط s را پرمایش می‌کند. در هر مرحله به ازای هر نقطه <math>p_i</math> تا زمانی که زاویه بین دو نفر آخر پشته s و <math>p_i</math> بیش از 180 درجه باشد نفر آخر پشته را حذف می‌کند.

در زیر پیاده سازیپیاده‌سازی این الگوریتم در زبان C# آمده استآمده‌است.

در این جا نشان می دهیم که زمان اجرای الگوریتم گراهام از <math>O(nlog n)\,\!</math> است. خط 1 الگوریتم زمان <math>O(n)\,\!</math> را مصرف می‌کند چون یک جستجوی ساده بر روی نقاط است. خط 2 الگوریتم را در صورتی که با الگوریتم [[مرتب‌سازی ادغامی]] پیاده سازیپیاده‌سازی کنیم در زمان <math>O(nlog n)\,\!</math> اجرا شود. در قسمت‌های بعد نیز ما فقط با پشته s کار می کنیم وچونو چون هر نقطه دقیقاً یک بار به پشته اضافه می‌شد و حداکثر یک بار از آن حذف می‌شود پس بقیه کد نیز در زمان <math>O(n)\,\!</math> اجرا می‌شود پس در کل الگوریتم پیمایش گراهام در زمان <math>O(nlog n)\,\!</math> اجرا می‌شود.

Jarvis's march از روشی به نام بسته بندیبسته‌بندی بسته{{انگلیسی| package wrapping}}برای یافتن پوش محدب مجموعه Q از نقاط صفحه استفاده می‌کند.

این الگوریتم به این صورت عمل می‌کند که ابتدا نقاط را بر اساس مختص Yشان مرتب کرده ودرو در صورتی که Y برابری داشته باشد بر اساس X آنهاآن‌ها را مرتب می‌کند و در آرایهٔ P نگه می‌دارد. در این صورت نقطه <math>p[0]</math> حتماً یکی از نقاط پوش محدب است. پس آن را در یک آرایه به نام C وارد می‌کند. حال از بین سایر نقاط نقطه‌ای را پیدا می‌کند که کمترین زاویهٔ قطبی را وابسته به نقطه <math>p[0]</math> دارد و آن را نیز در آرایهٔ C اضافه می‌کند و همین فرایند را برای نقطه <math>p[1]</math> تکرار می‌کند تا این که به آخرین نقطه آرایهٔ p برسد. به مجموعه کنونی که در C قرار دارد زنجیره راست {{انگلیسی|right chain}} می‌گوییم.