Как то раз, мне нужно было найти решение задачи обхода многоугольника. Долго искал в интернете, но так и не нашел нужного алгоритма. Возможно не правильно искал. Поэтому придумал свой алгоритм. В данном алгоритме для соединения прямых используются кривые Безье.
Собственно сам алгоритм.
1. Создадим многоугольник из заданных точек.
2. Все прямые многоугольника сохраняем в отдельный массив.
3. В многоугольнике находим прямую с максимальной длиной, эта прямая берется за основу для построения ограничивающего прямоугольника с минимальной площадью.
4. Повернем многоугольник так, чтобы прямая с максимальной длиной имела угол 0 градусов.
5. Создадим прямоугольник, который ограничивает многоугольник.
6. По всей площади отграничивающего прямоугольника создадим вертикальные параллельные прямые идущие от верхней грани прямоугольника до нижней его грани.
7. Обрезаем полученные параллельные прямые так, что бы каждая прямая проходила от одной грани многоугольника до противоположной грани.
8*. Удаляем из сцены предыдущей траектории, если она была ранее создана.
9. Соединяем параллельные прямые с кривыми Безье, что бы в результате образовалась одна сплошная траектория.
10. Удаляем ограничивающий прямоугольник. Поворачиваем многоугольник и получившуюся траекторию (все параллельные прямые соединенные с кривыми Безье) на исходный угол.
11. Добавляем на сцену получившуюся траекторию
Этот алгортм реализован на C++/Qt в моем проекте, который можно посмотреть на гитхабе функция createPoly.
Комментариев нет:
Отправить комментарий