Detecting the Intersection of Convex Objects in the Plane
Report ID: TR-231-89Author: Souvaine, Diane L. / Dobkin, David P.
Date: 1989-10-00
Pages: 29
Download Formats: |PDF|
Abstract:
Numerous applications require intersection detection. Many algorithms have been developed for telling whether two polygons intersect. We have extended one such algorithm to allow us to determine in C log n operations whether two convex planar regions intersects. Our algorithm is significant because it can be presented as a combination of two ideas. First, there is a revision of previous algorithms for detecting whether two convex polygons intersect. Second, there is a general method for transforming algorithms which work for polygons to make them work for piecewise curved boundaries. The constant C depends strictly upon the complexity of the piecewise curves. The algorithms presented here have been implemented and details of their implementation are included.