Изменения
→Идея
Рассмотрим все вершины многоугольника, и где возможно, будем отрезать уши.
Будем рассматривать вершины многоугольника в порядке обхода. Если вершина Индексирование вершин для удобства будем вести по модулю <tex>v_in</tex> является ухом, соединим смежные с ней вершины т.е. <tex>v_{i+-1} = v_{n-1}</tex> и <tex>v_{i-1}v_0 = v_n</tex>. Индексирование вершин ведётся по модулю Если вершина <tex>nv_i</tex>является ухом, т.е. соединим смежные с ней вершины <tex>v_{-1} = v_{n-i+1}</tex> и <tex>v_0 = v_nv_{i-1}</tex>. В противном случае переходим к следующей вершине в порядке обхода.
== Источники ==
* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Chapter 3: Polygon Triangulation: pp.45–61.
