CSharp 实现平面凸包算法 源代码
时间: 2023-09-29 20:06:12 浏览: 52
可以直接回答,以下是一个CSharp实现平面凸包算法的源代码:
```csharp
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConvexHull
{
class Point
{
public int X { get; set; }
public int Y { get; set; }
public Point(int x, int y)
{
X = x;
Y = y;
}
}
class Program
{
static void Main(string[] args)
{
List<Point> points = new List<Point>
{
new Point(0, 3),
new Point(2, 2),
new Point(1, 1),
new Point(2, 1),
new Point(3, 0),
new Point(0, 0),
new Point(3, 3)
};
List<Point> convexHull = GetConvexHull(points);
Console.WriteLine("Convex hull:");
foreach (Point point in convexHull)
{
Console.WriteLine("(" + point.X + ", " + point.Y + ")");
}
}
static List<Point> GetConvexHull(List<Point> points)
{
if (points.Count < 3)
{
throw new ArgumentException("At least 3 points are required");
}
List<Point> convexHull = new List<Point>();
Point firstPoint = points.OrderBy(p => p.Y).ThenBy(p => p.X).First();
Point currentPoint = firstPoint;
convexHull.Add(currentPoint);
Point nextPoint;
do
{
nextPoint = points[0];
foreach (Point point in points)
{
if (point == currentPoint)
{
continue;
}
int crossProduct = CrossProductLength(point, currentPoint, nextPoint);
if (crossProduct > 0 ||
(crossProduct == 0 && Distance(point, currentPoint) > Distance(nextPoint, currentPoint)))
{
nextPoint = point;
}
}
convexHull.Add(nextPoint);
currentPoint = nextPoint;
} while (currentPoint != firstPoint);
return convexHull;
}
static int CrossProductLength(Point point1, Point point2, Point point3)
{
return (point2.X - point1.X) * (point3.Y - point1.Y) -
(point2.Y - point1.Y) * (point3.X - point1.X);
}
static int Distance(Point point1, Point point2)
{
return (int)Math.Sqrt(Math.Pow(point2.X - point1.X, 2) + Math.Pow(point2.Y - point1.Y, 2));
}
}
}
```