الگوریتم اسکن گراهام یکی از روش‌های محبوب و موثر برای محاسبه محیط محدب یک مجموعه از نقاط در فضای دوبعدی است. این الگوریتم به ویژه در مسائل هندسی و گرافیکی کاربرد دارد.
مقدمه‌ای بر الگوریتم اسکن گراهام
این الگوریتم به نام ریچارد گراهام نام‌گذاری شده است و یکی از روش‌های ساخت محیط محدب (Convex Hull) می‌باشد. در واقع، محیط محدب شامل نقاطی است که می‌توانند یک شکل محدب را تشکیل دهند و به نوعی «مرز» نقاط موجود در یک مجموعه را مشخص می‌کند.
مراحل الگوریتم
الگوریتم اسکن گراهام به طور کلی شامل مراحل زیر است:
- انتخاب نقطه مرجع: ابتدا باید نقطه‌ای را به عنوان نقطه مرجع انتخاب کنیم. معمولاً این نقطه، نقطه‌ای با کمترین مختصات y (و در صورت تساوی، کمترین مختصات x) است.
- ترتیب‌دهی نقاط: سپس، نقاط دیگر بر اساس زاویه‌ای که با نقطه مرجع دارند، مرتب می‌شوند. این کار معمولاً با استفاده از تابع آرکتان انجام می‌شود.
- ساخت محیط محدب: در این مرحله، با استفاده از یک استک (Stack)، مسیر را طی می‌کنیم. نقاط را یکی یکی اضافه می‌کنیم و بررسی می‌کنیم که آیا تشکیل یک چرخش به راست یا چپ می‌دهند یا نه. در صورتی که چرخش به راست باشد، نقطه قبلی از استک حذف می‌شود.
- پایان: در نهایت، نقاط باقی‌مانده در استک، نقاط محیط محدب را تشکیل می‌دهند.
پیاده‌سازی در سی‌شارپ
در زبان برنامه‌نویسی سی‌شارپ، می‌توان الگوریتم اسکن گراهام را به راحتی پیاده‌سازی کرد. در زیر یک نمونه کد ساده از این الگوریتم آورده شده است:
```csharp
using System;
using System.Collections.Generic;
using System.Linq;
public class Point
{
public int X { get; set; }
public int Y { get; set; }
}
public class GrahamScan
{
public static List<Point> GetConvexHull(List<Point> points)
{
// مرحله 1: انتخاب نقطه مرجع
Point reference = points.OrderBy(p => p.Y).ThenBy(p => p.X).First();
// مرحله 2: ترتیب‌دهی نقاط
var sortedPoints = points
.OrderBy(p => Math.Atan2(p.Y - reference.Y, p.X - reference.X))
.ToList();
// مرحله 3: ساخت محیط محدب
Stack<Point> hull = new Stack<Point>();
hull.Push(reference);
foreach (var point in sortedPoints)
{
while (hull.Count >= 2)
{
var top = hull.Pop();
var nextTop = hull.Peek();
// چک کردن چرخش
if (CrossProduct(nextTop, top, point) > 0)
{
hull.Push(top);
break;
}
}
hull.Push(point);
}
return hull.ToList();
}
private static double CrossProduct(Point a, Point b, Point c)
{
return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
}
}
```
نتیجه‌گیری
الگوریتم اسکن گراهام یک ابزار قدرتمند و کارا برای حل مسائل هندسی است. با استفاده از این الگوریتم، می‌توان به سادگی محیط محدب یک مجموعه از نقاط را محاسبه کرد. پیاده‌سازی آن در زبان‌های برنامه‌نویسی مختلف، از جمله سی‌شارپ، بسیار ساده است و می‌تواند در پروژه‌های مختلف گرافیکی و محاسباتی مورد استفاده قرار گیرد.
