一种GIS缓冲区快速生成算法

第４３卷第８期　

２　０　１　２年４月　

文章编号：１００１—４１７９（２０１２）０８—０００７一Ｏ５　

人　民　长　江　

Ｙａｎｇｔｚｅ　Ｒｉｖｅｒ　

ＶｏＩ．４３．Ｎｏ．８　

Ａｐｒ．，　２０１２　

一

种ＧＩＳ缓冲区快速生成算法　

沈定涛，张治中，陈蓓青，曹　波　

（长江科学院空间信息技术应用研究所，湖北武汉４３００１０）　

摘要：针对目前已有的ＧＩＳ缓冲区生成算法的优缺点，提出了一种基于条带分割的缓冲区生成算法，将基元缓　

冲区的合并计算分解到条带中，以条带中面片单元合并代替缓冲区基元合并，避免了常见缓冲区生成方法中　

的弧段打断、重组等复杂的计算过程，提高了算法效率。论述了采用条带分割算法构建缓冲区的实现步骤及　

主要技术细节，经过理论分析和实际测试表明，该算法是一个较适用的缓冲区生成算法。　

关键词：缓冲区生成；扫描线；条带分割；面片单元；地理信息系统　

文献标志码：Ａ　中图法分类号：ＴＰ３９１　

缓冲区分析是ＧＩＳ空间分析的核心功能之一，是　

实现空间邻近度分析的一种重要方法。按照空间目标　

类型不同，ＧＩＳ缓冲区主要分为点缓冲区、线缓冲区、　

面缓冲区和混合目标缓冲区等几种　。目前ＧＩＳ缓冲　

区生成算法主要分为栅格算法和矢量算法两种。　

栅格算法主要有数学形态学扩张法　、填充算　

法　和栅格距离法　等，其主要算法思想为：首先将　

空间目标栅格化，得到空间目标栅格集合，然后按照给　

定的缓冲距离，从目标栅格向四周进行扩张，最后对栅　

格结果进行栅格边界追踪得到矢量缓冲区数据。栅格　

现凹陷和尖角等失真现象。　

本文借鉴栅格条带的思想，采用矢量算法中常用　

的扫描线方法，将空间目标生成的基元缓冲区进一步　

分割为面片单元并按条带存储，以条带中面片单元的　

合并计算代替矢量算法中复杂的弧段打断、重组计算，　

以简化算法复杂性。本算法兼具栅格算法的简易性，　

又保持了矢量数据精度，其实现简单，效率较高。　

１算法基本原理　

在空间目标缓冲区生成算法设计中，因为线目标　

自身包含了线段结点，其缓冲区生成已包含了点目标　

缓冲区生成，而面目标缓冲区生成可以通过构成面目　

算法实现较简单，算法效率较高，但是栅格数据的精度　

直接由网格密度决定，要想获得理想的计算结果需要　

不断提升网格密度，随着网格密度的增加则会产生计　

标的线向外侧生成缓冲区来间接完成。因此线目标缓　

冲区生成是算法实现的关键，本文在分析算法原理与　

思路时主要以线目标为例。由于线目标空间形态的复　

算机内存占用过大和算法效率降低等问题。　

常见的矢量生成算法主要包括平行双线法　、双　

线圆弧法　、凸角圆弧法　等。在矢量算法中空间目　

标生成的缓冲区多以有序线段链进行存储，在实现空　

间目标间缓冲区合并过程中包含大量的线段打断、重　

杂性，在进行缓冲区生成时，一方面需要顾及缓冲区头　

尾出现自相交的情形，另一方面需要判定其缓冲区是　

否与其他线目标缓冲区出现相交，此时需要对相交缓　

组、合并等复杂计算过程，因此弧段间求交计算效率是　

冲区进行合并。为了简化算法的复杂性，作者将空间　

线目标分解为点和线段的集合，并对其各自生成缓冲　

区集合，称之为基元缓冲区，并在此基础上进行基元缓　

冲区合并。如图１所示，线目标ＡＢＣＤ由３条线段和　

矢量算法研究的重点。矢量算法与栅格算法相比具备　

数据精度的优势，对计算机内存配置要求不高，但是算　

法设计复杂，算法效率相对较低，在实际应用中容易出　

收稿日期：２０１２—０ｌ一３Ｏ　

基金项目：水利部科技推广计划项目（ＴＧ１０１０）；国家科技支撑计划项目（２００９ＢＡＫ５６Ｂ０１）　

作者简介：沈定涛，男，助理工程师，硕士，主要从事地理信息系统理论与应用研究。Ｅ—ｍａｉｌ：ｓｄｔ２００３＠１６３．ｅｏｍ　

８　人　民　长　江　

４个结点组成，按照给定的缓冲距离，将点生成圆形基　分割的缓冲区生成方法。算法将空间划分为高度不规　

则的条带，在条带上存储经基元缓冲区分割后的面片　

单元，将栅格单元的叠置计算转化为面片单元的合并　

计算。在常见缓冲区生成矢量算法中对点生成的圆形　

元缓冲区，将线段向两侧平移做平行线，构造矩形基元　

缓冲区。图１中共有７个基元缓冲区，该条线目标的　

缓冲区即是上述７个基元缓冲区合并后的结果，因此　

可以将线目标集的缓冲区生成转化为平面上基元缓冲　

区的合并计算。　

缓冲区多以正多边形进行近似拟合，算法设计中，我们　

以正十二边形为例。如图２、３所示，为圆形和矩形基　

元缓冲区上每个结点构造水平扫描线，可以将空间划　

分为多个条带，如图２中７条扫描线构造了６条条带，　

共６个面片单元，图３中４条扫描线构造了３条条带　

共３个面片单元。最上和最下条扫描线外侧形成的无　

图１空间目标基元缓冲区示意　

在矢量算法中，如何提升弧段间交点计算的处理　

效率一直是人们关注的焦点。在进行点集缓冲区生成　

时需要求出所有圆形缓冲区间的交点，去掉无效弧段　

并完成新弧段构建。实际应用中多以有序链表存储弧　

段结点，通过在计算交点时，判定其是缓冲区多边形的　

入点或出点完成弧段的打断重组。基元缓冲区在空间　

上的互相覆盖，增加了缓冲区多边形有序链表的维护　

复杂性，在判定某个入点或出点时，若出现错误则会得　

出完全不同的计算结果。同时，有序链表形成的闭环　

难以判定其是多边形内环或外环，在构建带洞、岛形式　

的缓冲区多边形时较为困难。而基元缓冲区合并的栅　

格方法则相对简单，对于一个二值栅格场，将基元缓冲　

区进行矢量栅格转换，对基元缓冲区所覆盖的网格单　

元进行赋值，最后对此二值栅格场完成栅格矢量转换　

生成缓冲区多边形即可。栅格方法极大地简化了算法　

的复杂性，在计算过程中不需要考虑基元缓冲区之间　

的叠置求交点问题，基元缓冲区的重叠部分仅表现某　

些栅格单元具有相同值。栅格方法在一定程度上提升　

了算法效率，但是其数据精度依赖于栅格场密度，若栅　

格场过粗，其数据精度难以保证，同时极易将实际并不　

重叠的缓冲区基元合并到同一个缓冲区多边形中，出　

现计算误差。虽然提升网格密度可以有效保证算法精　

度，但随着网格密度的增长，其算法效率的快速下降也　

是很明显的。　

栅格算法有效避免了基元缓冲区合并时复杂的弧　

段求交点计算，基元缓冲区合并转换为栅格行上对应　

网格单元的叠置计算。借鉴这种栅格叠置思想，同时　

为了保证算法数据精度，笔者提出一种基于扫描条带　

限空间条带可以忽略不计，因为此条带上不会存储面　

片单元。一般情形下，基元缓冲区经分割后生成的面　

片单元多是梯形，该梯形斜边为缓冲区多边形边，上底　

和下底为相邻上下水平扫描线，在多边形的极值点处　

面片单元由梯形退化为三角形。　

图２　圆形基元缓冲区的条带分割　

Ｄ　

图３矩形基元缓冲区的条带分割　

要实现基元缓冲区生成的面片单元间快速合并，　

可以预先构造一个空的条带场，每当一个基元缓冲区　

进行了条带分割后，就将面片单元插入到条带场，在插　

入时完成与条带中已有面片单元的合并计算。条带场　

可以用一个一维数组表达，该一维数组存储了扫描线　

第８期　沈定涛，等：一种ＧＩＳ缓冲区快速生成算法　９　

所在的ｌ，值，数组元素之间代表一个条带场所在的空　

间，每插入新的条带时只需要对该数组进行更新即可。　

作者采用链表标记条带上的面片单元集合，链表中每　

个结点代表一个面片单元。算法设计时，为每个条带定　

义一个链表，同时用一个链表数组对所有条带链表进　

片单元，ｃ如，　

ｉ　

条带上有面片单元ｏ６　。　

＾　

ａ　ｂ　

＼　＼　

＼　

ｋ　

＼ｃ　

ｋ　／

／／／５￣　

／／　

行存储，显然，序号为Ⅳ的条带链表其下扫描线和上扫　

描线所在的ｙ值对应条带场数组中的第Ⅳ和Ⅳ＋１个　

元素值。由于每个条带上扫描线和下扫描线的ｌ，值都　

ｅ　／＼　／／／　

／　

／

Ｊ　

、　Ｌ　１　

存储在条带场数组中，面片单元只用记录４个顶点　

值即可。面片单元和条带链表数据结构如下。　

面片单元数据结构：　

ｓｔｒｕｃｔ　ＰｌａｎｅＵｎｉｔ　

｛　

ｄｏｕｂｌｅ　ＬＢＸ；／／左下点ｘ坐标　

ｄｏｕｂｌｅ　ＲＢＸ；／／右下点ｘ坐标　

ｄｏｕｂｌｅ　ＬＴＸ；／／左上点ｘ坐标　

：ｓ　∞　Ⅱ　

ｄｏｕｂｌｅ　ＲＴＸ；／／右上点ｘ坐标　

ＰｌａｎｅＵｎｉｔ　Ｎｅｘｔ；／／下一面片单元指针　

｝　

条带链表数据结构：　

ｓｔｒｕｃｔ　ＳｔｒｉｐＬｉｎｋ　

｛　

ｉｎｔ　ＰｌａｎｅＵｎｉｔ　Ｎｕｍ；／／链表结点数目　

ＰｌａｎｅＵｎｉｔ　Ｆｉｒｓｔ；／／链表头指针　

ＰｌａｎｅＵｎｉｔ￥Ｅｎｄ；／／链表尾指针　一　

｝　

２关键计算过程　

２．１　基元缓冲区生成和动态条带场构建　

在栅格算法中，栅格场的行列数目是预先设定的，　

基元缓冲区被栅格化到固定的栅格场中。本算法中条　

带由基元缓冲区多边形顶点所构造的扫描线生成，在　

初始状态下难以预先设定条带场的规模，新的条带是　

在基元缓冲区不断构建的过程中生成的，可以称之为　

动态条带场。注意到任一条带都是由上扫描线和下扫　

描线构成，当有新的条带插入条带场时，仅需要将上下　

扫描线所在的ｌ，值插入到条带场数组中完成条带场的　

更新。在插入某扫描线所在ｙ值后，数组中对应的该ｌ，　

值上下元素组成的原条带将分裂成为两条条带，此时　

需要对条带链表数组进行同步动态更新，原条带上有　

面片单元的，需要对该面片单元进行分裂，划分到对应　

的上下两个条带。　

如图４所示，条带场被５条水平扫描线（Ｌ１、Ｌ２、　

￡３、　、　）划分为４条条带，在Ｌ１Ｌ２条带上有面片单　

元ｋｈｉｊ，Ｌ２Ｌ３条带上有面片单元ｋｇｈ，Ｌ３Ｌ４条带上有面　

图４条帝场的动态构建　

基元缓冲区ＡＢＣＤ在条带场中的位置如图４所　

示，生成的面片单元为ＡＥＤ、ＥＤＦＢ和ＢＣＦ。由于Ａ、　、　

ｃ、Ｄ四点ｌ，值不属于条带场数组中的值，其构建的扫　

描线与条带场上扫描线不重合，此时将基元缓冲区的　

４条扫描线插入到条带场，进行条带场上对应条带的　

分裂，并对原条带上对应面片单元进行分割，如图中面　

片ｎ６　和　将分别分裂为３个面片单元。同理，用条　

带场上位于Ａ点和Ｄ点之间的ｙ值构建扫描线对基元　

缓冲区ＡＢＣＤ生成的面片单元进一步分割，如面片　

ＥＤＦＢ将分割为４个更小的面片。在对条带场进行分　

裂后，基元缓冲区所在的条带已经和条带场中条带完　

全匹配，后续工作是将经过分裂后的缓冲区基元所在　

面片单元插入到条带场上对应条带中。　

２．２条带场中面片单元合并　

在对条带场上面片单元和基元缓冲区生成的面片　

单元进行分割后，可以将基元缓冲区面片单元依次插　

入到对应的条带中。由于基元缓冲区多边形间存在相　

交的情形，而面片单元两斜边仅表示基元缓冲区多边　

形的边界，因此面片单元在插入条带时可能与同一条　

带中其他面片单元相交。如图５所示，某条带上有３　

个面片单元，待插入面片（以竖线填充）分别与条带上　

第１和第２个面片部分重叠。为便于数据组织，此时　

需要计算待插入面片与条带上相关面片的交点，并在　

交点处构造水平扫描线，生成新的条带，同时将原条带　

上面片和待插入面片进一步分割，最后完成待插人面　

片与条带上面片的合并。图６中该条带经交点处水平　

扫描线分割后分裂为３个条带，在进一步完成面片合　

并后，面片数目也从３个分裂为９个。在面片单元插　

入条带过程中，完成面片斜边求交点是关键。为判定　

待插入面片单元和条带上哪些面片单元相交，可以分　

别计算待插入面片单元两条斜边处于条带的位置。条　

带上面片单元集合采用有序链表存储，链表中面片上　

顶点或下顶点　值是依次从小到大排列的，因此只要　

计算出待插入面片斜边的上顶点和下顶点　值处于链　

表中的位置，即可计算出该面片单元与条带上面片集　

ｌ０　人　民　长　江　

合的相交关系。同时，面片单元成为链表中的结点，面　

片单元的合并仅仅表现为结点单元的插入和删除，其　

处理相对简单。　

合并前　

到一个面片单元，其右上顶点和当前面片单元右下顶　

点　值相同。若未能找到满足条件的面片单元，则表示　

当前面片单元所在顶点处于缓冲区多边形极值点处　

（此时面片单元由梯形退化为三角形），此时需要进行　

追踪方向转换，追踪也从当前面片单元某斜边转换到　

另一侧斜边。当转换到另一侧斜边且发现其已经被追　

踪过时，表示当前追踪已经结束，提取追踪到的面片单　

合并后　

图５条带上面片单元合并　

／＼　

／　、　

、ｌ　

左上　一　踹　下础　

ｊ　

／／　＼

／　

＼　

＼　

／　／　／　

｜　／　

图６基于条带的矢量边界追踪　

２．３边界追踪生成缓冲区　

在栅格算法中，因栅格单元以规则矩形表达，栅格　

单元所在边界线是水平或垂直线段，在进行边界追踪　

时，其追踪方向可以分为上、下、左、右４个　Ｉ９　。不同　

于栅格算法，本算法中面片单元采用梯形表达，边界为　

梯形两斜边构成，其边界追踪方向可以以左上、右上、　

左下和右下４个状态标记。如图６所示，某多边形带　

洞结构，条带上面片单元依次从左至右排列，外边界追　

踪方向从左上转换为右下，内边界追踪方向从右上转　

换为左下。　

在进行边界追踪时，可以为每个面片单元的左侧　

和右侧斜边标记追踪状态确定其是否已经被追踪过，　

每追踪一条斜边就对该斜边进行标记。从条带场中第　

一

个条带开始，逐个面片单元进行追踪，直至每个面单　

元片两斜边都被追踪过，则停止追踪。当追踪状态为　

左上时，继续在上一条条带上找到一个面片单元，其左　

下顶点与当前面片单元左上顶点　值相等；当追踪状　

态在为右上时，继续在上一条条带上找到一个面片单　

元，其右下顶点与当前面片单元右上顶点　值相等；当　

追踪状态为左下时，继续在下一条条带上找到一个面　

片单元，其左上顶点和当前面片单元左下顶点　值相　

等；当追踪状态为右下追踪时，继续在下一条条带上找　

元坐标构建缓冲区多边形，并继续从当前面片单元的　

下一个面片单元开始新的追踪，依此遍历条带直至整　

个追踪过程结束，提取出所有的缓冲区多边形。　

３测试与分析　

为评估算法性能，笔者进行了相关测试，算法程序　

采用ＶＣ＋＋６．０设计实现，计算机配置为：Ｉｎｔｅｌ酷睿　

ｉ５　２．２７ＧＨＺ　ＣＰＵ，计算机内存３Ｇ。算法测试以线目标　

集为例，图７中左侧图为测试图件之一，该线目标集中　

共有３　２２７条线，右侧两幅为该线目标集的双侧缓冲　

区生成结果局部放大图。表ｌ为在固定缓冲区距离时　

不同数据量情形下的算法耗时。算法测试表明，在算　

法执行过程中基元缓冲区生成和条带边界追踪耗时基　

本可以忽略，而算法耗时主要体现在面片单元插入条　

带场以及和条带场中已有面片单元进行合并的过程　

中。影响算法计算耗时的主要因素是空间目标数据量　

的大小，因为单点和单线生成的基元缓冲区其分割的　

面片单元数目是确定的，当数据量不断增加导致生成　

鼍　

的面片单元数目增加时，在插入条带时会进行条带的　

分割细化，使条带场规模不断增大。　

一　

图７缓冲区生成测试示例　

表１　线目标集缓冲区生成测试结果　

假定空间线目标组成的线段条数为Ⅳ，其结点数　

，

．　

、

第８期　沈定涛，等：一种ＧＩＳ缓冲区快速生成算法　

目也可以近似以Ⅳ计，则其圆形和矩形基元缓冲区生　

矢量两个方面着手，栅格算法虽然简单，但是内存占用　

高、数据精度难以保证，矢量算法数据精度高，但是算　

法设计复杂，异常情况多，算法效率难以保证。本文提　

出一种基于扫描条带存储的方法实现缓冲区生成，其　

成的面片单元分别为３Ⅳ＋６　Ｎ　９　Ｎ个，若不考虑面　

片单元斜边求交点则条带场中将有约９Ｎ个条带，考虑　

到面片单元交点数目远小于线段结点数目，条带场中　

的条带数目仍然是可以预估的。在基元缓冲区生成的　

面片单元插入条带场并进行分裂的过程中，判断条带　

斜边位于条带中面片单元集合的位置可以通过对比面　

片单元顶点　坐标采用折半查找法判定，假定每个条　

带上面片单元的平均数目为　，则通过折半查找的时　

条带存储思想类似于栅格行，通过在条带上存储形态　

简单的面片单元（因为面片单元顶点以实际空间坐标　

存储），可以保留矢量算法所具有的精度，同时通过在　

条带上进行面片单元的增加、删除完成面片单元合并，　

具备很好的灵活性。在条带上，面片单元的斜边求交　

间复杂度为Ｏ（１ｇＭ），完成所有面片单元插入时总体　计算比较简单，避免了矢量算法中复杂的弧段求交计　

时间复杂度为Ｏ（ＮｌｇＭ），此时Ｍ＜＜＜Ｎ。　

算，算法实现效率较高，具有一定的应用价值。　

在栅格算法中，计算机内存耗用取决于栅格场规　

参考文献：　

模大小的设置，不同的网格密度对计算机内存的耗用　

［１］　黄杏元，汤勤．地理信息系统概论［Ｍ］．北京：高等教育出版社，　

不同，而本算法在内存耗用方面主要取决于空间目标　

１９９１．　

数据规模。在算法处理中，条带场中面片单元的存储　

［２］　胡鹏，游涟，杨传勇，等．地图代数［Ｍ］．武汉：武汉大学出版社，　

２００２．　

占用了额外的内存。每个面片单元结构体存储了４个　

［３］　吴艳娜，汤易，施寅．ＧＩＳ中基于栅格转换的缓冲区生成算法　

顶点的　坐标值以及指向下一面片单元的指针，其内　

［Ｊ］．铁路计算机应用，２００２，（４）：１Ｏ一１２．　

存占用为４×８＋４＝３６字节，假定条带场中有十万个　

［４］　郭仁忠．空间分析［Ｍ］．武汉：武汉测绘科技大学出版社．１９９７．　

条带，每个条带上平均有２０个面片单元，则总内存占　

［５］　李金山，方金云．基于平面扫描的双线圆弧缓冲区生成算法［Ｊ］．　

用为３６×２０×１００　０００＝７２　Ｍ字节，目前主流计算机　

计算机工程与应用．２００７，４３，（２３）：２８—３１．　

［６］　陈学工，张文艺，张弛伟，等．一种ＧＩＳ缓冲区矢量生成算法及实　

配置一般能够达到２　Ｇ内存，因此本算法在内存耗用　

现［Ｊ］．计算机技术与发展，２００７，１７（３）：１３—１９．　

方面是可以接受的。　

［７］　董鹏，毛东军，李军，等．一种有效的ＧＩＳ缓冲区生成算法［Ｊ］．计　

以上算法测试与分析表明，本算法具有较快的计　

算机工程与应用，２００４，（１６）：４—８，１２．　

算效率，且对计算机内存耗用不高，可以满足常规条件　

［８］　张孝灿，潘云鹤．ＧＩＳ中基于“栅格技术”的栅格数据矢量化技术　

下的应用需求。　　．

［Ｊ］．计算机辅助设计与图形学学报，２００１，１３，（１０）：８９５—９００．　

［９］　沈掌泉，王人潮．栅格转换矢量的一种新方法：结点搜索法［Ｊ］．　

４结语　

中国图象图形学报，１９９８，３，（４）：３１８—３２１　

（编辑：赵凤超）　

缓冲区分析是ＧＩＳ中应用较多的一个空间分析功　

能，前人对其生成算法做了大量的研究，主要从栅格和　

Ａｎ　ｅｆｆｉｃｉｅｎｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ＧＩＳ　ｂｕｆｆｅｒ　ｇｅｎｅｒａｔｉｏｎ　

ＳＨＥＮ　Ｄｉｎｇｔａｏ，ＺＨＡＮＧ　Ｚｈｉｚｈｏｎｇ，ＣＨＥＮ　Ｂｅｉｑｉｎｇ，ＣＡＯ　Ｂｏ　

（ｓＰａｔｉａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ａｐｐｌｉｃａｔｉｏｎ　Ｉｎｓｔｉｔｕｔｅ，Ｃｈａｎｇｆｉａｎｇ　Ｒｉｖｅｒ　Ｓｃｉｅｎｔｉｉｆｃ　Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ，Ｗｕｈａｎ　４３００　１　０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：　Ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｄｉｓａｄｖａｎｔａｇｅｓ　ｏｆ　ｃｕｒｒｅｎｔ　ＧＩＳ　ｂｕｆｆｅｒ　ｇｅｎｅｒａｔｉｎｇ　ａｌｇｏｒｉｔｈｍ，ａ　ＧＩＳ　ｂｕｆｆｅｒ　ｇｅｎｅｒａｔｉｎｇ　ａｌ－　

ｇｏｒｉｔｈｍ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｓｔｒｉｐ　ｄｉｖｉｓｉｏｎ．Ｔｈｅ　ｃｏｍｂｉｎａｔｉｏｎ　ｏｆ　ｅｌｅｍｅｎｔｓ　ｂｕｆｆｅｒ　ｉｓ　ｄｅｃｏｍｐｏｓｅｄ　ｉｎｔｏ　ｓｔｒｉｐｓ　ｔｏ　ａｖｏｉｄ　ｔｈｅ　ｐｒｏｃｅｓｓ　

ｏｆ　ｃｏｍｐｌｅｘ　ｃａｌｃｕｌａｔｉｏｎｓ，ｓｕｃｈ　ａｓ　ａｒｃ　ｉｎｔｅｒｒｕｐｔｉｏｎ，ｒｅｓｔｒｕｃｔｕｒｅ　ｉｎ　ｔｈｅ　ｃｏｍｍｏｎ　ｂｕｆｆｅｒ　ｇｅｎｅｒａｔｉｏｎ　ｍｅｔｈｏｄ，ｓｏ　ｔｈａｔ　ｉｔ　ｃａｎ　ｉｍｐｒｏｖｅ　ｔｈｅ　

ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｉｍｐｌｅｍｅｎｔｉｎｇ　ｓｔｅｐｓ　ａｎｄ　ｔｈｅ　ｍａｉｎ　ｔｅｃｈｎｉｃａｌ　ｄｅｔａｉｌｓ　ｏｆ　ｂｕｉｌｄｉｎｇ　ｔｈｅ　ｂｕｆｆｅｒ　ｂｙ　ｕｓｉｎｇ　ｔｈｅ　ｓｃａｎ—ｌｉｎｅ　ａｌｇｏ—　

ｒｉｔｈｍ　ａｒｅ　ｄｉｓｃｕｓｓｅｄ．Ａｓ　ａ　ｒｅｓｕｌｔ，ｔｈｅ　ｔｈｅｏｒｅｔｉｃａｌ　ａｎａｌｙｓｉｓ　ａｎｄ　ｐｒａｃｔｉｃａｌ　ｔｅｓｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｎ　ａｐｐｒｏｐｒｉａｔｅ　ｂｕｆｆｅｒ　ｇｅｎｅｒ—　

ａｔｉｎｇ　ａｌｇｏｒｉｔｈｍ．　

Ｋｅｙ　ｗｏｒｄｓ：　ｂｕｆｆｅｒ　ｇｅｎｅｒａｔｉｏｎ；ｓｃａｎ—ｌｉｎｅ；ｓｔｒｉｐ　ｄｉｖｉｓｉｏｎ；ｐｌａｎｅ　ｕｎｉｔ；ｇｅｏｇｒａｐｈｉｃ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ（ＧＩＳ）