基于平面扫描的双线圆弧缓冲区生成算法  

Algorithm for line buffering based on plane sweep technique

作　　者：李金山[1] 方金云[1] 

机构地区：[1]中国科学院计算技术研究所空间信息处理技术实验室,北京100080

出　　处：《计算机工程与应用》2007年第23期28-31,共4页Computer Engineering and Applications

基　　金：国家高技术研究发展计划(863)(the National High- Tech Research and Development Plan of China under Grant No.2002AA114020;No.2001AA135210);中国科学院知识创新项目(No.20036020)

摘　　要：在GIS领域,线目标实体的缓冲区生成有很多算法,常见的双线圆弧法存在结果多边形自相交和失真问题,处理起来相当复杂。在双线圆弧法基础上提出一种基于平面扫描技术的线目标缓冲区生成算法,在扫描过程中处理多边形自相交问题,同时能够避免失真现象。算法的时间复杂度为O(nlbn)。In the GIS literature ,many algorithms to generate buffer areas of lines have been proposed.A popular method is based on double parallel lines and circular arcs.But in such methods ,there are serious problems such as self-intersections and distortion of the result polygon.Based on the plane sweep line technique,this paper presents one improved algorithm to generate buffer areas of line strings,which avoids the problems of distortion and simplifies the self-intersections handling.The time complexity of the new algorithm is O（nlbn）.

关 键 词：地理信息系统 缓冲区 双线圆弧法 平面扫描技术 失真 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]