Еще один алгоритм по нахождению выпуклой оболочки множества точек. Теперь уже не такой тормозной (не O=n^3, а O=n log n ) — Сканирование Грэхема.
</pre>
/// <summary>
/// Сканирование Грэхема.
/// </summary>
/// <param name="set"></param>
/// <returns></returns>
public static IEnumerable<Point> ConvexHull(Point[] points)
{
var upper = new List<Point>();
var lower = new List<Point>();
//сортируем точки P и Q в лексикографическом порядке: сначала по x,
//и если у нескольких точек Px = Qx, то сортируем их также по y
points = points.OrderBy(p => p.X).ThenBy(p => p.Y).ToArray();
upper.AddRange(points.Take(2));
//если в upper больше двух точек и если последние три точки upper не
//образуют поворот направо, то удаляем среднюю из них
for (int i = 2; i < points.Count(); i++)
{
upper.Add(points[i]);
while (upper.Count() > 2 && !IsRightTurn(upper.ElementAt(upper.Count - 1),
upper.ElementAt(upper.Count - 2), upper.ElementAt(upper.Count - 3)))
{
upper.RemoveAt(upper.Count() - 2);
}
}
lower.Add(points.ElementAt(points.Count() - 1));
lower.Add(points.ElementAt(points.Count() - 2));
//если в lower больше двух точек и если последние три точки lower не
//образуют поворот направо, то удаляем среднюю из них
for (int i = points.Count() - 2; i >= 0; i--)
{
lower.Add(points.ElementAt(points.Count() - 1));
while (lower.Count() > 2 && !IsRightTurn(lower.ElementAt(lower.Count - 1),
lower.ElementAt(lower.Count - 2), lower.ElementAt(lower.Count - 3)))
{
lower.RemoveAt(lower.Count() - 2);
}
}
//удаляем первую и последнюю точки в lower, чтобы избежать дублирования с upper
lower.RemoveAt(lower.Count() - 1);
lower.RemoveAt(0);
return upper.Concat(lower);
}
<pre>
Вначале сортируем все точки по X. На случай, если вдруг будет несколько точек с одним X, сортируем их лексикографически — также и по Y.
Теперь добавляем первые две точки в список upper (верхняя часть выпуклой оболочки) и начинаем обход всех точку в цикле for. Добавляем третью и далее в цикле while начинаем проверку — есть ли в upper как минимум 3 точки и образуют ли последние три поворот направо. Если три точки есть, но поворота направо не происходит — удаляем среднюю из этих трех и продолжаем работу while.
Аналогичным образом поступаем с «нижней» частью выпуклой оболочки — список lower.
Чтобы избежать дублирования точек в lower и upper, в lower удаляем первую и последнюю точки.
Возвращаем upper с присоединенным к нему в конец lower.
Поворот направо можно определить по положению третьей точки относительно отрезка, образуемого первой и второй точкой:
/// <summary>
/// Представляет ли последовательность трех точек повторот направо.
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <param name="c"></param>
/// <returns></returns>
public static bool IsRightTurn(Point a, Point b, Point c)
{
var seg = new LineSegment(a, b);
return WherePoint(seg, c) < 0;
}
/// <summary>
/// Определяет, где находится точка относительно вектора.
/// (bx-ax)*(py-ay)-(by-ay)*(px-ax)
/// </summary>
/// <returns>i. i больше 0, если точка слева от вектора,
/// a меньше 0, если точка справа от вектора,
/// и = 0, если точка на векторе, прямо по вектору или сзади вектора</returns>
public static int WherePoint(LineSegment vector, Point p)
{
return (vector.Q.X - vector.P.X) * (p.Y - vector.P.Y)
- (vector.Q.Y - vector.P.Y) * (p.X - vector.P.X);
}
Ниже классы точки и отрезка, используемого в алгоритме:
</pre>
/// <summary>
/// Направленный отрезок (p -> q). В общем это вектор.
/// </summary>
public class LineSegment
{
public Point P { get; private set; }
public Point Q { get; private set; }
public LineSegment(Point p, Point q)
{
this.P = p;
this.Q = q;
}
}
public class PointNamed
{
public int X { get; set; }
public int Y { get; set; }
public string Name { get; set; }
public Point Point;
public PointNamed(string name, Point point)
{
this.Name = name;
this.X = point.X;
this.Y = point.Y;
this.Point = point;
}
}
<pre>