الگوریتم اسکن گراهام یکی از روش‌های محبوب و موثر برای محاسبه محیط محدب یک مجموعه از نقاط در فضای دوبعدی است. این الگوریتم به ویژه در مسائل هندسی و گرافیکی کاربرد دارد.
مقدمه‌ای بر الگوریتم اسکن گراهام
این الگوریتم به نام ریچارد گراهام نام‌گذاری شده است و یکی از روش‌های ساخت محیط محدب (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);
}
}
```
نتیجه‌گیری
الگوریتم اسکن گراهام یک ابزار قدرتمند و کارا برای حل مسائل هندسی است. با استفاده از این الگوریتم، می‌توان به سادگی محیط محدب یک مجموعه از نقاط را محاسبه کرد. پیاده‌سازی آن در زبان‌های برنامه‌نویسی مختلف، از جمله سی‌شارپ، بسیار ساده است و می‌تواند در پروژه‌های مختلف گرافیکی و محاسباتی مورد استفاده قرار گیرد.
ALGORITHM GRAHAM SCAN IN C#
الگوریتم اسکن گراهام یکی از روش‌های معروف برای پیدا کردن محیط محدب یک مجموعه از نقاط در صفحه است. این الگوریتم به ویژه در مسائلی مانند گرافیک کامپیوتری و هندسه محاسباتی کاربرد دارد.
الگوریتم اسکن گراهام مراحل زیر را دنبال می‌کند:
- پیدا کردن نقطه مرجع:
- مرتب‌سازی نقاط:
- ساخت محیط محدب:
- بازگشت به محیط محدب:
کد C# برای الگوریتم اسکن گراهام
```csharp
using System;
using System.Collections.Generic;
using System.Linq;
class Point
{
public int X { get; set; }
public int Y { get; set; }
}
class GrahamScan
{
public static List<Point> ConvexHull(List<Point> points)
{
// پیدا کردن نقطه مرجع
Point pivot = points.OrderBy(p => p.Y).ThenBy(p => p.X).First();
// مرتب‌سازی نقاط
points = points.OrderBy(p => Math.Atan2(p.Y - pivot.Y, p.X - pivot.X)).ToList();
Stack<Point> hull = new Stack<Point>();
hull.Push(pivot);
foreach (var point in points)
{
while (hull.Count >= 2)
{
Point top = hull.Pop();
Point nextToTop = hull.Peek();
if (CrossProduct(nextToTop, 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);
}
}
```
با استفاده از این کد، می‌توانید محیط محدب نقاط دلخواه خود را به راحتی محاسبه کنید. توجه داشته باشید که این الگوریتم با کارایی O(n log n) عمل می‌کند.
به طور کلی، الگوریتم اسکن گراهام یک روش قدرتمند و کارآمد برای حل مسائل هندسی است که به راحتی می‌توان آن را در زبان‌های برنامه‌نویسی مختلف پیاده‌سازی کرد.
