基于向量边界追踪的高效缓冲区生成方法

需积分: 7 35 浏览量更新于2024-09-08 收藏 926KB PDF 举报

本文档探讨了一种新颖的基于向量边界追踪的缓冲区生成方法（A Novel Method of Buffer Generation Based on Vector Boundary Tracing），该方法充分利用了缓冲区边界上所有点到对应缓冲目标距离相等的特性。这种方法旨在简化复杂的矢量计算过程，如线段和曲线段的交点查找、裁剪与合并、边界的闭合等操作，同时保持与其他基于矢量的算法相当的高精度。算法的主要步骤包括： 1. 初始化追踪点集：首先，在缓冲区边界上生成一组初始的追踪点集，这些点代表了边界上的关键位置。 2. 连续并封闭边界：通过追踪这些点，形成一条连续且闭合的边界线，这一步减少了对复杂几何操作的需求，提高了计算效率。 3. 构建区域目标：利用这些封闭的边界线，可以精确地定义缓冲区区域，进而进行空间分析或其他相关GIS应用。测试结果显示，这种方法在减少内存消耗和提高计算准确性方面具有显著优势。特别是在地理信息系统（GIS）中，这种算法的高效性能能够满足日常应用的需求。此外，文中提到的边界追踪原理展示了其在设计更多高级空间分析算法方面的潜力。这种基于向量边界追踪的缓冲区生成方法不仅简化了数据处理流程，降低了计算负担，还提升了结果的精度，对于优化GIS工具和地理数据分析具有重要的实际意义。随着GIS技术的发展，这种创新方法有望成为未来空间分析领域的标准工具之一。

A Novel Method of Buffer Generation Based on Vector Boundary Tracing

Wang Jiechen

Yu Qing

Chen Yanming

Geographic Information Science Department, Nanjing University, Nanjing, 210093, China

wangjiechen@hotmail.com

ABSTRACT: Utilizing the property that the distances from all

points located on the borderline of buffer zone to corresponding

buffer target are the same, this paper presents a novel method of

buffer generation based on vector boundary tracing. The new

method can avoid complex vector calculations, such as line and

curve segment intersection, clipping and recombination, the

closure of borderline and so on, and also has an advantage of

high precision the same as all existing vector-based algorithms.

The main steps of this algorithm include: (1) Generate the initial

tracing point set located on the borderline of buffer zone; (2)

Obtain an integrated and closed borderline by tracing these

points; (3) Construct the area targets on the basis of these closed

borderlines. The test results and analysis indicate that this

algorithm has a great advantage in the aspects of decreasing

EMS memory consumption and improving calculation accuracy,

and its computational efficiency can fully meet the demand of

usual application in GIS. Furthermore, the principle of

boundary tracing in the algorithm has a potential for further

being promoted and used to design related spatial analysis

algorithms.

KEYWORDS: Buffer zone; buffer generation; GIS; algorithm;

vector; boundary tracing

I. INTRODUCTION

Buffer analysis is one of the most important functions in

geographic information system (GIS), and more and more

people pay attention to the auto-generation of buffer zone.

Buffer generation usually makes arithmetic realizations

aiming at point, line, and polygon respectively, and it’s

more significant for linear objects. At present, buffer

generation algorithms can be generally classified into raster-

based and vector-based algorithms. The representative raster

algorithms include the distance-changing method

[2]

and

Mathematical morphology expanding algorithm

[3]

based on

raster data. Most raster algorithms are simple in principle

and easy to implement, but difficult to obtain vector

boundary, and with high memory cost and low precision as

its main disadvantages. So vector algorithm has become the

focus of researchers’ attentions. Vector algorithms are

usually more complex, but don’t lower the precision of

original data within the range of machine accuracy. A

common vector algorithm is the method of angular bisector

[8]

, which consists of three steps: (a) Draw simple parallel

lines for each line segment; (b) Carry on cusp smoothing

correction; (c) Process line self-intersection, but the method

is difficult to implement perfectly because of many

abnormal problems and complicated correction process.

There is another intuitive algorithm used by many GIS

software, which needs to obtain the respective buffer zone

for each line segment firstly and then merge the buffer zones

one by one by overlaying the polygons, and the algorithm

takes polygon overlay as the core problem, which involves

judging the relationship among a lot of line segments. In

order to deal with abnormal problems such as line segments

overlapping and improve computational efficiency, some

researchers present a number of optimizations for the

existing algorithms, for example, the self-adaptive data re-

sampling algorithm

[6]

, the buffer zone growth algorithm

based on the dynamic overlay thought

[7]

. Sun, Huang and

Ren

[5]

analyze the direction rule of arc segment passing

borderline intersection point and put forward the deleting

rule for directed arc segment to avoid choosing the arc

segment by line-area inclusion relation, Dong

[1]

uses the

rotating point transformation formula and recursion method

to simplify the process of the generation of parallel lines and

the smooth correction of sharp angle, Wu, Gong and Li

[9]

propose the concept of buffer curve and buffer generation

algorithm in aid of edge constrained triangle network, which

reduces the number of line segments involving clipping and

recombination and enhances the stability of algorithm and

time efficiency.

The existing vector algorithms usually include such

processes: curve segment intersection, clipping and

recombination for arc segments, judging inclusion relation,

searching the arcs owned by certain polygon, so it’s quite

complex to implement. The author holds that a simpler

algorithm can be built if buffer generation is considered just

as boundary tracing for buffer zone. Now the thought of

vector-based boundary tracing has been applied to many

spatial algorithm designs, for example, Yang, Wang and

[10]

adopt vector-based tracing method to construct the

centerline of two curves, Li and Zhang

[4]

also use a similar

tracing process to construct the gravity-based model

algorithm for the sake of combining linear features and

eliminating some tiny unsmooth on curves. Enlightened by

the idea of boundary tracing in these algorithms, this paper

describes a novel method of buffer generation based on

vector-based boundary tracing in terms of the characteristic

that it has the same distance from each point located on the

buffer boundary to buffer target.

II. V

ECTOR-BASED TRACING ALGORITHM

In most simple cases, the result graph of the buffer

generation is a simple connectivity area; when generating

buffer zone for the set of arcs or the shape of arc is much

complicated, the result maybe a complex area with one or

more holes (see Fig. 1).