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