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

《关于传统空间缓冲区生成算法的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、关于传统空间缓冲区生成算法的分析：本文通过对各类空间缓冲区生成的算法思想及算法实现进行分析与比较，给出了避免在缓冲区生成结果的过程中出现的失真与尖角等问题的最适合的解决方法。　　关键词：缓冲区；栅格；矢量；角平分法；凸角圆弧法　　：TP301.6：A：1007-9599(2011)20-0000-01　　AnalysisofGenerationbyTraditionalSpatialBufferAlgorithm　　LiuLijuan,MinJie　　(XinyangAgriculturalCollege,Xinyan

2、g464000,China)　　Abstract:Inthispaper,theauthorhadanalysedthethinkingofalgorithmofthetraditionalspacebuffergeneration,paredtheimplementationofthealgorithm,andgivenThesummaryoftheaberrationandthebufferdistortion.kindsofissuesarearisedintheprocessoftheimplementatio

3、nofthealgorithm.suchastheputingspeedofalgorithm,sharpcorners,depression.　　Keyethod;Circulararcsmethod　　一、引言　　空间缓冲区是指空间目标的一种影响范围或服务范围，其数学定义为，空间目标对象缓冲区为：。即当空间目标对象的缓冲半径为R时，其缓冲区可以用距离对象的距离d小于或等于R的全部点的集合。而对于一些对象集合来说，其缓冲半径为R的缓冲区是各个对象缓冲区的并，用公式表示为：。空间目标可分为点目标、线目标和面目标，其中点

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

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

6、最具代表性的是角平分线法与凸角圆弧法。很多学者都是围绕这个两种传统方法进行算法改进的。其中角平分线法的缓冲区生成是分线目标的端点与线目标本身两个步来实现的。①分别在轴线起始点与终止点处作轴线的垂线，以左右侧缓冲半径和截出左右缓冲边线的起点与终点；②在轴线的转折点处缓冲顶点的是用与该点关联的两邻边距轴线的两平行线的交点。凸角圆弧算法与角平线算法的区别在于对目标线拐点的缓冲端点的生成上，其采用半径为缓冲距的圆弧进行拟合思路。根据拐点的凸凹性作不同的处理，在拐点的凸侧用缓冲距为半径的进行圆弧拟合。　　三、传统算法存在的问题　

7、　（一）栅格算法的海量问题。根据上文论述，栅格算法虽然在原理上较简单，容易实现，由于不能保证缓冲区精度，而且内存的开销大，其难以实现海量空间目标的缓冲区生成。因此建议当目标数据量相对比较多，尽量避免使用栅格方法。当对计算机硬件要求不高时，可以从栅格游程编码、图像膨胀等角度把空间目标栅格化来生成空间目标的缓冲区，这样就可在运算效率和内存开销有很大的改进。　　（二）缓冲区失真现象。①角平分线的算法的一个最大的缺陷在于，当轴线转角太大时难以最大限度地保证左右边界的等宽性。转角处的凸侧角点将随着角度的进一步变锐而沿角分线远离轴

8、线顶点。目前对于缓冲区生成的研究都在从这点入手，对算法对作了大量的修正，但效果不明显，几乎处于瓶颈状态。②尖角和凹陷的失真现象。在利用凸角圆弧的算法生成缓冲区时，当目标线出现尖锐转角时，平行线交点随缓冲距的增大将会迅速远离轴线，会出现如图1所示的尖角和凹陷。当建立左右缓冲距不相等的缓冲区时，在轴线两端处，由于左右缓冲距离不相等，在