An input-independent single pass algorithm for reconstruction from dot patterns and boundary samples

Given a set of points S∈R², reconstruction is a process of identifying the boundary edges that best approximates the set of points. In general, the set of points can either be derived from only the boundaries of the curves (called as boundary sample) or can be derived from both boundary and interior of the curves (called as dot pattern). Most of the existing algorithms focus towards reconstruction from only boundary samples, termed as curve reconstruction. Unfortunately many of them don't reconstruct when the input is of dot pattern type (called as shape reconstruction). In this paper, we propose an input-independent non-parametric algorithm for reconstruction that works for both dot patterns as well as boundary samples. The algorithm starts with computing the Delaunay triangulation of the given point set. An edge between a pair of triangles is marked for removal when the circumcenters lie on the same side of the edge. Further, we also propose additional criterion for removing edges based on characterizing a triangle by the distance between its circumcenter and incenter. To maintain a manifold output, a degree constraint is employed. The proposed approach requires only a single pass to capture both inner and outer boundaries irrespective of the number of objects/holes. Moreover, the same criterion has been employed for both inner and outer boundary detection. The experiments show that our approach works well for a variety of inputs such as multiple components, multiple holes etc. Extensive comparisons with state-of-the-art methods for various kinds of point sets including varying the sampling density and distribution show that our algorithm is either better or on par with them. Theoretical discussions on the algorithm have also been presented using ϵ-sampling and r-sampling. Limitations of the algorithm are also discussed.