ifsmirnov's blog

By ifsmirnov, 13 years ago, In Russian

Пытаюсь разобраться, как считать сумму Минковского двух выпуклых многоугольников. Нашел два алгоритма.

Первый, с английской википедии - отсортировать все ребра двух многоугольников по полярному углу и последовательно сцепить в ломаную; утверждается, что многоугольник, ограниченный ей, и будет искомой суммой.
Второй некоторое время назад мне рассказывали на лекции, но, видимо, я упустил какие-то детали. Перенесем центры масс обоих многоугольников в начало координат. Проведем всевозможные лучи из начала координат в вершины многоугольника. Для каждого луча возьмем векторную сумму точек пересечения его с обоими многоугольниками, это будет какая-то вершина их суммы Минковского.

Но ни один из них не работает так, как бы мне хотелось.
Что делает первый, вообще неясно. Подразумевается, что он работает только для контуров? 
Во втором я не понимаю, почему при переносе многоугольников в начало координат нужно выбирать именно центр масс, а не произвольную точку внутри (или это не так?) Вроде бы в алгоритме это никак не используется.

Ну и наконец один вопрос из практики. Есть у нас два совпадающих квадрата с вершинами
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
Снова считаем сумму Минковского вторым методом (не передвигая центры тяжести в начало координат) и получаем какой-то непонятный восьмиугольник. Значит, центр тяжести все-таки играет роль? Но если мы добавим несколько фиктивных точек на серединах сторон, то все опять съедет и появятся подобные баги.

Что я делаю не так? Буду благодарен, если поможете разобраться.
  • Vote: I like it
  • +6
  • Vote: I do not like it