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

PDF papers
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
pick and add to favorite papersHOMELOGIN (you are user _anon_522928 from group guest) CUMINCAD Papers Powered by SciX Open Publishing Services 1.002