Detecting the intersection of convex objects in the plane

David Paul Dobkin, Diane L. Souvaine

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

Numerous applications require intersection detection. Many algorithms have been developed for telling whether two convex polygons intersect. We have revised and generalized one such algorithm to allow us to detect in C log n operations the intersection of two convex planar regions with piecewise curved boundaries, where n represents the number of curved segments. The constant C depends strictly upon the complexity of the n curved segments. The algorithms presented here have been implemented and details of their implementation are included.

Original languageEnglish (US)
Pages (from-to)181-199
Number of pages19
JournalComputer Aided Geometric Design
Volume8
Issue number3
DOIs
StatePublished - Jan 1 1991

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Detecting the intersection of convex objects in the plane'. Together they form a unique fingerprint.

  • Cite this