Polygon decomposition

<< Click to Display Table of Contents >>

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

Polygon decomposition

Polygons may be divided into smaller sections in many different ways, for a wide variety of reasons. Most vector GIS packages support some decomposition procedures, through overlay of a template or cookie cutter polygons (e.g. the Clip operation in ArcGIS) and/or through the provision of explicit decomposition procedures. For example, complex polygons with convoluted boundaries may be divided up into a series of non-overlapping convex polygons. These polygons will have centers (e.g. centers of gravity) that are guaranteed to lie inside the original polygon. The multiple centers thus generated may then be used to assist labeling or in assigning data in spatial overlay operations. Polygons can also be divided into non-overlapping triangles, in a variety of different ways. Manifold, for example, provides commands to perform both such decompositions: Transform|Decompose to convex parts, and Transform|Decompose to triangles. A (simple) polygon with n vertices or nodes can be triangulated into n‑2 triangles using a procedure known as diagonal triangulation. This form of triangulation utilizes existing polygon vertices, but other triangulations are possible if additional internal vertices are permitted. With m such internal vertices (or Steiner points) a total of n+2m‑2 triangles will be generated.

A polygon can also be skeletonised, providing an additional view of its form and key internal points. In Figure 4‑14, below, bands of increasing distance in constant steps from the external boundary are shown. These terminate in a single central point and generate one intermediate point. Connecting these internal points to the polygon nodes creates a skeleton of lines known as the medial axis of the polygon. The medial axis is not necessarily comprised of straight line segments. In practice skeletonization is carried out using algorithms known generically as medial axis transforms, and may be computed in linear time (i.e. as a linear function of the number of polygon vertices, see Chin et al., 1999). The single central point in the example shown in Figure 4‑14 is the center of the largest inscribed circle.

Applications of skeletonization include label placement, especially useful for complex polygons which are concave and/or contain holes, and polygon generalization/smoothing, which has been applied to closed polygons and to open regions such as contour maps — see for example Gold and Thibault (2001). The reverse process, “given a skeleton (e.g. stream pattern) reconstruct a landscape”, has also been the subject of much research. Furthermore, the dual of skeletonization is one form of polygon decomposition, although not generally the version implemented within currently available GIS software. Neither does such software tend to provide skeletonization facilities, but asymmetric buffering (see Section 4.4.4, Buffering), which is a commonly available feature, enables first-stage skeletonization to be carried out.

Figure 4‑14 Skeletonised convex polygon


Raster-based spatial analysis makes limited use of region centers, where they occur mainly in connection with patch analysis. Patches are typically collections of contiguous cells that have the same or similar attribute values, although in some instances a patch may include holes. The commonest notion of center in such cases is the unweighted or weighted mean value of the cell coordinates of the patch under consideration. In cases where cell values (weights) are counts of points falling in each cell the weighted mean can be regarded as equivalent to the simple mean value (minimum of squared Euclidean distances) for point patterns.