缓冲区生成的边界追踪算法优化技术  

Optimization of Boundary Tracing Algorithm on Buffer Generation

作　　者：王结臣[1] 李利番[1] 李丽[1] 沈定涛[1] 

机构地区：[1]南京大学地理信息科学系,江苏南京210093

出　　处：《地理与地理信息科学》2009年第1期95-98,共4页Geography and Geo-Information Science

基　　金：国家基础科学人才培养基金(J0630535)

摘　　要：利用缓冲区边界曲线上各点距缓冲目标距离相等的性质,建立一种基于矢量追踪思想的缓冲区生成方法,提出并探讨了以下优化技术:进行缓冲目标弧段重采样;扩展弧段数据结构以提高点、弧距离计算的效率;闭合边界追踪过程中采用折半逼近的追踪策略并进行动态数据压缩;对缓冲目标集合进行自适应分组和运用分治算法等。结果表明,该算法在内存占用、计算精度等方面具有优势,其计算效率亦可满足一般的GIS应用需求;此外,该算法中边界追踪的思想可以推广应用于空间分析算法设计中。Utilizing the property that the distances from all points located on the borderline of buffer zone to arcs of the data set are the same, this paper presents a novel method of buffer generation based on vector boundary tracing. In order to improve performance of the algorithm, some optimization methods are put forward as follows： to extent the existing arc data structure for the sake of improving the efficiency of point-arc distance calculation; to compress the dynamic data during the process of the closed boundary tracing; to carry on self-adaptive grouping for arcs of the data sets and apply partition algorithm. Tests results and corresponding analyses indicate that the algorithm have the advantage of less memory cost, much higher resolution of calculation and so on, and its computational efficiency fully meets the demands of usual applications in GIS. Furthermore, the principle of boundary tracing in the algorithm has the potential for further being promoted to apply to many related spatial analysis algorithms.

关 键 词：缓冲区生成 算法 边界追踪 

分 类 号：P208[天文地球—地图制图学与地理信息工程]