#
The Article

Toussaint, Godfried T., "A simple linear algorithm for
intersecting convex polygons", in *The Visual Computer*, vol.
1, 1985, pp. 118-123.
Available in postscript: convex.intersection.ps.gz

##
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*(*n* + *m*)
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.
**keywords: **Algorithms ; Complexity ; Computational geometry ;
Convex polygons ; Intersection .

##
Related work

O'Rourke, J., "A new linear algorithm for intersecting
convex polygons", in *Computer Graphics and Image Processing*,
number 19, 1982, pp. 384-391.
Shamos, M.I., **Computational Geometry**, Ph.D.
thesis, Yale University, 1978.

Shamos, M.I., **Problems in Computational Geometry**,
Carnegie-Mellon University, 1977.

Shamos, M.I. and Hoey, D., "Geometric intersection
problems", in **Proceedings of the Seventeenth Annual IEEE Symposium on
Foundations of Computer Science**, October 1976, pp.208-215.

Follow the links below: