غلاف محدب: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۱:
[[Image:ConvexHull.svg|thumb|پوش محدب: مثال کِش.]]
برای این که تصور بهتری از پوش محدب به دست آورید، نقاط صفحه را مانند میخ هایی در نظر بگیرید که به دیوار کوبیده شده اند.حال کش تنگی را درنظر بگیرید که همه میخ ها را احاطه کرده است. در این صورت پوش محدب نقاط شکلی خواهد بود که کش به خود می گیرد.
==الگوریتم هایی جهت یافتن پوش محدب ==
ما در این
== الگوریتم پیمایش گراهام ==
[[پرونده:convexhull.gif|300px|thumb|left|300px|نمونه‌ای از فرآیند اجرای الگوریتمJarvis's march.]]▼
مجموعه نقاط ورودی را Q در نظر بگیرید.الگوریتم پیمایش گراهام{{انگلیسی|Grham's Scan}} با در نظر گرفتن یک پشته از نقاط کاندید، پوش محدب را پیدا می کند(ما این پشته راs می نامیم).در این روش همه نقاط یک بار در پشته اضافه می شوند و نقاطی که بر روی محیط پوش محدب قرار ندارند در نهایت از پشته حذف می شوند ودر نتیجه در پایان الگوریتم مجموعه نقاطی که در s قرار دارند همان رئوس پوش محدب است.
Jarvis's march از روشی به نام package wrapping برای یافتن پوش محدب مجموعه Q از نقاط صفحه استفاده میکند.▼
این الگوریتم به این صورت عمل میکند که ابتدا نقاط بر اساس مختصات Y آنها مرتب کرده ودر صورتی که Y برابری داشته باشد بر اساس X آنها را مرتب میکند و در آرایهٔ P نگه می‌دارد. در این صورت نقطه p۰ حتما یکی از نقاط پوش محدب است. پس آن را در یک آرایه به نام C وارد میکند. حال از بین سایر نقاط نقطه‌ای را پیدا میکند که کمترین زاویهٔ قطبی را وابسته به نقطه p۰ دارد و آن را نیز در آرایهٔ C اضافه میکند و همین فرآیند را برای نقطه p۱ تکرار میکند تا این که به آخرین نقطه آرایهٔ p برسد. به مجموعه کنونی که در C قرار دارد right chain (زنجیره راست) می‌گوییم.▼
برای ساختن زنجیره چپ از pn(آخرین نقطهٔ مجموعه P) را انتخاب کرده و باز هم نقطه‌ای را انتخاب می‌کنیم که نسبت به pn کمترین زاویه قطبی را دارد اما این بار نسبت به قسمت منفی محور X و آن نقطه را نیز به مجموعهٔ C اضافه می‌کنیم و این کار را برای این نقطه تکرار می‌کنیم تا به نقطه p۰ اولیه بر گردیم. در این صورت مجموعه C ساخته شده همان پوش محدب مورد نظر است.▼
شبه کد زیر الگوریتم پیمایش گراهام را پیاده سازی می کند.
'''پیچیدگی الگوریتم:''' این الگوریتم از اوردر (nh) است که در آن n تعداد نقاط است و h تعداد رئوس پوش محدب است. زیرا به ازای هر کدام از رئوس پوش محدب یک بار هر یک از نقاط را با عملی از تتای ۱ چک می‌کنیم.▼
{{چپ‌چین}}
<source lang="c">
1 let p[0] be the point in Q with the minimum y-coordinate
or the left most such point in case of a tie
2 letp[1],p[2],...,p[m] be the remaining points in Q,
sorted by polar angle in counterclockwise order around p[0]
(if more than one point has the same angle, remove all but
the one that is farthest from p0)
3 PUSH(p[0], S)
4 PUSH(<p[0],S)
5 PUSH(p[2],S)
6 for i ← 3 to m
7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S),
and p[i] makes a nonleft turn
8 do POP(S)
9 PUSH(p[i],S)
10 return S
</source>
{{پایان چپ‌چین}}
در خط 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 درجه باشد نفر آخر پشته را حذف می کند.
==پیچیدگی الگوریتم پیمایش گراهام==
در این جا نشان می دهیم که زمان اجرای الگوریتم گراهام از <math>O(nlog n)\,\!</math> است. خط 1 الگوریتم زمان <math>O(n)\,\!</math> را مصرف می کند چون یک جستجوی ساده بر روی نقاط است. خط 2 الگوریتم را در صورتی که با الگوریتم [[mergesort]] پیاده سازی کنیم در زمان <math>O(nlog n)\,\!</math> اجرا شود. در قسمت های بعد نیز ما فقط با پشته s کار می کنیم وچون هر نقطه دقیقا یک بار به پشته اضافه می شد و حداکثر یک بار از آن حذف می شود پس بقیه کد نیز در زمان <math>O(n)\,\!</math> اجرا می شود پس در کل الگوریتم پیمایش گراهام در زمان <math>O(nlog n)\,\!</math> اجرا می شود.
== الگوریتمJarvis's march ==
▲[[پرونده:convexhull.gif|300px|thumb|left|300px|نمونه‌ای از فرآیند اجرای الگوریتمJarvis's march.]]
▲Jarvis's march از روشی به نام بسته بندی بسته{{انگلیسی| package wrapping }}برای یافتن پوش محدب مجموعه Q از نقاط صفحه استفاده میکند.
▲این الگوریتم به این صورت عمل میکند که ابتدا نقاط را بر اساس
▲برای ساختن زنجیره چپ {{انگلیسی|right chain}} از
==پیچیدگی الگوریتم==
▲
== منبع ==
*{{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] and [[Clifford Stein]] | title = [[Introduction to Algorithms]] | publisher = MIT Press and McGraw-Hill | year = 2001 | isbn = 0-262-53196-8 | edition = second }}
| |||