Efficient generation of simple polygons for characterizing ...

1 Efficient generation of simple polygons forcharacterizing the shape of a set of points inthe planeMatt Duckham1, Lars Kulik2, Mike Worboys3, Antony Galton41. Department of GeomaticsUniversity of Melbourne, Victoria, 3010, Australia2. Department of Computer Science and Software EngineeringUniversity of Melbourne, Victoria, 3010, Australia3. National Center for Geographic Information and AnalysisUniversity of Maine, Orono, ME 04469, USA4. Department of Computer ScienceUniversity of Exeter, Exeter EX4 4QF, UKAbstractThis paper presents a simple , flexible, and efficient algorithm for constructing apossibly non-convex, simple polygon that characterizes theshape of a set of inputpoints in the plane, termed acharacteristic shape.

2 The algorithm is based on theDelaunay triangulation of the points. The shape produced bythe algorithm is con-trolled by a single normalized parameter, which can be used to generate a finite,totally ordered family of related characteristic shapes, varying between the convexhull at one extreme and a uniquely defined shape with minimum area. An optimalO(nlogn) algorithm for computing the shapes is presented. Characteristic shapespossess a number of desirable properties, and the paper includes an empirical in-vestigation of the shapes produced by the algorithm. This investigation providesexperimental evidence that with appropriate parameterization the algorithm is ableto accurately characterize the shape of a wide range of different point distributionsand densities.

3 The experiments detail the effects of changing parameter values andprovide an indication of some good parameter values to usein certain Duckham1, Lars Kulik2, MikeWorboys3, Antony Galton4). (Matt Duckham1, Lars Kulik2, Mike Worboys3,Antony Galton4).Preprint submitted to Elsevier11 January 20081 IntroductionThe construction of convex hulls is a fundamental operation in computationalgeometry. In the Cartesian plane, the convex hull of a set of pointsSis thesmallest convex polygon which contains all points inS. However, for sets ofpoints with a pronounced non-convex distribution the convexhull can neverprovide good characterization of that this paper we present an algorithm for building non-convex hulls.

4 Thealgorithm is as efficient as an optimal convex hull algorithm,O(nlogn) com-putation time fornpoints. For a finite set of input pointsP, the algorithmproduces a simple , possibly non-convex polygon that contains all the points inPand is contained within and possibly equal to the convex hull. We refer tothe polygons produced by the algorithm as characteristic shapes or simply (chi) features of our characteristic shapes are worth highlighting at this , while there exists only one convex hull for a set of pointsthere canbe many different characteristic shapes. There is no correct characteristicshape.

5 We argue that in many cases the algorithm yields abettercharacteriza-tion of distribution of a set of points than the convex hull. To illustrate, figure1 shows a gallery of convex and characteristic shapes for some example pointsets with clearly non-convex distributions. However, decidingprecisely whatconstitutes a better characterization of the distributionof a set of points isas much a matter for human cognition and preference as for computationalgeometry. Despite this inherent underspecification in the problem statement,our contention is that the characteristic shapes produced by our algorithmare useful.

6 Further, this paper explores experimentally someof the attributesof a shape which may constitute better or worse characterizations of thedistribution of a set of points, and proposes some natural choicesfor parame-terizing the characteristic shape algorithm in a way that generates a uniquelydefined , characteristic shapes are simple (Jordan) polygons , homeomorphic tothe closed unit disk. Thus, characteristic shapes are simply connected (all ofone piece containing no holes nor islands) and regular. In some cases, how-ever, the distribution of a set of points may be best characterized by multiple(possibly non-convex) polygons enclosing disconnected regions of space ( ,an i or = shape).

7 In this paper we do not consider directly such cases,and are primarily concerned with cases where the distributionof points canbe adequately characterized as a single simple polygon. However, it is possibleto deal with such cases indirectly by first preprocessing the inputpoint set topartition it into subsets, each of which may be adequately characterized by asingle simple polygon, explored briefly in section In othercases where the2 The convex hull ofPPoint setPA -shape ofPFig. 1. Gallery of convex hulls and -shapes for several point sets in the planedistribution of points is best characterized using a polygon containing one ormore holes ( , an 8 shape), the characteristic shape algorithm presentedin this paper will not be able to generate these holes.

8 It will, however, stillsuccessfully generate a characterization of the external edgeof such a Related workAn early, and influential, attempt to characterize the shape ofa set of points isdue to [1], which introduced a construction known as -shape as a general-ization of the convex hull. For a finite setPof points in the plane, the -hull for 6= 0 is the intersection of all closed discs of radius 1/ containing all thepoints ofP(where for negative values of a closed disk of radius, 1/ is inter-preted as the complement of an open disk of radius 1/ ). As approaches0, the -hull approaches the ordinary convex hull, and therefore the 0-hull isstipulated tobethe convex hull.

9 The -shape is a straight-line graph (usuallya polygon) derived in a straightforward manner from the -hull. When = 0,this is the convex hull, and for large negative values of it related notion,A-shape, was introduced in [2]. Given a finite set of pointsP,and a setA(which evidently needs to be disjoint fromP, although the authorsdo not specify this), we can define theA-shape ofPby first constructing theVoronoi diagram forA Pand then joining together any pair of pointsp, q Pwhose Voronoi cells both border each other and border some common Voronoicell containing a point ofA. The edgespqbelong to the Delaunay triangulationofA P: they are the A-exposed edges of the triangulation.

10 An importantissue discussed in the paper is how to chooseAso that theA-shape ofPis adequate. In a later paper [3], theA-shape is used as the basis for an onion-peeling method, by analogy with the popular convexonion-peelingmethod for organizing a set of points and extracting a central embeddedconvex shape from them [4].Two rather different constructs,r-shapeands-shape, were defined in [5] asfollows. The initial set of pointsPis assumed to be adot pattern, that is, aplanar point set whose elements are clearly visible as well as fairly densely andmore or less evenly distributed.