В настоящее время наиболее практичные алгоритмы триангуляции многоугольников состоят из двух этапов. На первом этапе исходный многоугольник разбивается на монотонные многоугольники, а на втором этапе полученные многоугольники триангулируются за линейное время. Функция trianSweepLine использует на первом этапе алгоритм "заметающей прямой". В книге Майкла Ласло "Вычислительная геометрия и компьютерная графика на С++" есть описание такого двухпроходного алгоритма, и я сначала в 2015 году сделал похожий, но в 2018 году придумал уже однопроходной, к тому же я обобщил его на случай многоугольников с дырками: SuiteRef<Set3<nat>> & trianSweepLine ( CCArrRef<Vector2d> & vert, SuiteRef<Set3<nat> > & res );
SuiteRef<Set3<nat>> & trianSweepLine ( CCArrRef<nat> & cntr,
CCArrRef<Vector2d> & vert, SuiteRef<Set3<nat> > & res );
Здесь cntr - это количества вершин многоугольников, vert - общий массив всех вершин, res - треугольники.
Внешний многоугольник должен иметь обход вершин против часовой стрелки, а внутренние - по часовой.
Порядок перечисления многоугольников произвольный.
В результате построения триангуляции этим алгоритмом могут появляться очень узкие треугольники. Чтобы избавится от них можно применить функцию rebuildDelauney, которая получает на входе какую-то триангуляцию и переделывает её в триангуляцию Делоне для многоугольников (максимизирует минимальный угол треугольников): ArrRef<Set3<nat>> & rebuildDelauney ( CCArrRef<Vector2d> & vert, ArrRef<Set3<nat>> & res ) Эта функция использует шаблон maxL1. В моих экспериментах функция rebuildDelauney работала медленее функции trianSweepLine в среднем в 3 раза. Описание класса Vector2d смотрите в разделе Вектора на плоскости.
|