184
правки
Изменения
→Наивный алгоритм
== Способы нахождения триангуляции ==
=== Наивный Примитивный алгоритм ===В произвольном <tex>n</tex>-угольнике всего <tex>n^2</tex> возможных вариантов построения диагоналей. За <tex>\mathcal{O}(n)</tex> проверим каждый из них. Для этого выясним:* пересекает ли данная диагональ многоугольник - находится за линейное время проверкой по всем рёбрам* принадлежит ли диагональ внутренней область многоугольника.Чтобы триангулировать многоугольник построить триангуляцию нужно найти <tex>n - 3</tex> диагоналей. В результате получается оценка <tex>\mathcal{O}(n^4)</tex>.
Для некоторых классов многоугольников оценку можно улучшить, например:
Если же многоугольник выпуклый, то достаточно лишь выбрать одну его вершину и соединить со всеми остальными, кроме его соседей. В итоге оценка <tex>\mathcal{O}(n)</tex>.
