Skip navigation

Efficient generation of simple polygons for characterizing the shape of a set of points in the plane

Efficient generation of simple polygons for characterizing the shape of a set of points in the plane

Duckham, Matt, Kulik, Lars, Worboys, Mike and Galton, Antony (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition, 41 (10). pp. 3224-3236. ISSN 0031-3203 (doi:https://doi.org/10.1016/j.patcog.2008.03.023)

Full text not available from this repository.

Abstract

This paper presents a simple, flexible, and efficient algorithm for constructing a possibly non-convex, simple polygon that characterizes the shape of a set of input points in the plane, termed a characteristic shape. The algorithm is based on the Delaunay triangulation of the points. The shape produced by the algorithm is controlled by a single normalized parameter, which can be used to generate a finite, totally ordered family of related characteristic shapes, varying between the convex hull at one extreme and a uniquely defined shape with minimum area. An optimal O(n log n) algorithm for computing the shapes is presented. Characteristic shapes possess a number of desirable properties, and the paper includes an empirical investigation of the shapes produced by the algorithm. This investigation provides experimental evidence that with appropriate parameterization the algorithm is able to accurately characterize the shape of a wide range of different point distributions and densities. The experiments detail the effects of changing parameter values and provide an indication of some "good'' parameter values to use in certain circumstances. © 2008 Elsevier Ltd.

Item Type: Article
Additional Information: [1] First published: October 2008. [2] Published as: Pattern Recognition, (2008), Vol. 41, (10), pp. 3224–3236. [3] Pattern Recognition is the journal of the Pattern Recognition Society.
Uncontrolled Keywords: convex hull, alpha shape, shape analysis, cartography, GIS
Subjects: Q Science > Q Science (General)
Pre-2014 Departments: School of Computing & Mathematical Sciences
Related URLs:
Last Modified: 14 Oct 2016 09:24
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
URI: http://gala.gre.ac.uk/id/eprint/10091

Actions (login required)

View Item View Item