Нахождение выпуклой оболочки для множества точек. Медленный вариант.

Давно хотел начать разбирать алгоритмы вычислительной геометрии и вот начал.

Это, самый первый алгоритм из книги «Вычислительная геометрия. Алгоритмы и приложения».  В книге он называется SlowConvexHull. Работает он неидеально — из-за того, что в нем нет разницы в том, где находится точка — на/перед/позади отрезка. Хотя это не проблема алгоритма, а проблема моей реализации.

Писал его на C#. Думаю, надо бы понемногу начинать осваивать что-то на Python для операций вроде нахождения положения точки относительно отрезка. Вначале меня эта формулировка очень смутила, потому что не подумал, что у этого отрезка есть направление. Вероятно, аналогичных операций еще очень много и не уверен, стоит ли все их реализовывать самостоятельно по формулам.

Код программки для реализации алгоритма.

Класс направленного отрезка

/// <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;
}
}

Сам алгоритм:

/// <summary>
/// Получение минимальной выпуклой оболочки множества точек.
/// </summary>
/// <param name="set"></param>
/// <returns></returns>
public static List<Point> SlowConvexHull(IEnumerable<Point> set)
{
//получаем все возможные векторы для множества точек
var vectors = GetAllLineSegmentsForPointsSet(set.ToArray());
//вектора, входящие в выпуклую оболочку
List<LineSegment> E = new List<LineSegment>();

//оставляем только те вектора, которые являются частью выпуклой оболочки.
bool valid;
foreach(var ve in vectors)
{
valid = true;
//точки, не являющиеся частью текущего вектора ve
var points = set.Where(a => (a.X != ve.P.X && a.Y != ve.P.Y) || (a.X != ve.Q.X && a.Y != ve.Q.Y));

foreach (var p in points)
{
if (WherePoint(ve, p) > 0)
{
valid = false;
break;
}
}

if (valid)
E.Add(ve);
}

//получаем уникальные вектора
E = E.GroupBy(a => new { a.P, a.Q }).Select(a => a.First()).ToList();

//получаем вершины полигона, отсортированные в порядке движения
//по оболочке по часовой стрелке
var res = OrderLineSegments(E);
return res;
}

/// <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);
}

/// <summary>
/// Получение упорядоченного в порядке обхода по часовой стрелке
/// списка вершин выпуклой оболочки из списка направленных отрезков.
/// </summary>
/// <returns></returns>
public static List<Point> OrderLineSegments(List<LineSegment> vectors)
{
List<Point> L = new List<Point>();

var fst = vectors.First();
L.Add(fst.P);
L.Add(fst.Q);

while (true)
{
var po = vectors.Where(v => v.P.X == L.Last().X && v.P.Y == L.Last().Y).First().Q;
L.Add(po);
if (L.First().X == po.X && L.First().Y == po.Y)
break;
}

return L;
}

/// <summary>
/// Получение всех возможных векторов для множества точек.
/// </summary>
/// <param name="points"></param>
/// <returns></returns>
public static List<LineSegment> GetAllLineSegmentsForPointsSet(Point[] points)
{
List<LineSegment> res = new List<LineSegment>();

for (int i = 0; i < points.Length; i++)
{
for (int j = 0; j < points.Length; j++)
{
if(i != j)
{
res.Add(new LineSegment(points[i], points[j]));
res.Add(new LineSegment(points[j], points[i]));
}
}
}

res = res.GroupBy(x => new { x.P, x.Q }).Select(x => x.First()).ToList<LineSegment>();
return res;
}

Выполнение алгоритма:

public static void Main(string[] args)
{
//множество точек на плоскости
List<Point> P = GetRandomPoints(5, maxXY: 10);

//тест:
P = GetRandomPointsTest();

//вершины оболочки выпуклой плоскости CH(P) в порядке обхода по часовой стрелке
IEnumerable<Point> L = SlowConvexHull(P);
//рисуем все точки и минимальную выпуклую оболочку для них
DrawPointsSetWithConvexHull(P, L);

foreach(var po in L)
Console.WriteLine(string.Format("X: {0} and Y: {1}", po.X, po.Y));
Console.ReadLine();
}

/// <summary>
/// Получение множества случайных точек.
/// </summary>
/// <param name="num">вернуть это количество точек</param>
/// <param name="maxXY">максимальная длина по абсциссе и ординате
/// (отсчет от 0, без отрицательных значений)</param>
/// <returns></returns>
public static List<Point> GetRandomPoints(int num, int maxXY = 25)
{
List<Point> res = new List<Point>();
Random r = new Random();
int x;
int y;

for(int i = 0; i < num; i++)
{
x = r.Next(maxXY + 1);
y = r.Next(maxXY + 1);
res.Add(new Point(x, y));
}

res =
res.GroupBy(a => new { a.X, a.Y })
.Select(a => a.First())
.ToList();

return res;
}