ALGORITHM GRAHAM SCAN: A COMPREHENSIVE OVERVIEW
الگوریتم اسکن گراهام یکی از مشهورترین روش‌ها برای یافتن حداقل محاط در نقاط داده در فضای دوبعدی است. این الگوریتم به طور خاص برای حل مسئله محاط سازی نقاط استفاده می‌شود. در ادامه، مراحل این الگوریتم را به تفصیل بررسی می‌کنیم.
STEP 1: SELECTING THE REFERENCE POINT
ابتدا باید یک نقطه مرجع را انتخاب کنیم. این نقطه معمولاً نقطه‌ای است که کمترین مقدار y را دارد. اگر چند نقطه با کمترین مقدار y وجود داشته باشد، نقطه‌ای را که بیشترین مقدار x را دارد انتخاب می‌کنیم. این نقطه مرجع، پایه‌ای برای تعیین ترتیب سایر نقاط خواهد بود.
STEP 2: SORTING THE POINTS
پس از انتخاب نقطه مرجع، سایر نقاط باید بر اساس زاویه‌ای که با خط افقی از نقطه مرجع می‌سازند، مرتب شوند. این کار با استفاده از تابع تانژانت انجام می‌شود. با این حال، اگر دو نقطه زاویه یکسان داشته باشند، باید نقطه نزدیک‌تر به مرجع را در اولویت قرار دهیم.
STEP 3: CREATING THE HULL
حالا که نقاط مرتب شده‌اند، باید یک لیست خالی برای نگهداری نقاط مرزی ایجاد کنیم. ابتدا دو نقطه اول را به این لیست اضافه می‌کنیم. سپس، برای هر نقطه جدید، بررسی می‌کنیم که آیا آن نقطه به سمت چپ یا راست می‌چرخد. اگر سمت چپ باشد، نقطه به لیست اضافه می‌شود. اما اگر سمت راست باشد، آخرین نقطه در لیست حذف می‌شود تا زمانی که یک چرخش به سمت چپ پیدا کنیم.
STEP 4: FINALIZING THE HULL
در نهایت، این فرایند تا زمانی که تمام نقاط بررسی شوند ادامه پیدا می‌کند. در پایان، لیست نقاط مرزی، حداقل محاط را تشکیل می‌دهد که شامل نقاطی است که در شکل نهایی قرار دارند.
CONCLUSION
به طور کلی، الگوریتم اسکن گراهام یک روش کارآمد و سریع برای حل مسئله محاط سازی است. با پیچیدگی زمانی O(n log n)، این الگوریتم در مقایسه با روش‌های دیگر، یکی از بهترین گزینه‌ها برای مسائل هندسی محسوب می‌شود.
