Systolic algorithms for rectilinear polygons (Q1108798)

We develop systolic algorithms for the OR, AND, oversizing, and undersizing of rectilinear polygons. These algorithms work on an edge representation of the polygons rather than on a bit map representation. The algorithms are to be run on a systolic chain of processors. The edges are input at the left end of this chain. From here, they ``float'' as far to the right as necessary. As edges float to the right, they compare themselves with edges that are resident in the processors they are floating through. During this comparison the output polygons are generated. Output polygons float to the left. These polygons are output from the left end of the chain. The throughput of the systolic system can be improved by increasing the length of the processor chain.