Количество баллов: 10 баллов
Срок сдачи: конец октября.
Используя алгоритм триангуляции разбить невыпуклый многоугольник на треугольники.
Варианты
1. Подсчитать площадь невыпуклого многоугольника.
2. Проверить принадлежит ли точка невыпуклому многоугольнику.
3. Закрасить треугольник внутри многоугольника, в котором была отмечена точка.
4. Закрасить все треугольники внутри многоугольника, исключив треугольник с отмеченной точкой.
5. Закрасить первый и последний треугольник, которые были получены при триангуляции многоугольника.
6. Пронумеровать треугольники в том порядке, как производится разбиение.
7. Начать разбиение многоугольника на треугольники с вершины, имеющей наименьшую координату по оси X и по оси Y.
8. Провести разбиение многоугольника на треугольники выбрав направление против часовой стрелки.
9. Закрашивать треугольники, полученные при разбиении, через один. Первый закрашиваем, второй - нет и т.д.
Материалы по теме:
1. Триангуляция многоугольника
2. Литература со страницы "Вычислительная геометрия"
