Пытаюсь разобраться, как считать сумму Минковского двух выпуклых многоугольников. Нашел два алгоритма.
Первый, с английской википедии - отсортировать все ребра двух многоугольников по полярному углу и последовательно сцепить в ломаную; утверждается, что многоугольник, ограниченный ей, и будет искомой суммой.
Второй некоторое время назад мне рассказывали на лекции, но, видимо, я упустил какие-то детали. Перенесем центры масс обоих многоугольников в начало координат. Проведем всевозможные лучи из начала координат в вершины многоугольника. Для каждого луча возьмем векторную сумму точек пересечения его с обоими многоугольниками, это будет какая-то вершина их суммы Минковского.
Но ни один из них не работает так, как бы мне хотелось.
Что делает первый, вообще неясно. Подразумевается, что он работает только для контуров?
Во втором я не понимаю, почему при переносе многоугольников в начало координат нужно выбирать именно центр масс, а не произвольную точку внутри (или это не так?) Вроде бы в алгоритме это никак не используется.
Ну и наконец один вопрос из практики. Есть у нас два совпадающих квадрата с вершинами
2 -2
2 2
-2 2
2 2
Их сумма Минковского, если считать вторым методом - ожидаемый квадрат со стороной 8. Теперь сдвинем квадраты (при этом сумма Минковского тоже должна лишь сдвинуться на некоторый вектор!).
3 -1
3 3
-1 3
-1 -1
1 -2
1 2
-3 2
-3 -2
Снова считаем сумму Минковского вторым методом (не передвигая центры тяжести в начало координат) и получаем какой-то непонятный восьмиугольник. Значит, центр тяжести все-таки играет роль? Но если мы добавим несколько фиктивных точек на серединах сторон, то все опять съедет и появятся подобные баги.
Что я делаю не так? Буду благодарен, если поможете разобраться.
Пример применения для двух квадратов из поста: (-2, -2) -- (-2, +2) -- (+2, +2) -- (+2, -2) -- cycle.
Рёбра каждого квадрата имеют координаты (4, 0), (0, 4), (-4, 0), (0, -4).
Значит, получается многоугольник с рёбрами (8, 0), (0, 8), (-8, 0), (0, -8).
Теперь его надо построить из нужной точки, скажем, из суммы первых вершин каждого квадрата как векторов, то есть (-4, -4), и начиная с правильного ребра.
Во втором способе как минимум неверное предположение: центр масс многоугольника, если это не треугольник, не обязательно получается как среднее арифметическое отдельно по x и по y всех вершин.
На сторону треугольника ставим точку — четвёртую вершину. Реальный центр масс не изменился. А посчитанный как среднее арифметическое вершин сместился к поставленной точке.
Если не нравится, что настоящих вершин всё ещё три — двигаем точку на eps наружу так, чтобы четырёхугольник стал строго выпуклым.
стороннормалей). Найдем во втором полигоне вершину, самую далекую в этом направлении, то есть имеющую максимальное скалярное произведение с этим вектором. Сложим эти две вершины, добавим в ответ. Поменяем местами полигоны и сделаем то же самое. Получим в ответе множество вершин. Если идти везде по порядку, то можно во-первых искать соответствующую вершину бегущим указателем, во-вторых делать оба симметричных случая сразу (то есть не менять местами полигоны и не запускать второй раз), в-третьих сразу получать вершины в порядке обхода. Получается метод с той же идеей, что и первый, но сложнее в реализации.