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

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

 

 

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