Efficient polygonal intersection determination with applications to robotics and vision

Abstract

Several robotic and computer vision applications depend upon the efficient determination of polygonal self- and mutual-intersection checking. The commonly used algorithms for intersection checking rely upon static geometric primitives, such as lines and vertices. When these geometric primitives are dynamic, that is moving or changing shape, these algorithms become inefficient due to repeated actions that do not utilize topological features of the primitives. In this paper we present a novel algorithm for line segment intersection checking that builds a query structure and then updates the structure using previously computed topological data. We exploit the fact that the amount of model deformation is limited during any single iteration, yielding a relatively small bookkeeping cost to maintain the query structure. The result is an algorithm whose asymptotic runtime complexity in the expected case is better than competing methods. We then suggest an extension of this work into higher dimensions (polytope intersection for 3D and higher).