Earcut - базовый, почти учебный алгоритм триангуляции, но при некоторых раскладах он обгоняет более "продвинутые" решения.

Я убедился в этом, тестируя iTriangle, который построен на монотонной триангуляции. Для замеров я использовал Earcut от MapBox - и C++ версию, и Rust-порт.

Результаты оказались предсказуемыми: Earcut стабильно выигрывал на простой геометрии и малом числе точек. Причём настолько уверенно, что я задумался: почему бы не встроить Earcut прямо в iTriangle?

Так и родилась идея: сделать мини-версию, заточенную только под одиночные контуры до 64 точек. С таким ограничением можно выжать максимум: обойтись без аллокаций, работать напрямую с битовой маской и попытаться обойти решение от MapBox.

Теория

Идея Earcut строится на простом наблюдении: в любом не самопересекающемся многоугольнике всегда найдутся три подряд идущие вершины, которые образуют так называемое ухо - внутренний треугольник, не содержащий других точек внутри.

Вся суть алгоритма - находить такие уши и последовательно их "отрезать", пока от многоугольника не останется последний треугольник.

Из этого подхода вытекает простая и красивая формула: каждый раз, отрезая ухо, мы теряем одну вершину, но получаем один треугольник. Алгоритм заканчивается, когда остаётся три вершины - это и есть последний треугольник.

В итоге: Tcount = N - 2

где Tcount - количество трегольников, N - количество вершин

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

Жадный Earcut

Проходим по контуру и перебираем все подряд идущие тройки точек. Для каждой тройки проверяем:

1. Образуют ли они треугольник в правильном порядке (против часовой стрелки).

2. Не содержит ли этот треугольник других вершин внутри.

Если оба условия выполняются - это ухо. Отрезаем его (удаляем центральную вершину) и продолжаем проход с обновлённым контуром.

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

Отсюда и получается асимптотика:

• O(N) - пройти по всем вершинам, чтобы найти одно ухо.

• O(N) - таких ушей нужно вырезать.

• O(N) - на проверку "ухо ли это" (нет ли точек внутри).

Итог: O(N³) - в худшем случае.

К слову, на практике всё не так печально. Большинство контуров ближе по форме к окружности, чем к спирали или другому "запутанному" многоугольнику. В таких случаях уши находятся значительно быстрее - зачастую на первом или втором проходе. Поэтому реальная асимптотика ближе к O(N²).

Большеухая реализация

Часто выгоднее отрезать сразу несколько треугольников, если это возможно. Такой подход позволяет сократить количество проверок на наличие внутренних точек. Суть такая вместо треугольника мы ищем выпуклый многоугольник.

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

Почему именно выпуклый многоугольник?

• Тривиальная триангуляция.

• Проверка на внутренние точки проще и быстрее (см. ниже).

Как только мы собрали выпуклый сегмент, возникает вопрос:

• Содержит ли он внутренние точки? Если нет - отрезаем.

• Если содержит - как разбить его так, чтобы избавиться от внутренних точек?

Проверка на пустоту

Есть два простых метода, которые можно использовать для проверки, лежит ли точка внутри многоугольника:

• Even-Odd (чет-нечет) - пускаем луч из точки и считаем количество пересечений с рёбрами. Если нечётное - точка внутри.

• Векторное произведение - для каждой стороны многоугольника смотрим векторное произведение стороны и вектора до точки. Если все произведения одного знака (например, положительные), значит точка внутри.

Векторное произведение чуть проще и позволяет закончить проверку досрочно если появляется противоречие.

Проще всего понять метод векторного произведения - через порядок точек треугольника.

• Если точка лежит внутри, то все векторные произведения (от стороны к точке) будут направлены в одну сторону - против часовой стрелки.

• Если снаружи - направление будет обратным.

Максимально допустимое ухо

Итак, мы нашли большое ухо - выпуклый многоугольник - и выяснили, что внутри него есть лишние точки.

Как найти ту часть, где нет внутренних точек?

Здесь важно понимать одно: первую вершину уха (то есть ту, с которой мы начинали) менять не нужно. Именно по ней идёт основной проход по контуру. Если ухо в текущем виде не подойдёт - всё равно цикл дойдёт до следующей вершины и начнёт попытку заново.

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

Как найти крайнюю точку?

Если провести вектора от начальной точки до всех внутренних точек, становится понятно: крайней будет та, чей вектор образует минимальный угол с направлением начального ребра

"Ближайший" вектор к начальному ребру

Считать угол напрямую — плохая идея:

• arccos - дорогая операция

• вычисления могут быть неточными из-за ограниченной точности float'ов

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

Пример

Пусть:

• - вектор начального ребра

• и вектора до внутренних точек.

Тогда:

cross_product =

Если cross_product > 0 то переходит в путем поворота против часовой стрелки, и как видно из рисунка он оказывается ближе к

Важное замечание

Все углы гарантировано < 180

Крайний вектор для замыкания уха

Итак, мы нашли "ближайший" вектор - тот, который образует минимальный угол с начальным ребром уха и указывает в сторону внутренней точки.

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

Сравнение выполняем по тому же принципу:

• Для каждого кандидата строим вектор от начальной вершины

• Сравниваем его с найденным крайним вектором через векторное произведение

• Если cross_product > 0 - всё ещё "внутри" угла, продолжаем

• Если cross_product < 0 - вышли за предел -> предыдущая вершина была последней допустимой

Ухо готово к ампутации.

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

Где можно ускорить процесс?

Мы начали алгоритм с поиска внутренних точек - и именно этот этап можно ускорить.

Вот две простые оптимизации:

• Фильтрация по bounding box
  Отбрасываем точки, которые явно лежат вне пределов уха.

• Фильтрация по первому треугольнику
  Сначала проверяем только базовый треугольник уха.
  Если уже он содержит внутренние точки - всё ухо можно отбросить. Особенно полезно на сложной геометрии.

Ускорение за счёт порядка обхода

Чтобы не проверять все точки на внутренность, поступим по другому.

Начнем жадно искать "ближайший" вектор - тот, что образует минимальный угол до крайней внутренней точки.

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

Если новая потенциальная точка образует более "ближайший" вектор:

• Проверяем, является ли она внутренней

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

• Если внешняя - просто пропускаем её

Проверку на внутренность лучше начинать с конца уха - так мы гарантированно сделаем не больше N тестов на наличие точки в треугольнике.

Scount < Tcount + Pcount < N

• Scount - количество тестов, содержит ли треугольник точку

• Tcount - количество треугольников

• Pcount - количество потенциальных внутренних точек

Оптимизация в действии.

• Голубой вектор — текущий "ближайший" вектор

• Зелёный вектор — кандидат, который мы рассматриваем

• Пунктирный голубой — новый "ближайший" вектор, если кандидат проходит проверку

Низкоуровневая оптимизация Earcut64

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

Но если длина контура ≤ 64, для эффективной навигации можно использовать - битовую маску, где каждый бит кодирует наличие точки по индексу.

Вот часть кода вспомогательных методов для навигации вперед:

impl Bit for u64 {
    #[inline(always)]
    fn ones_index_to_end(index: usize) ->; Self {
        // index is included
        debug_assert!(index <= 64);
        let zeros_count = index & 63;
        u64::MAX << zeros_count
    }

    #[inline(always)]
    fn next_wrapped_index(&self, after: usize) -> usize {
        debug_assert!(after <= 63);
        let front = self & u64::ones_index_to_end(after + 1);
        if front != 0 {
            front.trailing_zeros() as usize
        } else {
            self.trailing_zeros() as usize
        }
    }
}

Фильтрация внутренних точек

Имея маску контура, легко получить маску внутренних кандидатов:

let candidates = available & !ear_indices;

• available — все оставшиеся точки

• ear_indices — текущие точки, входящие в ухо

• candidates — точки, которые потенциально могут быть внутри

Почему это важно?

Потому что мы не аллоцируем память вообще.

Аллокация - дорогая операция. И чем меньше объём, тем дороже стоимость одного байта.
В нашем случае объём невелик (64 байта максимум), и поэтому цена аллокации высока.

И напоследок - одна мысль

Всё, что описано выше - работает на CPU, не требуя аллокации.

И тут возникает закономерный вопрос:

А можно ли реализовать, что-то подобное на GPU?
И если да - найдётся ли область, где это даст реальный профит?