غلاف محدب
دانشنامه عمومی
ما در این قسمت دو الگوریتم برای یافتن پوش محدب مجموعه ای از نقاط ارائه خواهیم داد. خروجی هر دوی این الگوریتمها رئوس پوش محدب در جهت پادساعتگرد خواهد بود.
مجموعه نقاط ورودی را Q در نظر بگیرید. الگوریتم پیمایش گراهام ( به انگلیسی: Grham's Scan ) با در نظر گرفتن یک پشته از نقاط کاندید، پوش محدب را پیدا می کند ( ما این پشته راs می نامیم ) . در این روش همه نقاط یک بار در پشته اضافه می شوند و نقاطی که بر روی محیط پوش محدب قرار ندارند در نهایت از پشته حذف می شوند و در نتیجه در پایان الگوریتم مجموعه نقاطی که در s قرار دارند همان رئوس پوش محدب است.
شبه کد زیر الگوریتم پیمایش گراهام را پیاده سازی می کند.
1 let p be the point in Q with the minimum y - coordinate or the left most such point in case of a tie 2 letp, p, . . . , p be the remaining points in Q, sorted by polar angle in counterclockwise order around p ( if more than one point has the same angle, remove all but the one that is farthest from p0 ) 3 PUSH ( p, S ) 4 PUSH ( p, S ) 5 PUSH ( p, S ) 6 for i ← 3 to m 7 do while the angle formed by points NEXT - TO - TOP ( S ) , TOP ( S ) , and p makes a nonleft turn 8 do POP ( S ) 9 PUSH ( p, S ) 10 return S در خط 1 این کد ابتدا از بین نقاط Q نقطه ای را که کمترین مختصه y را دارد انتخاب می کند و آن را p 0 می نامد. و سپس در خط 2 نقاط باقی مانده را نسبت به زاویهٔ قطبی آن ها نسبت به p 0 مرتب می کند. در این مرتب سازی در صورتی که دو نقطه زاویه برابری داشتند آن نقطه ای را که فاصله کمتری تا p 0 دارد را حذف می کند و در پایان نقاط مرتب شده را درآرایهٔ p قرار می دهد و نقاط p 0 و p 1 و p 2 را به پشته s اضافه می کند. در خطوط 6 تا 10 که در واقع قسمت اصلی الگوریتم است یک بار کل نقاط s را پرمایش می کند. در هر مرحله به ازای هر نقطه p i تا زمانی که زاویه بین دو نفر آخر پشته s و p i بیش از 180 درجه باشد نفر آخر پشته را حذف می کند. در زیر پیاده سازی این الگوریتم در زبان C# آمده است.
