A contact algorithm for partitioning N arbitrary sized objects

Abstract

A new spatial reasoning algorithm that can be used in multi-body contact detection is presented. The algorithm achieves the partitioning of N bodies of arbitrary shape and size into N lists in order O(N) operations, where each list consists of bodies spatially near to the target object. The algorithm has been tested for objects of arbitrary shape and size, in two and three dimensions. However, we believe that it can be extended to dimensions of four and higher. The algorithm (CGRID) is a binning algorithm that extends traditional binning algorithms so that the arbitrary sizes and shapes can be handled efficiently. The algorithm has applications in discrete element, finite element, molecular dynamics, meshles methods, and lattice-Boltzmann codes and also in domains such as path planning, target acquisition and general clustering problems.