A simple linear algorithm for intersecting convex polygons

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume1
Issue number2
DOIs
StatePublished - Aug 1985

Keywords

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

ASJC Scopus subject areas

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

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

Cite this