Efficient generation of simple polygons for characterizing the shape of a set of points in the plane
Matt Duckham,
Lars Kulik,
Mike Worboys, and
Antony Galton
In Pattern Recognition, Volume 41, issue 10, October 2008, pages 3224-3236.
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.
Antony Galton
Last modified: Mon Mar 29 13:05:45 BST 2010