Загрузка

Многоугольники

Теги: unity, математика, алгоритмы

В данной статье я бы хотел рассмотреть такую фигуру, как многоугольник с точки зрения вычислительной геометрии. 

Практическая применимость

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

Раскрывая тему

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

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

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

Так же я буду часто оперировать такими понятиями как:<> Простой многоугольник - любой геометрически верный многоугольник, который не пересекает сам себя. Точки такого многоугольника тем не менее могут совпадать или лежать на грани, но не заходить "внутрь" фигуры.<> Выпуклый многоугольник - это такой многоугольник, из любой точки которого можно провести линию в любую другую точку. Все внутренние углы такой фигуры меньше 180 градусов. Явные примеры выпуклой фигуры - треугольник, квадрат, параллелограмм.

Данная статья разбита на конкретные задачи, которые встают перед разработчиками.

Общие функции

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

public static float Scalar(Vector2 a, Vector2 b)
{
    return a.x * b.x + a.y * b.y;
}

public static float Scalar(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2)
{
    return PseudoScalar(a2 - a1, b2 - b1);
}

public static float PseudoScalar(Vector2 a, Vector2 b)
{
    return a.x * b.y - b.x * a.y;
}

public static float PseudoScalar(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2)
{
    return PseudoScalar(a2 - a1, b2 - b1);
}

/// Угол по часовой стрелке на плоскости (0 <= angle < 360)
public static float AngleClockwise(Vector2 v1, Vector2 v2)
{
    var angle = Vector2.Angle(v1, v2);
    if (v1.x * v2.y - v1.y * v2.x > 0)
        return angle;
    return 360 - angle;
}

/// Угол по часовой стрелке на плоскости (0 <= angle < 360)
public static float AngleClockwise(Vector2 a, Vector2 b, Vector2 c)
{
    return AngleClockwise(a - b, c - b);
} 

Перебор граней многоугольника

Этот простой прием приходится использовать чуть ли не чаще всего остального. Его суть состоит в том, чтобы в цикле перебрать "текущую" и "следующую" точку сразу.<>Делается это вот так:

for (int i = 0; i < points.Length; i++)
{
    var a = points[i];
    var b = points[(i+1)%points.Length];
}

Этот простой способ позволяет захватить в последний шаг первую точку многоугольника в качестве переменной b.

Нахождение площади многоугольника

Самый быстрый способ посчитать плошадь многоугольника - воспользоваться методом треугольников. Для этого мы берем по очереди две смежных точки многоугольника и соединяем их с произвольной точкой на плоскости (чтобы не выдумывать, пусть это будет нулевая координата).

Соответственно, перебирая грани многоугольника и вычисляя, мы получаем вот такие функции:

//Ориентированная площадь треугольника равна половине скаляра
public static float OrientationTriangleArea(Vector2 a, Vector2 b, Vector2 c)
{
    return PseudoScalar((a - b), (c - b)) / 2f;
}

public static float OrientationPolygonArea(List polygonPoints)
{
    var s = 0f;
    for (int i = 0; i < polygonPoints.Count; i++)
    {
        var a = polygonPoints[i];
        var b = polygonPoints[(i + 1) % polygonPoints.Count];
        s += OrientationTriangleArea(Vector2.zero, a, b);
    }
    return s;
}

Таким образом, для нахождения обычной площади нам достаточно добавить Mathf.Abs().<>Так же с учетом погрешности float'a, проявляемой на операциях деления, можно оптимизировать вычисление, сначала сложив псевдоскаляры, а уже потом поделив всё на 2.

узнаем Направление последовательности по углам

Фактически, последовательность, которая нам поступает может оказаться в одном из двух направлений - по или против часовой стрелки. Если многоугольник простой, то определить такую последовательность можно сложив углы многоугольника по часовой стрелке. Так как нам известно, что сумма углов простого многоугольника равна 180f * (pointCount - 2) мы можем соотнести эти данные и если они не совпадают - то многоугольник "вывернут".

/// Сумма углов простого многоугольника
public static float AngleSummSimplePolygon(int pointCount)
{
    return 180f * (pointCount - 2);
}

/// Сумма всех углов по часовой стрелке у данного многоугольника
public static float AngleSummClockwisePolygon(List points)
{
    var summAngle = 0f;
    for (int i = 0; i < points.Count; i++)
    {
        var a = points[i];
        var b = points[(i + 1) % points.Count];
        var c = points[(i + 2) % points.Count];
        var angle = AngleClockwise(a, b, c);
        summAngle += angle;
    }
    return summAngle;
}

/// Расположены ли точки многоугольника по часовой стрелке?
public static bool IsClockwise(List points)
{
    var realAngle = AngleSummClockwise(points);
    var needAngle = AngleSumm(points.Count);
    return realAngle.LessOrApprox(needAngle);
}

/// Перевернуть многоугольник, если он идет против часовой стрелки
public static List AsClockwise(List points)
{
    return IsClockwise(points) ? points.ToList() : points.Revert();
}

Примечания:

  • здесь я использую функцию LessOrApprox, которая означает "меньше или приблизительно равно", так как float имеет погрешность. Подобная функция реализуется по-разному разными программистами, но наиболее часто используется вариант Mathf.Abs(a-b) < 0.000001f
  • я использую функцию Revert(), обращающую массив, которая возможно недоступна, но ее принцип легко повторить.

Узнаем направление последовательности по ориентированной площади

Есть и более надежный способ узнать направление последовательности - просто вычислить ориентированную площадь многоугольника. Отрицательная площадь даст результат по часовой, а положительная - против часовой. Однако, несмотря на то что этот способ более точный, он дает обратный эффект при "обращении" оси Y (когда положительные числа считаются с левого верхнего угла). Другим минусом является то, что этот способ не работает на самопересекамой фигуре хоть сколько нибудь адекватно, потому должна существовать некоторая гарантия того, что предоставленный многоугольник является простым. Несмотря на это, я настоятельно советую пользоваться ориентированной площадью, и только в особых "гибких" случаях применять написанный выше способ "сложения углов".

Проверка принадлежности точки многоугольнику

Проверка принадлежности точки многоугольнику<>Иногда нам нужно проверить принадлежит ли точка многоугольнику. Однако в случае с самопересекаемым многоугольником - всё зависит от правила, которое мы используем. <> В случае, если наш многоугольник простой, мы можем использовать любое из указанных правил. Правила эти состоят в том, как ведет себя многоугольник на "внутренних дырах".<> Различие продемонстрировано на данном рисунке:

Even-odd rule

Это правило работает по следующему алгоритму:

  • Берем произвольную точку вне многоугольника (в моем примере это будет смещение по x от искомой точки, я просто вычисляю максимальное значение x для многоугольника)
  • Проводим луч, к точке, состояние которой нам нужно узнать
  • Узнаем количество пересечений, и если оно четное, то пересечения нет.
/// Пренадлежит ли точка многоугольнику
public static bool PolygonContainsEvenOdd(List polygonPoints, Vector2 point)
{
    var x = polygonPoints.Max(v => v.x) + 10f;
    var p1 = new Vector2(x, point.y);
    var p2 = point;
    bool contains = false;
    for (int i = 0; i < polygonPoints.Count; i++)
    {
        var a1 = polygonPoints[i];
        var a2 = polygonPoints[(i + 1) % polygonPoints.Count];
        if (SegmentIntersectFast(a1, a2, p1, p2))
            contains = !contains;
    }
    return contains;
}

В своем примере я просто обращал bool при каждом пересечении, фактически смысл тот же. По факту расчет можно существенно оптимизировать (по сравнению с моим примером функции), так как нас интересуют только ребра, для которых xAny > point.x && y1 <= point.y <= y2, что в свою очередь проверяется полиноминально, даже без поиска всяких крайних точек, как это сделал я. Таким образом проверка пересечений будет происходить реже.

Non-zero winding rule

Это правило работает почти так же, но учитывает направление, в котором была пересечена та или иная линия. Если луч пересечен слева направо, то мы увеличиваем значение, если справа налево - уменьшаем. Если финальный результат равен 0, то точка находится вне многоугольника, любое другое значение - мы внутри. Моя функция для исполнения этого довольно габаритна (но работает!)

/// Пренадлежит ли точка многоугольнику (самопересекающийся многоугольник)
public static bool PolygonContainsNonzeroRule(List polygonPoints, Vector2 point)
{
    if (polygonPoints.Count < 1)
        return false;
        
    //Вычисляем края
    var minX = polygonPoints[0].x;
    var minY = polygonPoints[0].x;
    var maxX = polygonPoints[0].y;
    var maxY = polygonPoints[0].y;
    for (int i = 0; i < polygonPoints.Count; i++)
    {
        var current = polygonPoints[i];
        if (minX > current.x) minX = current.x;
        if (maxX < current.x) maxX = current.x;
        if (minY > current.y) minY = current.y;
        if (maxY < current.y) maxY = current.y;
    }
    //Вне границ
    if (point.x < minX || point.y < minY || point.x > maxX || point.y > maxY)
        return false;


    int coef = 0;
    var p1 = point;
    var p2 = new Vector2(maxX + 1, point.y);
    for (int i = 0; i < polygonPoints.Count; i++)
    {
        var a1 = polygonPoints[i];
        var a2 = polygonPoints[(i + 1) % polygonPoints.Count];

        if (SegmentIntersect(a1, a2, p1, p2))
        {
            var normalY = (a1 - a2).y;
            if (normalY < 0) coef++;
            else if (normalY > 0) coef--;
        }
    }
    return coef != 0;
}

Здесь важно понимать что мой код естественно не идеален. По сути тут так же, как и в прошлом примере достаточно было проверять только ребра, для которых xAny > point.x && y1 <= point.y <= y2, что в свою очередь упростило бы проверку пересечений. Однако мой пример хорошо иллюстрирует сам способ поиска пересечений как таковой.

Поиск точки, гарантированно принадлежащей многоугольнику

Изначально эта задача может показаться проще, чем кажется. <>Если вы имеете дело с выпуклым многоугольником, то, разумеется, нам будет достаточно найти центр масс (проще говоря, среднее арифметическое):

public static Vector2 Average(params Vector2[] points)
{
    return points.Aggregate(new Vector2(), (current, point) => current + point) / points.Length;
}

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

int j = polygon.Count;
while (j-- > 0)
{
    var a = polygon[j];
    var b = polygon[(j + 1) % polygon.Count];
    var c = polygon[(j + 2) % polygon.Count];
    var angle = AngleClockwise(a, b, c);
    if (angle < 180f && !Math.SegmentIntersectWithoutCloseUp(insidePoly, c, a))
    {
        insidePoint = (a + b + c) / 3f;
        if (!Math.SegmentIntersectWithoutCloseUp(polygon, b, insidePoint))
            return true;
    }
}
insidePoint = Vector2.zero;
return false;

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

Триангуляция

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

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

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

var result = new List();
for (int i = 1; i < polygonPoints.Count - 1; i++)
{
    result.Add(polygonPoints[0]);
    result.Add(polygonPoints[i + 1]);
    result.Add(polygonPoints[i]);
}
return result;

<>Конструктивная сплошная геометрия

Конструктивная сплошная геометрия в принципе является реализуемой для многоугольников и имеет практическое применение. Тут важно понимать, что в 2D используется 4, а не 3 операции.

  • Union (объединение)
  • Difference (вычитание)
  • Exclusion (исключение)
  • Intersection (пересечение)

Операция исключения не испольуется в 3D, так как ее результат всегда скрыт внутри меша, однако в 2D это самостоятельная операция.

<>Чтобы реализовать любую из операций, достаточно сделать следующие действия:

  1. Построить из многоугольников A и B граф, общими точками на котором станут точки пересечения
  2. С помощью графа, разбить многоугольник на простые многоугольники.
  3. В каждом простом многоугольнике найти точку внутри
  4. С помощью правил even-odd или non-zero winding найти, является многоугольник дырой или частью большего мноугольника A.
  5. С помощью правил even-odd или non-zero winding найти, является многоугольник дырой или частью большего мноугольника B.
  6. Применить к двум полученным значениям соответствующую логическую операцию (например aContain || bContain будет эквивалетно операции Union)
  7. Многоугольники, вернувшие значение true можно объединять и закрашивать.

Разбиение самопересекаемого многоугольника на простые

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

Представление самопересекаемого многоугольника как граф

Пример кода:

private static Graph BakeGraph(IEnumerable polygon)
{
    var pArray = polygon.ToList();
    var area = Mathf.Abs(Math.OrientationPolygonArea(pArray));
    if (area.Approx(0f))
        return new Graph();

    var handles = pArray.Select(x => new GraphPoint(x)).ToList();
    var graph = new Graph();
    //Добавляем все точки пересечения к текущему полигону
    for (int i = 0; i < handles.Count - 1; i++)
        for (int j = i; j < handles.Count; j++)
        {
            var a1 = handles[i];
            var a2 = handles[(i + 1)%handles.Count];
            var b1 = handles[j];
            var b2 = handles[(j + 1)%handles.Count];
            Vector2 cross;
            if (Math.SegmentIntersectWithoutCloseUp(a1.value, a2.value, b1.value, b2.value,
                out cross))
            {
                var handle = new GraphPoint(cross);
                handles.Insert(j + 1, handle);
                handles.Insert(i + 1, handle);
            }
        }

    graph.points.AddRange(handles);
    for (int i = 0; i < handles.Count; i++)
    {
        var a = handles[i];
        var b = handles[(i + 1)%handles.Count];
        var edge = new GraphEdge(a, b);
        a.edges.Add(edge);
        b.edges.Add(edge);
        graph.edges.Add(edge);
    }
    return graph;
}

Естественно, здесь нужно так же создать соответствующие классы для графа, точек и ребер.


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

  1. триангуляция
  2. создание простых многоугольников из графа

Эти алгоритмы нуждаются в более тщательном объяснении, и я думаю есть смысл позже рассказать об этом отдельно.

Поделиться
Многоугольники
В данной статье я бы хотел рассмотреть такую фигуру, как многоугольник с точки зрения вычислительной геометрии, на примере тех задач, которые мне доводилось решать....
article
3 Монеты
Devion (4 года назад)

7 комментариев:
romgerman, уровень 1 (3 года назад):

Статья хорошая. Хотелось бы увидеть статью про многогранники.

Devion, уровень 1 (3 года назад):

SpectreZ, Вам спасибо, что читаете.

Кстати, функция "захлыста" в таком варианте не работает правильно для отрицательных чисел. Для первого ряда отрицательных можно использовать

(index+points.Count)%points.Count

а для гарантии любого значения вообще можно использовать такую функцию:

if (index < 0)
    return points.Count - Mathf.Abs(index)%points.Count;
return index%points.Count;
SpectreZ, уровень 2 (3 года назад):

Очень полезная статья. Я пока не дочитал до конца, но уже заинтересовался описываемыми функциями. Особенно понравился подход с применением остатка от деления для выбора пар точек многоугольника - простой и красивый.

Полезны функции векторной алгебры, они часто применимы в разработке игр. Функция нахождения площади прямоугольника оказалась для меня посложнее, но всё равно понятна. Наверное потому что я не очень люблю математику. :) Я интересуюсь компьютерной графикой как с позиции художника, так и с позиции программиста. Раньше работал с OpenGL и надеюсь в будущем развивать свои проекты.

Хочу поблагодарить автора за подробное объяснение некоторых алгоритмов в своих статьях.

Devion, уровень 1 (4 года назад):

Конечно. Наверное, как будет окно в работе - что-то напишу

SaiLight, уровень 4 (4 года назад):

Планируешь рассказать здесь когда-нибудь о своем алгоритме?

Devion, уровень 1 (4 года назад):

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

Первый раз, когда решил писать алгоритм триангуляции. Этот алгоритм ужасно реализовывался везде, где мне приходилось видеть, код составлял от 2 до 7 тысяч строк причем был совершенно неоправданым. Тогда я сел сам разбираться, искал закономерности. В результате нашел достаточно чтобы сделать гораздо быстрее и гораздо короче.

Второй раз, когда писал наработку CSGPolygon. Я хотел выложить ее на Asset Store, но пока не дошли руки записать видео. Цель наработки лично для меня была в том, чтобы создать плоский городской ландшафт с дырами и потом решил пойти дальше, попробовав сделать полноценный CSG 2D инструмент. Жаль в коммент не могу приложить изображение, но у меня это сделать получилось.

SaiLight, уровень 4 (4 года назад):

Довольно обширная статья получилась. Тем не менее, эта статья принадлежит твоему блогу о Unity, а не проекту House Builder, всвязи с чем возник вопрос: используются ли описанные знания в проекте или это чисто личный интерес?

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

Войти