Ear clipping (отсечение ушей)
Простой алгоритм триангуляции многоугольника: он раз за разом отсекает «уши» — выпуклые углы, чей треугольник пуст.
«Ухо» — это три подряд идущие вершины, где средняя выпуклая, а образованный ими треугольник не содержит других вершин многоугольника. Алгоритм находит ухо, отсекает его как треугольник и повторяет, пока не останется один треугольник.
Сложность O(n²), зато реализуется легко и справляется с любыми простыми многоугольниками, в том числе вогнутыми и с отверстиями (через мосты). Название ввёл Гэри Мейстерс в 1975 году. Это вариант по умолчанию, когда нужно превратить 2D-контуры — шрифты, элементы интерфейса, навигационные полигоны — в треугольники, которые умеет рисовать GPU.