Delaunay-based representation of surfaces defined over arbitrarily shaped domains


A method for constructing surface models from a discrete set of arbitrarily distributed data is described. The surface is represented as a network of planar, triangular faces with vertices at the data points, which is built up on a Delaunay triangulation of the data point projections on thex−y plane. In the paper, the problem of triangulating arbitrarily shaped domains is considered. A new definition of Delaunay triangulation of a set of points constrained by a polygonal boundary is introduced, and some of its basic properties are briefly discussed. A new incremental algorithm for constructing a Delaunay triangulation of an arbitrarily shaped domain is described. This method is also demonstrated to be well suited to generate surface approximations at predefined levels of accuracy, which are based on significant subsets of selected data points.

Computer Vision, Graphics, and Image Processing