Триангуляцией полигона называется декомпозиция полигона в набор треугольников. Триангуляция часто используется для упрощения решения задачи в пределах области со сложной конфигурацией, и сведения ее к более простой задаче в пределах треугольника, поскольку треугольник относится к простейшей области и в этом случае задачу можно решить гораздо проще. Например, для определения, лежит ли точка внутри невыпуклого полигона, можно осуществить триангуляцию полигона и ответить "да" только в том случае, если точка принадлежит по крайней мере хотя бы одному треугольнику. Или при анализе сложных поверхностей, расположенных в пространстве, можно эти поверхности аппроксимировать сеткой треугольников, проанализировать которые значительно легче. Пожалуй, самым простым алгоритмом триангуляции является метод Разделяй-и-властвуй. Требуется O(nlogn) операций в среднем и O(n2) - в худшем случае. Многоугольник рекурсивно делится на части путем проведения хорды вплоть до треугольников. Более сложные и эффективные алгоритмы(простейшие из таковых) используют понятие монотонных полигонов. Общая стратегия триангуляции состоит из двух этапов: Декомпозиция полигона на монотонные части. Триангуляция монотонных частей за общее время О(n). Быстрее, чем за O(n) триангуляцию осуществить нельзя, поэтому общее время задается первой частью алгоритма. Довольно старый, но весьма эффективный подход заключается в декомпозиции на монотонные полигоны методом сканирующей линии. Недавно появился гораздо более эффективный алгоритм Зейделя, простой и работающий за почти линейное время. Существует его реализация, написанная Narkhede и Manocha. В их коде есть и общая функция триангуляции, делающая второй шаг алгоритма. Кроме того (!) их код поддерживает полигоны с дырами, чего не скажешь о методах выше.  8  Комментарии к статье  8 8  Обсудить в чате