학술논문
A Review of Methods to Compute Minkowski Operations for Geometric Overlap Detection
Document Type
Periodical
Author
Source
IEEE Transactions on Visualization and Computer Graphics IEEE Trans. Visual. Comput. Graphics Visualization and Computer Graphics, IEEE Transactions on. 27(8):3377-3396 Aug, 2021
Subject
Language
ISSN
1077-2626
1941-0506
2160-9306
1941-0506
2160-9306
Abstract
This article provides an extensive review of algorithms for constructing Minkowski sums and differences of polygons and polyhedra, both convex and non-convex, commonly known as no-fit polygons and configuration space obstacles. The Minkowski difference is a set operation, which when applied to shapes defines a method for efficient overlap detection, providing an important tool in packing and motion-planning problems. This is the first complete review on this specific topic, and aims to unify algorithms spread over the literature of separate disciplines.