


2 Dimensional Collision Detection 

Download mink2d 
Given two convex polygons with m and n vertices respectively, it was shown that detecting collision and computing directional penetration depth can be done in optimal time O(log m + log n) [GS88], and that the (absolute) penetration depth can be computed in O(log(m + n)) time using the Minkowski sum computed a priori [DHK93]. It is well known that the Minkowski sum in this case consists of m + n edges when there are no degeneracies, and can be computed in linear time simply by merging the edges in slope order. We have implemented a few exact routines that answer the collision detection, directional penetration depth, and separation distance queries. These implementations are not necessarily characterized with the optimal asymptotic timecomplexities mentioned above, but rather follow approaches that can be generalized to handle the 3D case. more References
 
Last modified: December 19 2004. 