关于传统空间缓冲区生成算法的分析

1、关于传统空间缓冲区生成算法的分析 摘要：本文通过对各类空间缓冲区生成的算法思想及算法实现进行分析与比较，给出了避免在缓冲区生成结果的过程中出现的失真与尖角等问题的最适合的解决方法。 关键词：缓冲区；栅格；矢量；角平分法；凸角圆弧法 中图分类号：TP301.6 文献标识码：A文章编号：1007-9599 (2011) 20-0000-01 Analysis of Generation by Traditional Spatial Buffer Algorithm Liu Lijuan,Min Jie (Xinyang Agricultural College,Xinyang464000,Chin

2、a) Abstract:In this paper,the author had analysed the thinking of algorithm of the traditional space buffer generation,compared the implementation of the algorithm,and given The summary of the aberration and the buffer distortion.kinds of issues are arised in the process of the implementation of the

3、 algorithm.such as the computing speed of algorithm,sharp corners,depression. Keywords:Buffer;Grid;Vector;Angular bisectrix method;Circular arcs method 一、引言 空间缓冲区是指空间目标的一种影响范围或服务范围，其数学定义为，空间目标对象 缓冲区为： 。即当空间目标对象 的缓冲半径为R时，其缓冲区可以用距离对象 的距离d小于或等于R的全部点的集合。而对于一些对象集合来说，其缓冲半径为R的缓冲区是各个对象缓冲区的并，用公式表示为： 。空间目标可分为

4、点目标、线目标和面目标，其中点目标的缓冲区比较容易生成。面目标也可当作一个特殊的线目标。因此大部分的文献中，关于缓冲区生成算法的研究都是基于线目标来阐述的。本文也是把线目标的缓冲区生成作为问题分析的主要对象。 二、传统缓冲区生成算法思想 目前对于缓冲区的生成算法的学术研究主要从数学运算法、栅格算法和混合算法这个三个方面入手。其中栅格方法在原理上较简单，容易实现。矢量方法在机器精度范围内尽可能保持原始精度。混合算法将这两种方法结合起来，取利去弊，目前还是一种比较合理并使用广泛的方法。 （一）基于栅格的缓冲区生成算法。栅格方法的核心思想是基于数学形态学的扩张算子的，也可叫做点阵法。栅格方法在实现过

5、程中是先将点、线和面这些空间目标栅格化，再向目标栅格周围进行量化扩张，最终通过边界提取方式来生成结果多边形。 （二）基于矢量的缓冲区生成算法。平行双线算法是用矢量方法建立缓冲区的核心算法，在很多文献资料也将其称为计算机图形加粗法、加宽线法或中心线扩张等。矢量算法的主要思路是首先确定缓冲目标，其次将缓冲目标分成若干个单独目标并逐一生成缓冲多边形，然后进行多边形求交得出所有可能多边形，最后根据拓扑关系，生成结果多边形。空间实体目标缓冲区边界线的矢量生成算法有多种，这其中最具代表性的是角平分线法与凸角圆弧法。很多学者都是围绕这个两种传统方法进行算法改进的。其中角平分线法的缓冲区生成是分线目标的端点与

6、线目标本身两个步来实现的。分别在轴线起始点与终止点处作轴线的垂线，以左右侧缓冲半径 和 截出左右缓冲边线的起点与终点；在轴线的转折点处缓冲顶点的是用与该点关联的两邻边距轴线的两平行线的交点。凸角圆弧算法与角平线算法的区别在于对目标线拐点的缓冲端点的生成上，其采用半径为缓冲距的圆弧进行拟合思路。根据拐点的凸凹性作不同的处理，在拐点的凸侧用缓冲距为半径的进行圆弧拟合。 三、传统算法存在的问题 （一）栅格算法的海量问题。根据上文论述，栅格算法虽然在原理上较简单，容易实现，由于不能保证缓冲区精度，而且内存的开销大，其难以实现海量空间目标的缓冲区生成。因此建议当目标数据量相对比较多，尽量避免使用栅格方法

7、。当对计算机硬件要求不高时，可以从栅格游程编码、图像膨胀等角度把空间目标栅格化来生成空间目标的缓冲区，这样就可在运算效率和内存开销有很大的改进。 （二）缓冲区失真现象。角平分线的算法的一个最大的缺陷在于，当轴线转角太大时难以最大限度地保证左右边界的等宽性。转角处的凸侧角点将随着角度的进一步变锐而沿角分线远离轴线顶点。目前对于缓冲区生成的研究都在从这点入手，对算法对作了大量的修正，但效果不明显，几乎处于瓶颈状态。尖角和凹陷的失真现象。在利用凸角圆弧的算法生成缓冲区时，当目标线出现尖锐转角时，平行线交点随缓冲距的增大将会迅速远离轴线，会出现如图1所示的尖角和凹陷。当建立左右缓冲距不相等的缓冲区时，

8、在轴线两端处，由于左右缓冲距离不相等，在轴线两端会产生如图2所示尖角。一些研究者就从这一点入手，运用旋转点变换公式来简化尖角的纠正过程，来达到平缓尖角和凹陷的目的。 图1：线的缓冲区失真现象图2：不对称缓冲区端点处圆弧拟合 （三）缓冲区的自相交。当线目标的弯曲空间不能容许缓冲区边界线自身无压盖地通过时，缓冲区边界线就会产生若干个如图3所示自相交多边形。某些目标实体其自身就有相交现象（如图4所示）。对于这两种自相交现象，可以运用递归方法来这种不确定性。 图3线的缓冲区边界自相交多边形图4轴线自相交情况 四、小结 为了解决栅格与矢量算法产生的大量缺陷，专家们采用相应的补救措施，但是由于空间目标实体的复杂性，采用的算法模型进行相应的处理时，依然会出现各种异常情况。因而对于空间目标的缓冲区生成，我们仍需要进一步研究与探索。 参考文献： 1毋河海.关于GIS缓冲区的建立问题J.武汉测绘科技大