Условие: На входе дан многоугольник (пятиугольник, рис. 1), заданный на плоскости точками (A, B, C, D, F) с известными координатами. Задана величина отрезка h, про который известно, что как минимум одна из граней многоугольника по длине более или равна 2h.

Для любого многоугольника существует только 2 боковых ребра и произвольное количество верхних и нижних граней.

Для боковых ребер существует параметр тесселяции t1, который определяет, на сколько отрезков может быть разбито боковое ребро, так чтобы отрезок AB был разделен на n равных отрезков длинной h ± t1 (количество отрезков на боковых ребрах должно быть строго одинаково). Аналогичный параметр t2 устанавливает значение для верхних и нижних ребер. При этом t1 и t2 могут быть не равны, а количество отрезков на верхних и нижних гранях может быть не равно.

Необходимо (рис. 2): Построить алгоритм, который бы разбивал грань многоугольника на четырехугольники с заданной длинной боковых ребер и допустимым отклонением. Алгоритм должен быть применим к разным типам многоугольников.




Цену и ограничение при разработке алгоритма можем обсудить.