Введение
Сумма векторных множеств A и B вычисляется путем прибавления каждого вектора из A к каждому вектору из B.
В геометрии сумма Минковского двух множеств позиционных векторов A и B в евклидовом пространстве формируется путем прибавления каждого вектора из A к каждому вектору из B:
Разность Минковского (также вычитание Минковского, разложение Минковского или геометрическая разность) является соответствующей обратной операцией, результатом которой является множество, которое при суммировании с B позволяет восстановить A. Она определяется как дополнение к сумме Минковского дополнения A и отражения B относительно начала координат. Это определение обеспечивает симметричные отношения между суммой и разностью Минковского. Следует отметить, что последовательное применение суммы и разности с B не всегда эквивалентно. Сумма может заполнять пробелы, которые разность не может восстановить, а разность может удалять небольшие изолированные области, которые сумма не может создать из ничего. В 2D обработке изображений сумма и разность Минковского известны как расширение и сужение (эрозия). Альтернативное определение разности Минковского иногда используется для вычисления пересечения выпуклых фигур. Оно не эквивалентно предыдущему определению и не является обратной операцией сложения. Вместо этого оно заменяет векторное сложение в сумме Минковского векторным вычитанием. Если две выпуклые фигуры пересекаются, результирующее множество будет содержать начало координат. Эта концепция названа в честь Германа Минковского.
Приложения
Добавление Минковского играет центральную роль в математической морфологии. Оно возникает в парадигме «кисть и штрих» двумерной компьютерной графики (с различными применениями, в частности, у Дональда Э. Кнута в Metafont) и как операция обхода твердым телом в трехмерной компьютерной графике. Также было показано, что оно тесно связано с расстоянием перемещения Земли и, как следствие, с оптимальным транспортом.
Планирование движения
Суммы Минковского используются в задачах планирования движения объекта среди препятствий. Они применяются для вычисления пространства конфигураций, представляющего собой множество всех допустимых положений объекта. В простой модели поступательного движения объекта в плоскости, где положение объекта однозначно определяется положением его фиксированной точки, пространство конфигураций является суммой Минковского множества препятствий и самого объекта, расположенного в начале координат и повернутого на 180 градусов.
Машиностроение с цифровым управлением (NC)
При обработке с ЧПУ программирование инструмента использует тот факт, что сумма Минковского режущей части с ее траекторией определяет форму выреза в материале.
3D-моделирование твердых тел
В OpenSCAD суммы Минковского используются для создания очертания фигуры с помощью другой фигуры, формируя объединенную фигуру из обеих.
Теория агрегации
Суммы Минковского также часто используются в теории агрегирования, когда отдельные объекты, подлежащие агрегированию, характеризуются посредством множеств.
Обнаружение столкновения
Суммы Минковского, и в особенности разности Минковского, часто используются совместно с алгоритмами GJK для вычисления обнаружения столкновений выпуклых оболочек в физических движках.
Два выпуклых многоугольника в плоскости
Для двух выпуклых многоугольников и в плоскости с и вершинами, их сумма Минковского является выпуклым многоугольником с не более чем + вершинами и может быть вычислена за время O( + ) с помощью очень простой процедуры, которую можно неформально описать следующим образом. Предположим, что ребра многоугольников заданы и направление, например, против часовой стрелки, вдоль границы многоугольника. Тогда легко заметить, что эти ребра выпуклого многоугольника упорядочены по полярному углу. Объединим упорядоченные последовательности направленных ребер из и в одну упорядоченную последовательность. Представим, что эти ребра – это твердые стрелки, которые можно свободно перемещать, сохраняя их параллельными исходному направлению. Собираем эти стрелки в порядке последовательности, прикрепляя хвост следующей стрелки к головке предыдущей стрелки. Оказывается, что полученная ломаная линия на самом деле является выпуклым многоугольником, который и представляет собой сумму Минковского и .
Другое
Если один многоугольник выпуклый, а другой — нет, сложность их суммы Минковского составляет O(nm). Если оба многоугольника невыпуклые, сложность их суммы Минковского составляет O((mn)2).