Implementation of polygon overlay based on run-length encoding

Aiming at the low computation efficiency and storage insufficiency of direct-encoded raster data, a new data structure on the basis of run-length encoding has been proposed to optimize the algebraic operations that are based on direct-encoded raster data. In this paper, employing this new data structure, the realization of "intersection" is introduced; moreover, all kinds of algebraic operations on the run-length's attribute are performed during the realization process. Adopting this "intersection" operation to implement polygon overlay, the steps are as follows: firstly, convert the polygons on two different layers into run-length sets, and then intersect the run-length set of the base layer with the run-lengths of the adding layer, carrying out this "intersection" operation until obtain the resulting run-length set of the two layers, afterwards, extract the required run-length units according to different overlay modes, such as "Union" and "Erase", finally, vectiorize the run-lengths into polygons then output. In the process of overlapping, all kinds of polygon overlay modes have been realized, proving that the algorithm could be applied broadly.