Задача: разбить произвольный многоугольник на треугольники.
Что нужно.
Теперь сам алгоритм.
Подготовка рабочих объективов.
Результатом работы должен быть список треугольников (result), потому создаем пустой список. Рабочий двунаправленный замкнутый список (points), представляющий многоугольник.
Перед стартом просчитываем углы для всех точек многоугольника.
Выбираем любую точку многоугольника как «рабочую» (p(i)).
Теперь пара слов об оптимизации алгоритма.
На втором этапе выбирается треугольник с минимальной разницей между минимальным и максимальным углом для того, чтобы треугольник был максимально подобный к правильному, иногда это важно. Если же вам нет разницы как выглядит треугольник — тогда можно не создавать временный список треугольников, а выбрать первый из трех возможных треугольников который не содержит внутри себя другую точку многоугольника и угол, который образует средняя точка треугольника в многоугольнике меньше 180 градусов. Такое упрощение значительно снизит вычислительные затраты.
Еще, если уверены, что многоугольник выпуклый — тогда не нужно проверь содержит ли треугольник другие точки многоугольника.
П.С. Я не встречал такой алгоритм на просторах инета, хотя и уверен, что что-то подобное уже есть.
Что нужно.
- Клас, что-то наподобие списка, где можно двигаться вперед-назад и конец соединен с началом. То есть замкнутый круг, элементами которого будут объекты описаны пунктом ниже.
- Клас для представления точки. В нем, как полагается, должны быть координаты х и у. Так же еще одно поле в котором записано значение угла соответствующего этой точке в многоугольнике
- Функция, на вход которой идут два векторы, а на выход — угол между ними
- Функция, на вход которой идет точка и треугольник, на выход — признак, лежит ли точка внутри треугольника.
Теперь сам алгоритм.
Подготовка рабочих объективов.
Результатом работы должен быть список треугольников (result), потому создаем пустой список. Рабочий двунаправленный замкнутый список (points), представляющий многоугольник.
Перед стартом просчитываем углы для всех точек многоугольника.
Выбираем любую точку многоугольника как «рабочую» (p(i)).
- Создаем пустой список для хранения временных треугольников.
Если точка слева от «рабочий» (p(i)->left) имеет угол меньше чем 180 градусов и треугольник (p(i), p(i)->left, p(i)->left->left) не содержит внутри себя других точек многоугольника — заносим этот треугольник в наш временный список.
Если точка справа от «рабочий» (p(i)->right) имеет угол меньше чем 180 градусов и треугольник (p(i), p(i)->right, p(i)->right->right) не содержит внутри себя других точек многоугольника — заносим этот треугольник в наш временный список.
Если «рабочая» точка (p(i)) имеет угол меньше чем 180 градусов и треугольник ( p(i)->left, p(i),p(i)->right) не содержит внутри себя других точек многоугольника — заносим этот треугольник в наш временный список. - Если временный список не содержит треугольников — выбираем вместо «рабочий», точку слева от нее и возвращаемся к первому пункту.
Если содержит — выбираем треугольник с минимальной разницей между минимальным и максимальным углом (нужно пересчитать значение углов), заносим его в список result, удаляем из points среднюю точку из треугольника который выбрали а соседним точкам от нее (в points) пересчитываем значения углов, первую точку выбираем в качестве «рабочей» (p(i)).Если в points осталось только две точки — прекращаем работу, список треугольников содержится в res, иначе возвращаемся к первому пункту.
Теперь пара слов об оптимизации алгоритма.
На втором этапе выбирается треугольник с минимальной разницей между минимальным и максимальным углом для того, чтобы треугольник был максимально подобный к правильному, иногда это важно. Если же вам нет разницы как выглядит треугольник — тогда можно не создавать временный список треугольников, а выбрать первый из трех возможных треугольников который не содержит внутри себя другую точку многоугольника и угол, который образует средняя точка треугольника в многоугольнике меньше 180 градусов. Такое упрощение значительно снизит вычислительные затраты.
Еще, если уверены, что многоугольник выпуклый — тогда не нужно проверь содержит ли треугольник другие точки многоугольника.
П.С. Я не встречал такой алгоритм на просторах инета, хотя и уверен, что что-то подобное уже есть.