Edge list constructor for digital image processor

Claim 1

An edge list constructor comprising: a calculation means for advance calculation of f(K), which is the number of intersections made by a horizontal straight line whose Y value equals K and an edge of an m-polygon, the m-polygon being formed by m segments (edges) ending at two adjacent vertex elements (Xn, Yn) as the starting point and (Xn+1, Yn+1) as the terminating point and being defined by a coordinate vertex sequence {Xn, Yn} (where m is a natural number not less than 3, n is a natural number not more than m, Xm+1=X1 and Ym+1=Y) on the two-dimensional X-Y plane, and the greatest and the smallest Y coordinate values among the elements in said coordinate vertex sequence {Xn, Yn} being Ymax and Ymin, respectively, and K being an integer not less than Ymin but not more than Ymax; a generation means to generate a plurality of edge list elements including coordinates of intersections made by an edge of said m-polygon and the horizontal straight line where Y=K and the plus or minus sign for the outer product of that intersection in the order where all the edges of said m-polygon are traced in one direction along the edges; a storage means to store said edge list elements generated by said generation means; and a storage processing means to store, during the process of storing said edge list elements serially generated by said generation means to said storage means, each of said edge list elements at a location spaced apart from the location where the previous edge list element whose Y equals K has been stored, by f(K) calculated by said calculation means.