Transfer: blog.csdn.net/wsh6759/cat…
I. Introduction to the algorithm:
Buffer analysis is a kind of proximity analysis, which is to establish a strip area with a certain width around a geographical entity or space object in order to identify its impact on the surrounding ground objects. Buffer zone, as an independent data layer, can be applied to the spatial analysis of roads, rivers, environmental pollution sources, settlements, radiation sources, etc., providing scientific basis for some application purposes. In addition, combined with different professional models, it can play an important role in life, military, urban and rural planning and other fields.
According to different geometric types of point, line and plane, the way of establishing buffer is different from each other. It is simple to build point buffer, that is, taking a point element as the center of the circle and taking the buffer radius R as the circle, the buffer of point element is obtained. The buffer of line elements takes line as the axis and R as the distance as parallel lines on both sides. Two semicircular arcs are constructed at both ends of the line to form buffer with parallel lines. The establishment of the surface buffer takes the boundary of the surface elements as the baseline to make parallel lines inward and outward, and the area in the parallel line and baseline is the surface buffer. In addition, the grid data can be buffered, based on different model equations to create dynamic buffer, the basic method is similar regardless of what kind of data to create buffer. (See Reference 4)
Buffer algorithm modules are available in GRASS, GEOS and JTS. GEOS is the C++ version of JTS.
Applications using GEOS include PostGIS (C API),MapServer (C API),Quantum GIS (C API),OGR (C API),GRASS (C API),Shapely (C API),INGRES (C API) API),SpatiaLite (C API),MapGuide Open Source GeoDjango (C API),MapWindow GIS (C API), Osm2pgsql (C++ API),osgEarth (C++ API),MonetDB (C API), rGEOS (C API), there are packages of FME and Autodesk MapGuide Enterprise.
GRASS version introduction (see http://grass.itc.it/gdp/html_grass63/v.buffer.html) (related to the project introduction to see http://download.osgeo.org/grass/grass6_progman/)
Here only list the relevant source code, to be listed later comparison algorithm analysis, algorithm performance, etc.
two Algorithm description and pseudo-code demonstration
There are two kinds of buffer implementation algorithms: vector method and grid method. Among them, the vector method has a small amount of data and is relatively mature. The raster image needs to carry out Boolean operation between raster pixels. When the buffer is large, it will bring heavy calculation load, and there are certain limitations in practical application.
Vector method algorithms generally follow the following steps:
Point: determine the center point — take the center point as the center of the circle and R as the radius to generate a circle — get the buffer boundary;
Line and plane: determine axis — generate parallel curve of central axis with distance R — process angular arc — calculate intersection and merge operation of generated arc — generate buffer boundary;
Commonly used vector data center line expansion algorithm:
Angle points in line method
Basic idea: namely “simple parallel line method”, make parallel lines on both sides of the axis, form a sharp Angle at the corner, and form an arc at both ends to form a buffer zone.
Defects: it is difficult to ensure the same width of the left and right sides of the buffer at sharp corners; The correction process is complicated, which is mainly reflected in the large and small axis bending Angle. The algorithm model is complex, mainly because of the need to deal with many anomalies in the process of geometry generation.
Convex arc method
Basic idea: as the name implies, it is to use circular arc to replace sharp Angle on the outside of the corner, and the method of sharp Angle is still used on the inside to generate buffer.
Implementation steps:
1. Straightness judgment: judge whether the adjacent three points are on the same line;
2. Judging the convexity and concavity of the bending point to determine which side of the corner is intersected by a straight line and which side is connected by an arc;
3. The insertion of convex arc, that is, the arc formed on the outside of the corner is connected with the line segment on both sides;
4. Identification and processing of edge relation, island polygons participate in the formation of buffer boundary, overlapping polygons do not participate in the formation of buffer boundary;
5. The formation of buffer boundary is to merge overlapping areas and draw peripheral edges, including the outline of island polygon, to form the final buffer boundary.
In the buffer algorithm, one problem that needs to be paid attention to is the overlap and merge of buffer polygons, including the overlap of the same element buffer and the overlap of multiple elements buffer. The grid in the grid data buffer has a value corresponding to its impact degree. If the overlapping areas have the same impact degree, any value should be taken. If the overlapping areas have different impact degree, the method of replacing the small impact degree with the large impact degree is adopted. There are three processing algorithms for vector data: mathematical operation; Vector-raster conversion method; Vector – raster hybrid method. (See Reference 4)
Three, the source code
1, the administrators of the source code (source location in administrators/source/operation/buffer/BufferOp CPP) :
GRASS \vector\ v.booffer and GRASS -. SRC \vector\ v.booffer, The algorithm is based on grass\lib\vector\Vlib\buffer.c and grass\lib\vector\Vlib\buffer2.c.
The first version is buffer.c (treated separately by point, line, and plane types: points and lines are treated as one class; Surfaces are decomposed into line objects and finally merged into surface objects).
The second version is the buffer2.c version (this is the Google Summer of Code 2008 source Code, the dot, line and face buffer separately).
Iv. References
a) GRASS (Geographic Resources Analysis Support System)
grass.osgeo.org/
staging.grass.osgeo.org/
github.com/OSGeo/grass
b) GEOS (Geometry Engine – Open Source) trac.osgeo.org/geos/
C) JTS (JTS Topology Suite) www.tsusiatsoftware.net/jts/main.ht…
D) GIS buffer and the algorithm is applied to implement www.blogjava.net/flyingis/ar…
E) Buffer to introduce www.volusia.org/gis/buffer….
F) Fundamentals of Geographic Information System Algorithms, author: Zhang Hong, Wen Yongning, Liu Aili et al., Science Press
5. Academic papers
1. Overview and comparison of GIS spatial buffer generation algorithms
2. Research and implementation of buffer algorithm based on grid run and boundary vector
Fang Jinyun, Chinese Academy of Sciences VegaGIS
