پیمایش گراهام: تفاوت میان نسخه‌ها

برای افزایش سرعت محاسبه لازم نیست زاویه ی واقعی که این نقاط با محور X می سازند محاسبه شود در عوض، محاسبه کسینوس این زاویه کافیست .. <br>

این الگوریتم با در نظر گرفتن هر نقطه در آرایه مرتب شده پیش می رود. برای هر نقطه این موضوع را در نظر می گیرد که آیا حرکت از دو نقطه ای که قبلا در نظر گرفته به این نقطه یک چرخش به چب بوده یا چرخش به راست. اگر چرخش به راست باشد به این معناست که نقطه دوم به آخر بخشی از بدنه محدب نمی باشد و باید حذف شود. این فرآیند تا زمانی ادامه می یابد که مجموعه سه نقطه آخر چرخش به راست باشد. به محض اینکه با یک چرخش به چپ مواجه شود الگوریتم به سراغ نقطه بعدی در آرایه مرتب شده می رود. (اگر در هر مرحله سه نقطه در یک راستا باشند ، ممکن است انتخاب شود یا دور انداخته شود چون در برخی برنامه ها لازم است همه نقاط روی مرز بدنه محدب پیدا شوند. )<br>

<br>

بازهم برای تعیین اینکه آیا سه نقطه تشکیل یک چرخش به چپ را می دهند یا چرخش به راست، نیازی نیست زاویه واقعی میان دو پاره خط محاسبه شود و در واقع می توانید تنها با حسابی ساده به این هدف برسید. برای سه نقطه (x1,y1)، (x2,y2)و (x3,y3) ،محاسبه جهت ضرب خارجی دو برداری که با نقاط (x1,y1) , (x2,y2)و (x1,y1), (x3,y3)تعریف می شوداز طریق تعیین علامت عبارت (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1)میسر است.اگر این عبارت صفر شد نقاط هم راستا هستند. اگر مثبت شد نقاط یک گردش به چپ و در غیر اینصورت یک گردش به راست را تشکیل می دهند.<br>

ابتدا تعریف

<br>

سپس نتایج در آرایه points ذخیره می شود.

<br>

<br>

این شبه کد از کتاب Sedgewick and Wayne's Algorithms چاپ چهارم گرفته شده است.