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