1

Тема: Сумма Минковского

Недавно узнал про эту интересную штуку. Писать статью всё равно не буду (кода нет, да и времени нет), поэтому здесь.

Сумма Минковского для двух геометрических фигур - это фигура, составленная из всевозможных точек вида a+b, где точка a принадлежит первой фигуре, b - второй. Понятно, что сумму можно применять вообще к любым двум множествам.

Интересно то, что эту сумму можно вычислять даже за линейное время, если входные многоугольники - выпуклые. Как - не знаю, предлагаю читателям подумать big_smile Эта задача, оказывается, даже была достаточно много лет назад на IOI wink

А интереснее всего то, что эту на первый взгляд абстрактную штуку можно вполне практично применять: оказывается, так можно получить критерий пересечения многоугольников. Действительно, если сумма Минковского содержит точку (0,0), то первый многоугольник содержит точку (x,y), а второй - (-x,-y). Стало быть, если у одного из них изначально поменять знак всех координат, то точка (0,0) в сумме Минковского сигнализирует о том, что многоугольники имеют общую точку.

Более того, если сдвинуть один многоугольник на некоторый вектор, то и сумма сдвинется на тот же вектор. Таким образом, мы сразу получаем решение такой задачи: найти вектор (и даже множество всех таких векторов!), что при сдвиге одного многоугольника он только лишь касается другого.

2

Re: Сумма Минковского

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