برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: اولین گام در این الگوریتم یافتن نقطه‌ای با کمترین y است. اگر چند نقطه با کمترین y وجود داشت، در این مجموعه نقطه با کمترین x انتخاب خواهد شد. این نقطه را p می‌نامیم. این مرحله به اندازه (o (n زمان می‌برد که n تعداد نقاط می‌باشد. سپس مجموعه نقاط باید بر حسب افزایش زاویه‌ای که آن‌ها و نقطه p با محور x می‌سازند، مرتب شوند. از هر الگوریتم مرتب‌سازی برای این این مرحله می‌توان استفاده کرد به عنوان مثال مرتب‌سازی هرمی که پیچیدگی زمانی آن (o (n log n است. برای افزایش سرعت محاسبه لازم نیست زاویه واقعی که این نقاط با محور x می‌سازند محاسبه شود در عوض، محاسبه کسینوس این زاویه کافیست. این الگوریتم با در نظر گرفتن هر نقطه در آرایه مرتب شده پیش می‌رود. برای هر نقطه این موضوع را در نظر می‌گیرد که آیا حرکت از دو نقطه‌ای که قبلا در نظر گرفته به این نقطه یک چرخش به چب بوده یا چرخش به راست. اگر چرخش به راست باشد به این معناست که نقطه دوم به آخر بخشی از بدنه محدب نمی‌باشد و باید حذف شود. این فرایند تا زمانی ادامه می‌یابد که مجموعه سه نقطه آخر چرخش به راست باشد. به محض اینکه با یک چرخش به چپ مواجه شود الگوریتم به سراغ نقطه بعدی در آرایه مرتب شده می‌رود. (اگر در هر مرحله سه نقطه در یک راستا باشند، ممکن است انتخاب شود یا دور انداخته شود چون در برخی برنامه‌ها لازم است همه نقاط روی مرز بدنه محدب پیدا شوند. بازهم برای تعیین اینکه آیا سه نقطه تشکیل یک چرخش به چپ را می‌دهند یا چرخش به راست، نیازی نیست زاویه واقعی میان دو پاره‌خط محاسبه شود و در واقع می‌توانید تنها با حسابی ساده به این هدف برسید. برای سه نقطه (x ۱ ,y ۱)، (x ۲ ,y ۲) و (x ۳ ,y ۳)، محاسبه جهت ضرب خارجی دو برداری که با نقاط (x ۱ ,y ۱) , (x ۲ ,y ۲) و (x ۱ ,y ۱) , (x ۳ ,y ۳) تعریف می‌شوداز طریق تعیین علامت عبارت (x ۲ − x ۱) (y ۳ − y ۱) − (y ۲ − y ۱) (x ۳ − x ۱) میسر است. اگر این عبارت صفر شد نقاط هم راستا هستند. اگر مثبت شد نقاط یک گردش به چپ و در غیر اینصورت یک گردش به راست را تشکیل می‌دهند. این فرایند در نهایت به نقطه‌ای که از آن شروع کرده‌است بازمی گردد، که در آن نقطه الگوریتم به پایان رسیده‌است و پشته شامل نقاط روی بدنه محدب در خلاف جهت عقربه‌های ساعت می‌باشد. مرتب‌سازی نقاط دارای پیچیدگی زمانی (o (n logn می‌باشد. در حالی که ممکن است به نظر برسد پیچیدگی زمانی حلقه از o (n ۲) …
برداشت:
پیمایش گراهام روشی است برای محاسبه پوش محدب مجموعه متناهی از نقاط صفحه که پیچیدگی زمانی آن o (n logn) است . این الگوریتم به افتخار رونالد گراهام که نسخهٔ اصلی الگوریتم را در ۱۹۷۲ منتشر کرد نامگذاری شده‌است . این الگوریتم تمامی راس‌های مرزی پوش محدب به صورت مرتب می‌یابد .