CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

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. 384-391 : 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 Content-type: text/plain
last changed 2003/06/02 12:42
HOMELOGIN (you are user _anon_347974 from group guest) Works Powered by SciX Open Publishing Services 1.002