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 ldquointersectionrdquo is introduced; moreover, all kinds of algebraic operations on the run-lengthpsilas attribute are performed during the realization process. Adopting this ldquointersectionrdquo 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 ldquointersectionrdquo 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 ldquoUnionrdquo and ldquoEraserdquo, 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.