Efi Fogel

2 Dimensional Collision Detection


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 time-complexities mentioned above, but rather follow approaches that can be generalized to handle the 3D case. more


[DHK93] D. Dobkin, J. Hershberger, D. Kirkpatrick, and S. Suri. Computing the Intersection-Depth of Polyhedra. Algorithmica,9:518-533,1993.
[GS88] L. J. Guibas and J. Stolfi. Ruler, Compass and Computer: the Design and Analysis of Geometric Algorithms. In R. A. Earnshaw, editor, Theoretical Foundations of Comput. Graph. and CAD, Volume 40 of NATO ASI Series F, pages 111-165. Springer-Verlag, 1988.
Last modified: December 19 2004.