The computation of convex hulls is a fast and useful facility, but does not necessarily match the requirements of the analyst attempting to define a region enclosing a set of objects. We have already noted, for example, that the method is strongly affected by the location of outliers, and as a result may enclose large regions that are of no interest or relevance to the analysis. Whilst the convex hull of a point set in the plane is unique, any number and variety of non-convex hulls may be generated. Such alternative hulls may meet certain pre-defined application-related criteria. Examples might include: the hull must be a polygon; the polygon must be as near convex as possible; the polygon must have the smallest possible area enclosing the set as possible; the polygon must reflect the density of points in the sample; the polygon must assign each point its own nominal region and include all points.

There are three principal methods for generating non-convex polygonal hulls (NCPHs) that meet specified criteria. These are: (a) expansion; (b) contraction; and (c) density contouring. Some of these methods may be implemented using most GIS packages, but the majority require some programming. TNTMips includes facilities for computing several of the variants described within its Polygon Fitting facility. These algorithms were originally developed to help identify animal “home ranges” but may be utilised in many areas — see for example, Harvey and Barbour (1965), White and Garrott (1990, pp 145-82, “Home range estimation”) and Mitchell (2006).

Case (a), expansion: in this case the non-convex hull is created by assigning each point a surrounding region and then growing this region until all points are covered and a continuous external hull is obtained. This may be achieved in several ways. One method is to compute Voronoi polygons for all the points and use the external boundary of the (finite) set as the NCPH (see for example Figure 4‑32B). This leaves the problem of how to treat the points that make up the convex hull. An alternative non-polygonal approach is to buffer all the points and increase the buffer width until a single merged zone is formed. This process may highlight the need to consider the benefits of using several sub-regions rather than a single region — for example, in cases where many of the observations lie near the region boundary with a large central region containing few observations. Yet another alternative is to overlay the study region with a rectangular grid and define the NCPH with reference to this (for example, requiring that the grid includes every point and a minimum number of cells surrounding every point). Where necessary interstitial gaps in the grid are grown to ensure a contiguous overall region is achieved without necessarily growing the external boundary.

Case (b), contraction: this case involves reduction of the convex hull according to selected rules. The simplest of these is a systematic area minimisation procedure. First the area of the convex hull is computed. Next a point on the convex hull is removed and the new convex hull recomputed. The area of this new region is calculated and stored. The process is repeated for all points on the original convex hull and the point that results in the greatest decrease in area is permanently removed. The procedure then iterates until only a pre-defined percentage of the original points remain (e.g. 90%) or the area has been reduced by a given percentage. The result is a convex hull of an optimised subset of the original points. A second procedure, which results in a NCPH, involves a form of shrinkage of the convex hull around the point set, rather like a plastic bag full of small balls having the air removed. In this method the longest linear segment of the convex hull is selected and replaced with two segments connecting the original two end points via an intermediate point that is the closest to the original line — almost the reverse of point-weeding (Section 4.2.4). The process continues until the overall area enclosed has been reduced by a pre-determined amount, or a number of iterations have been reached — 10 is a typical number to use. Hybridisation of this method with the preceding method is possible.

Note that in the majority of contraction and expansion methods the result is either a grid or polygon form, with the latter having straight line edges. Procedures also exist in which the restriction of convexity, connectedness and/or to straight edges is relaxed, e.g. forming so-called alpha hulls or alpha shapes where concavities and unconnected sets are permitted. Consider a circle or disc of radius 1/alpha. When alpha is small (close to zero) the disc radius is large (infinite at 0). With a large enough radius the disc can be placed over any given point set such that the set is fully enclosed and precisely two points from the set lie on its boundary (Figure 4‑27A). These are then typically connected by a straight line, and a complete hull can thus be generated. Figure 4‑27B to D illustrate the results obtained by varying alpha, as explained below.

Figure 4‑27 Alpha hulls

a. alpha>0

b. alpha>0, increasing positive

c. alpha<0

d. alpha<0, increasing negative

In Figure 4‑27B, with larger alpha the disc radius is reduced and only a limited number of circles can be drawn that enclose the point set and have a pair of points from the set on their boundary. The resulting alpha shape excludes many of the original points. Figure 4‑27C and Figure 4‑27D illustrate the shapes formed as alpha becomes increasingly negative. In this case the complement of the positive disc shapes are used. Some have likened this process in 3D to using an ice-cream scoop of a given radius to extract the 3D solid surrounding the immovable point set ― smaller scoops can remove more material until the form becomes increasingly convex and starts to break up. Specialised tools exist for constructing such hulls in 2D and 3D and are of particular application in visualisation of environmental and similar datasets. The images shown in Figure 4‑27 were generated using the interactive Java applet developed by François Bélair whilst at the Computational Geometry Laboratory of McGill University.

Case (c), density contouring: this last of the three cases involves overlaying the study region with a (fine) grid and then computing an estimated point density at each grid point. There are several ways in which the density can be estimated, but the most widely used, within GIS and related packages, is kernel estimation (discussed in some detail in Section 4.3.4). Once a density value has been assigned to each intersection or cell, the region taken for the NPCH may be determined by specifying a threshold density and using the grid directly, or by contouring the grid. The final result may then be used directly or converted to polygonal form, depending on the requirement.