A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering

• A fully automatic algorithm using the structural properties of Delaunay triangles.
• External boundary as well as an internal hole detection have been addressed.
• Demonstrate the efficacy with varying point set densities and distributions.
• Theoretical guarantee of the algorithm has been presented.

In this paper, we present a fully automatic Delaunay based sculpting algorithm for approximating the shape of a finite set of points SS in R2R2. The algorithm generates a relaxed Gabriel graph (RGGRGG) that consists of most of the Gabriel edges and a few non-Gabriel edges induced by the Delaunay triangulation. Holes are characterized through a structural pattern called as body-arm formed by the Delaunay triangles in the void regions. RGGRGG is constructed through an iterative removal of Delaunay triangles subjected to circumcenter (of triangle) and topological regularity constraints in O(nlogn)O(nlogn) time using O(n)O(n) space.We introduce the notion of directed boundary samples which characterizes the two dimensional objects based on the alignment of their boundaries in the cavities. Theoretically, we justify our algorithm by showing that under given sampling conditions, the boundary of RGGRGG captures the topological properties of objects having directed boundary samples. Unlike many other approaches, our algorithm does not require tuning of any external parameter to approximate the geometric shape of point set and hence human intervention is completely eliminated. Experimental evaluations of the proposed technique are done using L2L2 error norm measure, which is the symmetric difference between the boundaries of reconstructed shape and the original shape. We demonstrate the efficacy of our automatic shape reconstruction technique by showing several examples and experiments with varying point set densities and distributions.