В рамках этой статьи я вновь попытаюсь аккуратно стереть границы между абстрактной алгеброй и объектно-ориентированным программированием, чтобы посмотреть на то, что получится на стыке. Ознакомиться с предыдущими трудами на эту тему можно по ссылкам: раз и два.

На этот раз мы остановимся на связи между алгебраическими кольцами и алгоритмом поиска выпуклой оболочки множества точек (convex hull).

▍ Алгебраическое отступление

Мои предыдущие публикации на эту тематику вышли практически год назад. Там представлены некоторые наработки по проектированию алгебраических структур. Но ими я пользоваться не буду, поскольку за прошедший год многое изменилось.

В частности, в C# 11 появилась достаточно интересная возможность языка — статические абстрактные члены интерфейсов. Подробнее о static abstract members in interfaces можно прочитать здесь.

Напомню, что кольцо — это структура, которая является абелевой группой по сложению и моноидом по умножению. При этом умножение дистрибутивно относительно сложения.

Если раньше саму алгебраическую структуру было необходимо проектировать как некий отдельный тип, то теперь про сам тип можно сказать, что над ним можно эту структуру построить. Покажу это на примере кольца, абстрагировавшись от связи с другими структурами.

Было:

public interface IRing<T>
{
    T Plus(T left, T right);

    T Zero { get; }

    T Inverse(T item);
        
    T Times(T left, T right);

    T One { get; }
}

Стало:

public interface IRing<T>
    where T : IRing<T>
{
    static abstract T operator +(T x, T y);

    static abstract T Zero { get; }

    static abstract T operator -(T x);

    static abstract T operator *(T x, T y);

    static abstract T One { get; }
}

То есть теперь абстракция операций будет входить в само определение типа, а не выделяться в отдельную структуру данных. Теперь встаёт вопрос о том, как использовать эти конструкции.

Потому что если хочется создать некий пользовательский тип данных, то ничего не мешает просто реализовать интерфейс IRing<T> и радоваться жизни. Но с системными типами вроде int, double и так далее такой трюк не пройдёт.

Конечно, в Microsoft сидят неглупые ребята, и они этот вопрос предусмотрели. Настолько предусмотрели, что теперь стандартная библиотека C# содержит контракты, описывающие те самые алгебраические структуры, о которых я пишу уже в третий раз.

Чтобы убедиться в этом, давайте заглянем внутрь исходного кода типа int.

Там мы увидим, что структура Int32 стала реализовывать много новых интерфейсов. В частности, среди них есть обобщённый интерфейс ISignedNumber<T>, который расширяет контракт INumberBase<T>. Этот контракт является описанием абстракции числа, который аккумулирует известные уже нам свойства за счёт использования таких интерфейсов, как: IAdditionOperators<T, T, T>, IAdditiveIdentity<T, T>, IMultiplicativeIdentity<T, T> и так далее.

Каждый из этих типов атомарно представляет из себя некое абстрактное свойство, присущее некоторой алгебраической структуре. Все эти типы можно найти в пространстве имён System.Numerics.

Таким образом, получается, что для совместимости со стандартной библиотекой C# кольцо можно описать следующим образом:

public interface IRing<T> :
    IAdditionOperators<T, T, T>,
    IAdditiveIdentity<T, T>,
    IUnaryNegationOperators<T, T>,
    IMultiplyOperators<T, T, T>,
    IMultiplicativeIdentity<T, T>
    where T :
    IAdditionOperators<T, T, T>,
    IAdditiveIdentity<T, T>,
    IUnaryNegationOperators<T, T>,
    IMultiplyOperators<T, T, T>,
    IMultiplicativeIdentity<T, T>
{
}

В этом случае можно создавать свои пользовательские типы данных, над которыми можно построить кольцо, и использовать при этом системные, над которыми оно уже построено. Правда, есть нюанс. При проектировании типов данных, которые будут использовать нечто, над чем можно построить кольцо, не получится использовать наш интерфейс в качестве generic constraint.

Дело в том, что в C# отсутствуют intersection types.

Пусть имплементация IRing<T> и означает совокупность нескольких других интерфейсов, их реализация по отдельности не равнозначна. На эту тему даже были дискуссии в формате proposal в репозитории dotnet/csharplang.

Например, перепишем реализацию кольца эндоморфизмов, представленную в одной из предыдущих статей. Новая реализация будет описывать сам эндоморфизм (обёртка над Func<T, T>). При этом ограничение на то, что сами отображения могут существовать только над абелевыми группами, будет не таким лаконичным в силу вышеописанных причин.

public class Endomorphism<TGroup> : IRing<Endomorphism<TGroup>>
    where TGroup :
    IAdditionOperators<TGroup, TGroup, TGroup>,
    IAdditiveIdentity<TGroup, TGroup>,
    IUnaryNegationOperators<TGroup, TGroup>
{
    private readonly Func<TGroup, TGroup> _func;

    private Endomorphism(Func<TGroup, TGroup> func) =>
        _func = func;

    public TGroup At(TGroup x) =>
        _func(x);

    public static implicit operator Endomorphism<TGroup>(Func<TGroup, TGroup> func) =>
        new(func);

    public static Endomorphism<TGroup> operator +(Endomorphism<TGroup> left, Endomorphism<TGroup> right) =>
        (Func<TGroup, TGroup>)(x => left.At(x) + right.At(x));

    public static Endomorphism<TGroup> AdditiveIdentity =>
        (Func<TGroup, TGroup>)(_ => TGroup.AdditiveIdentity);

    public static Endomorphism<TGroup> operator -(Endomorphism<TGroup> value) =>
        (Func<TGroup, TGroup>)(x => -value.At(x));

    public static Endomorphism<TGroup> operator *(Endomorphism<TGroup> left, Endomorphism<TGroup> right) =>
        (Func<TGroup, TGroup>)(x => left.At(right.At(x)));

    public static Endomorphism<TGroup> MultiplicativeIdentity =>
        (Func<TGroup, TGroup>)(x => x);
}

▍ Convex hull & Graham Scan

Продолжая речь о том, что можно обобщать с помощью алгебраических структур, в частности, колец, хочется заострить внимание на такой вещи, как построение выпуклой оболочки (convex hull). О том, что это такое, хорошо написали в Википедии, приведя пример с доской, верёвкой и гвоздями.

Чёрная линия — это доска, а точки — гвозди. Синяя линия — верёвка, она же наш convex hull

Для построения convex hull придумали множество различных алгоритмов. Здесь же рассмотрим один из самых популярных — Graham Scan. Поскольку он относительно эффективен при своей простоте в реализации.

Для написания самой реализации необходимо уметь вычислять «поворот» образующегося угла из трёх точек и сортировать точки на плоскости в порядке возрастания полярного угла. Соединив всё вместе, получим примерно следующее:

public record Point2D(int X, int Y)
{
    public static Point2D operator -(Point2D p1, Point2D p2) =>
        new(p1.X - p2.X, p1.Y - p2.Y);

    public static int operator *(Point2D p1, Point2D p2) =>
        p1.X * p2.X + p1.Y * p2.Y;

    public static int operator ^(Point2D p1, Point2D p2) =>
        p1.X * p2.Y - p1.Y * p2.X;
}

public enum Turn : byte
{
    ClockWise,
    Collinear,
    CounterClockWise
}

public class TurnCalculator : ITurnCalculator
{
    public Turn GetTurn(Point2D p1, Point2D p2, Point2D p3)
    {
        var crossProduct =
            (p2.X - p1.X) * (p3.Y - p1.Y) -
            (p2.Y - p1.Y) * (p3.X - p1.X);

        return crossProduct switch
        {
            < 0 => Turn.ClockWise,
            > 0 => Turn.CounterClockWise,
            _ => Turn.Collinear
        };
    }
}

public class GrahamScan : IConvexHullFinder
{
    private readonly ITurnCalculator _calculator;

    public GrahamScan(ITurnCalculator calculator) =>
        _calculator = calculator;

    public IEnumerable<Point2D>? GetConvexHull(IList<Point2D>? points)
    {
        if (points is null or { Count: < 3 })
            return null;

        var p0 = points.OrderBy(p => p.X).ThenBy(p => p.Y).First();
        points = points.OrderBy(p => p, new PolarOrderComparer(p0)).ToList();

        var hull = new Stack<Point2D>();
        hull.Push(points[0]);
        hull.Push(points[1]);
        hull.Push(points[2]);

        for (var i = 3; i < points.Count; i++)
        {
            while (_calculator.GetTurn(hull.NextToTop(), hull.Peek(), points[i]) != Turn.CounterClockWise)
                hull.Pop();

            hull.Push(points[i]);
        }

        return hull;
    }
}

Реализация начинает исполнение алгоритма с поиска самой левой и самой нижней точки во множестве, после чего оставшиеся точки сортируются в порядке возрастания полярного угла, который образует с осью X вектор с началом в наименьшей точке. Этап сортировки гарантирует, что алгоритм посещает каждую точку против часовой стрелки.

Затем инициализируется стек для хранения контура с тремя первыми точками. Алгоритм проходит по оставшимся точкам и добавляет к контуру точку в порядке против часовой стрелки, удаляя любые точки, которые нарушают свойство выпуклости многоугольника.

Основой алгоритма является цикл while, который, удаляя точки из контура, повторяется до тех пор, пока текущая точка не образует поворот против часовой стрелки с последними двумя точками в контуре.

Например, для следующего набора точек:

IConvexHullFinder.Instance.GetConvexHull(new List<Point2D>
    {
        new(0, 3),
        new(1, 1),
        new(2, 2),
        new(4, 4),
        new(0, 0),
        new(1, 2),
        new(3, 1),
        new(3, 3)
    }
)?.ToList().ForEach(Console.WriteLine);

Получим контур из точек, указанных ниже:

Point2D { X = 0, Y = 3 }
Point2D { X = 4, Y = 4 }
Point2D { X = 3, Y = 1 }
Point2D { X = 0, Y = 0 }

Графическая интерпретация результата

Внимательно изучив приведённую реализацию, нетрудно заметить, что над координатами точек можно построить кольцо. Действительно, векторное произведение, используемое для определения направления поворота, использует все свойства этой алгебраической структуры. Также дополнительно следует наложить на тип координаты ограничение по реализации интерфейса IComparable<T>. Изменённый класс точки будет выглядеть следующим образом:

public record Point2D<TRing>(TRing X, TRing Y)
    where TRing :
    IComparable<TRing>,
    IAdditionOperators<TRing, TRing, TRing>,
    IAdditiveIdentity<TRing, TRing>,
    IUnaryNegationOperators<TRing, TRing>,
    IMultiplyOperators<TRing, TRing, TRing>,
    IMultiplicativeIdentity<TRing, TRing>
{
    public static Point2D<TRing> operator -(Point2D<TRing> p1, Point2D<TRing> p2) =>
        new(p1.X + -p2.X, p1.Y + -p2.Y);

    public static TRing operator *(Point2D<TRing> p1, Point2D<TRing> p2) =>
        p1.X * p2.X + p1.Y * p2.Y;

    public static TRing operator ^(Point2D<TRing> p1, Point2D<TRing> p2) =>
        p1.X * p2.Y + -(p1.Y * p2.X);
}

Соотвественно, далее следует распространить это обобщённое ограничение в соответствующие методы, заменяя 0 на TRing.AdditiveIdentity. Также вычитание можно заменить комбинацией плюса и унарного минуса, либо же использовать контракт ISubtractionOperators<T, T, T>.

▍ Вместо заключения

Теперь отсутствует зависимость от конкретного типа координаты в алгоритме построения convex hull. У него есть области применения за рамками вычислительной геометрии: финансы, машинное обучение, текстовый анализ.

Например, можно ввести для точки операцию определения принадлежности внутренности контура, и вот уже имеем простейший классификатор.

Все ограничения находятся только внутри нашего сознания. Но если мы используем наше воображение, то возможности станут безграничными.

Исходный код, использованный в статье, доступен на GitHub по ссылке: github.com/StefanioHabrArticles/generalize-this-and-that.

Ещё я веду Telegram-канал StepOne, куда выкладываю много интересного контента про коммерческую разработку, C# и мир IT глазами эксперта.

Telegram-канал с розыгрышами призов, новостями IT и постами о ретроиграх ????️