A Novel Algorithm of Buffer Construction Based on Run-length Encoding

作者：Wang, Jiechen^*; Cui, Can; Pu, Yingxia; Ma, Jinsong; Chen, Gang

来源：Cartographic Journal, 2010, 47(3): 198-210.

DOI：10.1179/000870410X12786821061413

• buffer construction
• run-length encoding
• run-length brush calculation algorithm
• geographic information system

This paper presents an algorithm of buffer construction incorporating run-length encoding and the idea of raster overlay method. In traditional raster methods, the buffer target is traced and scanned using a 'brush', the width of which is equal to the buffer distance. During this process, the brushed raster grids are marked. Then by carrying out dynamic calculation on these marked grids, the buffer zone, constituted of grids, would be generated. Finally, the desired boundary of the buffer zone could be obtained through vectorisation. Considering the obvious drawbacks of raster data in computing efficiency and storage capacity, this paper puts forward the idea of storing raster data by means of run-length encoding, on which the raster-based operations are carried out. In order to improve the spatial precision, the borderlines of each run-length unit are recorded in the data of real type. The tests and analyses indicate that this algorithm has integrated advantages with respect to time complexity, space complexity and computational accuracy.

• 出版日期2010-8
• 单位南京大学