Изменения

При проверке каждой вершину следует для начала проверить, является ли она выпуклой, в противном случае её просто нет надобности рассматривать в качестве уха. Это несложно сделать, воспользовавшись [[Предикат_"левый_поворот"|левым поворотом]]. "Ушную" проверку вершины будем осуществлять алгоритмом принадлежности точки <tex>n</tex>-угольнику (в нашем случае треугольнику). В качестве поддерживаемых структур удобно хранить два DCEL, в одном из которых отрезать уши, а в другом котором будем строить новые диагонали, и список вершин с двойными связями, аналогичный DCEL по построению. ==== Псевдокод ==== DCVL D1 //список вершин doubly connected vertex list по аналогии с DCEL DCEL D2 Construct(D1); Construct(D2); vertex v = random_vertex_of(D1); while size_of(D1) <tex> \varnothing </tex> 3 if IsConvex(v) //проверка на выпуклость for each Vertex v_i in D1 if v_i <tex> \varnothing </tex> v, v.prev(), v.next() //проверка всех вершин на and v_i <tex>\in </tex> Triangle(v, v.prev(), v.next()) //принадлежность треугольнику, //одной из вершин которого //является потенциальное ухо v.  edge e = new edge(v.prev, v.next) Insert e in D2; v = v.next Delete v.prev from D1

Изначально в многоугольнике содержится <tex>\mathcal{O}(n)</tex> ушей. Нетрудно понять, что в процессе отрезания ушей, смежные точки могут тоже становиться ушами. В результате триангуляции образуется <tex>n - 3</tex> диагонали, соответственно максимальное количество вершин, которые в процессе могут становиться ушами <tex>2n - 6</tex>. Итого общее количество ушей будет <tex>\mathcal{O}(n)</tex>. Определить, является ли вершина ухом можно за <tex>\mathcal{O}(n)</tex>, поскольку используется алгоритм определения принадлежности точки треугольнику — это <tex>\mathcal{O}(3)</tex>. Таким образом общий процесс отрезания ушей займёт <tex>\mathcal{O}(n^2)</tex>. Невыпуклых вершин всего <tex>\mathcal{O}(n)</tex>, каждая из них обрабатывается за константу, поэтому общее время для их обработки <tex>\mathcal{O}(n)</tex>. DCEL строится Списки рёбер и вершин строятся за линейное время, добавление ребра и удаление вершины в каждом из них работает за константу. Общее время <tex>\mathcal{O}(n^2)</tex>. Поскольку храним только два DCEL списка — память линейная.