Line Smoothing and point-weeding

Navigation:  Building Blocks of Spatial Analysis > Geometric and Related Operations >

Line Smoothing and point-weeding

Previous pageReturn to chapter overviewNext page

Polylines and polygons that have a large number of segments may be considered over-complex or poor representations of the original features, or unsuitable for display and printing at all map scales (a problem of map generalization). A range of procedures exist to achieve simplification of lines in such cases, including those illustrated in Figure 4‑7.

A. Point weeding is a procedure largely due to Douglas and Peuker (1973) — for a fuller discussion, see Whyatt and Wade (1988) and Visvalingam and Whyatt (1991). In the example shown in Figure 4‑7a the original black line connecting all the vertices 1 to 10 is progressively simplified to form the green line shown. The procedure commences by connecting point 1 (the anchor) to point 10 (the floating point) with a temporary line (the initial segment). This enables point 8 to be identified as the vertex that deviates from this initial segment by the greatest distance (and more than a user-defined tolerance level, shown here by the bar symbol on the left of the upper diagram). Euclidean distance squared is sufficient for this algorithm and is significantly faster to compute. Point 10 is then directly connected to point 8 and point 9 is dropped. A new temporary line is drawn between point 8 (the new floating point) and 1 and the process is repeated. This time points 5, 6 and 7 are dropped. Finally point 3 is dropped and the final line contains only 4 segments and 5 nodes (1, 2, 4, 8 and 10).

This process can be iterated by moving the initial anchor point to the previous floating point and repeating the process for further simplification. Some implementations of this algorithm, including those of the original authors, fail to handle exceptions where the furthest point from the initial segment is one end of a line that itself lies close to the initial segment. Ebisch (2002) addresses this error and provides corrected code for the procedure. The procedure is very sensitive to the tolerance value selected, with larger values resulting in elimination of more intermediate points.

Figure 4‑7 Smoothing techniques

clip0031.zoom30

A number of GIS products provide a range of simplification methods. The default in ArcGIS is point-weeding (POINT_REMOVE) but an alternative BEND_SIMPLIFY which removes extraneous bends is also available.

B. Simple smoothing utilizes a family of procedures in which the set of points is replaced by a smooth line consisting of a set of curves and straight line segments, closely following but not necessarily passing through the nodes of the original polyline. This may be achieved in many ways with Figure 4‑7b showing one example.

C. Spline smoothing typically involves replacing the original polyline with a curve that passes through the nodes of the polyline but does not necessarily align with it anywhere else, or approximates the point set rather like a regression fit (Figure 4‑7c). A range of spline functions and modes of operation are available (including in some cases Bézier curves and their extension, B-splines), many of which involve using a series of smoothly connected cubic curves. In some cases additional temporary nodes or “knots” are introduced (e.g. half way between each existing vertex) to force the spline function to remain close to the original polyline form.

Each method and implementation (including the selection of parameters and constraints for each variant) will have different results within and across different GIS packages and the process will not generally be reversible. Furthermore, different GIS packages tend to offer only one or two smoothing procedures, so obtaining consistent results across implementations is almost impossible. Note that once a polyline or polygon has been subject to smoothing its length will be altered, becoming shorter in many cases, and enclosed areas will also be altered though generally by a lesser amount in percentage terms. The orientation of the line segments also changes dramatically, but not the relative positions of the two end nodes, so the end-node to end-node orientation is retained. Determination of the length and area of amended features may require numerical integration utilizing fine division of the smoothed objects rather than the simple procedures we have described in Section 4.2, Geometric and Related Operations. Further discussion of smoothing, including additional approaches, is provided in Chapter 6, Surface and Field Analysis. These methods have been described by McMaster and Shea (1992) as forms of feature generalization (see also, Section 2.1.9, Detail, resolution, and scale). Other forms of generalization include: amalgamation (replacing a large number of separate area features or cells by a smaller number, e.g. a single feature); merging (replacing several line features with a single line feature); and collapse  (replacing an area object by a point, cells or a combination of points and lines, or replacing dual lines by a single centerline. For a fuller discussion of generalization issues see the ESRI (1996) white paper, available via the ESRI web site.