A LINEAR COMPLEXITY INTERSECTION ALGORITHM FOR DISCRETE ELEMENT SIMULATION OF ARBITRARY GEOMETRIES

We present an algorithm for contact resolution that is valid for a wide variety of polygonal two dimensional shapes and is of linear computational complexity. The algorithm is designed for use in discrete element analysis of granular and multibody systems exhibiting discontinuous behaviour. Contact detection usually consists of a spatial sorting phase and a contact resolution phase. The spatial sorting phase seeks to avoid an all-to-all body comparison by culling the number of objects which are potential contactors of a given object. The contact resolution phase resolves the details of the contact between two given objects. The algorithm presented here (called DFR) addresses the contact resolution phase and is applicable to convex geometries and to a restricted set of concave geometries. Examination of the algorithm establishes an upper bound linear computational complexity, of order O(N), with respect to the number of points (N) used to define the object boundary. The DFR algorithm is combined with a modified heapsort algorithm for spatial sorting of M bodies which has complexity O(M log M) and is applied to a baseline granular simulation problem to test its efficiency.