Какой оптимальный алгоритм нахождения суммы Минковского?
Приветствую!
В общем сабж. Находить нужно много и часто. Сейчас используется встроенная в ClippingLib но уже для 300 точек считает порядка 4 секунд - очень долго.
Что дано: Многоугольники не самопересекаются, выпуклые и не выпуклые.
Помимо алгоритма в английской Википедии нашёл ещё описание вот такого:
Находим центр масс каждого, сдвигаем каждый так, что бы центр масс оказался в начале координат (пусть вектора сдвига А1 и А2), проводим лучи из начала координат к вершинам каждого многоугольника. Находим точки пересечения данных лучей и многоугольников, векторно складываем все пары точек на всех лучах, что бы найти вершины искомого многоугольника, сдвигаем получившийся многоугольник на вектор (-А1,-А2). Всё.
Подскажите, насколько этот алгоритм верный? Будет ли он быстрее "классического"? Может есть ещё более оптимальный?
Алгоритм неясный. Вот два впуклых многоугольника, приведённых к началу координат - как разруливать "точки пересечения данных лучей и многоугольников"?
Есть ощущение, что можно нарожать неодносвязных областей - и что делать с этим головняком?
Спасибо. Добавлю, что нужно после нахождения точек найти оболочку и лишь потом переносить обратно.
Но Вы правы, алгоритм не работает для впуклых многоугольников, нужно разбивать на выпуклые сначала.
Для двух невыпуклых многоугольников с n и m вершинами сложность вычесления (nm)^2. Для 300 вершин - это уже порядка нескольких секунд. Можно сильно напрячься и ускорить на несколько процентов. Но сильно быстрее вы ничего не найдете.
Простой
Средний