基于平面扫描的线状缓冲区生成的改进算法  

Improved algorithm for line buffering based on plane sweep technique

作　　者：许允波[1] 张建兵[2] 谭宁生[1] 

机构地区：[1]中国科学院遥感应用研究所遥感科学国家重点实验室,北京100101 [2]中国石油大学(北京)信息学院,北京102249

出　　处：《计算机应用研究》2012年第11期4364-4366,4389,共4页Application Research of Computers

基　　金：国家"863"计划资助项目(2012AA12A401)

摘　　要：针对传统双线圆弧算法存在失真现象和效率低下问题,提出了一种改进的基于线段/弧段的平面扫描算法。首先通过在凹点记录线段来避免失真问题;然后利用线段/弧段之间距离远近和相互连接的性质,采用改进的平面扫描算法大幅度地提高求交效率;同时设计一种算法快速剔除非边界点;最后利用线段/弧段具有前进方向的性质,快速构造最终缓冲区边界。该算法能避免失真问题,精确高效,具有较高的空间和时间利用率。This paper persented an improved algorithm, which could resolve disortion and inefficient problems existing in traditional double parallel lines and circular arcs method. First, it recorded segments in concave point to avoid distortion. Then by using distance and interconnected nature, using improved plane sweep algorithm could substantially improve the efficiency of intersect. At the same time, it designed an efficient algorithm to remove the non-boundary points. Lastly, it built the final buffer boundary by using the forward direction nature of line/arc segment. This algorithm can avoid distortion, and is accurate and efficient, with high spatial and time utilization.

关 键 词：缓冲区 线状 平面扫描 地理信息系统 

分 类 号：TP399[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]