Изменения

Рассмотрим все вершины многоугольника<tex>P</tex>, и где возможно, будем отрезать ушидо тех пор, пока <tex>P</tex> не станет треугольником.

Будем рассматривать вершины многоугольника в порядке обхода. Индексирование вершин для удобства будем вести по модулю <tex>n</tex>, т.е. <tex>v_{-1} = v_{n-1}</tex> и <tex>v_0 = v_n</tex>. Если вершина <tex>v_i</tex> является ухом, построим диагональ <tex>v_{i+1}v_{i-1}</tex> и отрежем треугольник <tex>\Delta v_{i-1}v_iv{i+1}</tex> от <tex>P</tex>. В противном случае переходим к следующей вершине в порядке обхода. ==== Алгоритм ====При проверке каждой вершину следует для начала проверить, является ли она выпуклой, в противном случае просто нет надобности рассматривать в качестве уха. Это несложно сделать, воспользовавшись [[Предикат_"левый_поворот"|левым поворотом]]. "Ушную" проверку вершины будем осуществлять алгоритмом принадлежности точки <tex>n</tex>-угольнику (в нашем случае треугольнику).