A Narrow-Phase Collision Detection Algorithm Based on Contact Theory in 2D

Collision detection is the core of collision analysis which is a vital fundamental work in computational particle mechanics. Collision detection algorithms can be divided into direct and indirect algorithms. Among them, the indirect algorithms transform the collision detection between two 2D objects into the position judgment of a reference point and a 2D object by constructing the no-fit polygon (NFP). However, the existing NFP algorithms are either not suitable for concave objects, or their time complexity is too high. This has hindered the development of indirect algorithms. Almost unknown to researchers interested in NFP, in the field of discontinuous mechanics calculation, there exists an ‘entrance block’ in Contact theory. Since NFP is the outline of the entrance block, the entrance block also has the potential to develop into a collision detection algorithm like NFP. The entrance block is suitable for arbitrary objects but ignores the rotation in each time step, which restricts it from becoming a collision detection algorithm. In this study, we improve this limitation and propose a 2D collision detection algorithm that is suitable for arbitrary objects. This algorithm can distinguish collision and contact, which reduces the calculation of late collision response. In addition, the algorithm has the potential to be transformed into a continuous algorithm and a new narrow-phase 3D collision detection algorithm. Finally, we propose a potential NFP algorithm that can be applied to arbitrary objects, which has an important influence on many NFP-related fields like computer graphics, operations research, computational mechanics, etc.