Какие существуют методы разбиения невыпуклых четырехугольников на треугольники?

Один из методов разбиения невыпуклых четырехугольников на треугольники — алгоритм триангуляции Делоне методом заметающей прямой. 2

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

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