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: