authors 
O'Rourke, J., Chien, C.B. and Olson, Th. (et al) 
year 
1982 
title 
A New Linear Algorithm for Intersecting Convex Polygons 
source 
Computer Graphics and Image Processing. 1982. vol. 19: pp. 384391 : ill. includes a short bibliography 
summary 
An algorithm is presented that computes the intersection of two convex polygons in linear time. The algorithm is fundamentally different from the only known linear algorithms for this problem, due to Shamos and to Hoey. These algorithms depend on a division of the plane into either angular sectors (Shamos) or parallel slabs (Hoey), and are mildly complex. The authors' algorithm searches for the intersection points of the polygons by advancing a single pointer around each polygon, and is very easy to program 
keywords 
algorithms, boolean operations, polygons, intersection, search 
series 
CADline 
references 
Contenttype: text/plain

last changed 
2003/06/02 12:42 
