PavelK
@PavelK

Какой оптимальный алгоритм нахождения суммы Минковского?

Приветствую!
В общем сабж. Находить нужно много и часто. Сейчас используется встроенная в ClippingLib но уже для 300 точек считает порядка 4 секунд - очень долго.

Что дано: Многоугольники не самопересекаются, выпуклые и не выпуклые.

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

Подскажите, насколько этот алгоритм верный? Будет ли он быстрее "классического"? Может есть ещё более оптимальный?
  • Вопрос задан
  • 80 просмотров
Пригласить эксперта
Ответы на вопрос 2
longclaps
@longclaps
Алгоритм неясный. Вот два впуклых многоугольника, приведённых к началу координат - как разруливать "точки пересечения данных лучей и многоугольников"?
5dae862d0d14e749941765.png
Есть ощущение, что можно нарожать неодносвязных областей - и что делать с этим головняком?
Ответ написан
wataru
@wataru
Для двух невыпуклых многоугольников с n и m вершинами сложность вычесления (nm)^2. Для 300 вершин - это уже порядка нескольких секунд. Можно сильно напрячься и ускорить на несколько процентов. Но сильно быстрее вы ничего не найдете.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Click Санкт-Петербург
от 180 000 до 250 000 руб.
Chudo Москва
от 90 000 до 180 000 руб.
АО «НИИМЭ» Зеленоград
от 100 000 до 170 000 руб.
18 нояб. 2019, в 12:09
7000 руб./за проект
18 нояб. 2019, в 10:48
3000 руб./за проект