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:


    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:

 Main Page 
About the Article
 The Algorithm 
The Applet
  home page