A simple linear algorithm for intersecting convex polygons

Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review


Let P and Q be two convex polygons with m and n vertices, respectively, which are specified by their cartesian coordinates in order. A simple O(m+n) algorithm is presented for computing the intersection of P and Q. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.

Original languageEnglish (US)
Pages (from-to)118-123
Number of pages6
JournalThe Visual Computer
Issue number2
StatePublished - Aug 1985


  • Algorithms
  • Complexity
  • Computational geometry
  • Convex polygons
  • Intersection

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'A simple linear algorithm for intersecting convex polygons'. Together they form a unique fingerprint.

Cite this