С книгой Скорцова я конечно же знаком, во многих вещах она для меня стала путеводителем.
Да я сам хорошо разобрался с методом монотонного разбиения. И могу вам с ним помочь. По сути там та же идея, что и в вашей имплементации. Вы движетесь вдоль оси заметающей прямой и делаете суждение заканчивается, начинается или продолжается монотонный полигон. Сортировка начальных вершин и порождает N*log(N). Далее идет триангуляция, которая на практике в подавляющем случаи идет за линейное время и в очень редком случаи с откатом к предыдущей или далее вершине. Я к сожалению не могу оценить эту асимптотику (наверное это N*log(N), но доказать не могу). Для дальнейшего приведения к Делоне так же потребуется связать между собой треугольники, те что лежат на ребре разделяющем один монотонный полигон от другого.
У меня есть две имлементации swift и СSharp. Обе написаны в Data-oriented design, что делает их не много громоздкими для понимания. Так же мне почему то было проще рассуждать двигая заметающую прямую по оси oX. Swift версия использует ARC (умный подсчет ссылок), а СSharp версия полагается на ручной механизм управления памятью. Еще стоит наверное сказать, что в swift версии я начал добавлять поддержку дополнительных точек. Точки которые лежат внутри полигона, и обычно нужны для более «красивой» триангуляции.
Спасибо за статью. Больше всего понравилась в ней описание алгоритма триангуляции. С этим методом я не был знаком. Вы случайно не сравнивали этот метод с другими алгоритмами триангуляции? Например, с методом монотонных полигонов. Интересуют полный процесс триангуляции от построения базовой к последующему приведению Делоне. Как я сам вижу оба алгоритма имеют асимптотику базовой триангуляции (без Делоне) n*Log(n). Но возможно у вашего алгоритма базовая триангуляция ближе к Делоне. Плюс у монотонного метода есть шаг с разбиением на полигоны. С другой стороны в вашем алгоритме присутствует излишняя триангуляция «вспомогательных» треугольников. Но это все в теории, а хотелось бы практическую скорость сравнения. Еще из плюсов вашего подхода, как вы сами отметили устойчивость алгоритма к петлям.
Да я сам хорошо разобрался с методом монотонного разбиения. И могу вам с ним помочь. По сути там та же идея, что и в вашей имплементации. Вы движетесь вдоль оси заметающей прямой и делаете суждение заканчивается, начинается или продолжается монотонный полигон. Сортировка начальных вершин и порождает N*log(N). Далее идет триангуляция, которая на практике в подавляющем случаи идет за линейное время и в очень редком случаи с откатом к предыдущей или далее вершине. Я к сожалению не могу оценить эту асимптотику (наверное это N*log(N), но доказать не могу). Для дальнейшего приведения к Делоне так же потребуется связать между собой треугольники, те что лежат на ребре разделяющем один монотонный полигон от другого.
У меня есть две имлементации swift и СSharp. Обе написаны в Data-oriented design, что делает их не много громоздкими для понимания. Так же мне почему то было проще рассуждать двигая заметающую прямую по оси oX. Swift версия использует ARC (умный подсчет ссылок), а СSharp версия полагается на ручной механизм управления памятью. Еще стоит наверное сказать, что в swift версии я начал добавлять поддержку дополнительных точек. Точки которые лежат внутри полигона, и обычно нужны для более «красивой» триангуляции.