A sampling type discernment approach towards reconstruction of a point set in R2

In this paper, we propose a Delaunay triangulation based algorithmic framework for the 2D point set type discernment and its reconstruction. The point set discernment deals with determining whether the given point set S consists of only the points sampled along the boundary of an object (referred to as boundary sample) or S is distributed across the object (referred to as dot-pattern). In general, the existing approaches deal with the reconstruction of an a priori known input type - boundary sample or dot-pattern. Our approach works on both sets of input data type by first identifying the input type that a given point set belongs to. To distinguish the point set type, we introduce the notion of Petal-Ratio(P R) which captures the ratio of the longest edge to the smallest edge emanating from a vertex in Delaunay triangulation. Further, we employ the Petal-Ratio as the essence to design simple reconstruction algorithms pertaining to each input type that unveil the shape of the object hidden in the given point set. The reconstruction algorithms start with computing the Delaunay triangulation of the given point set and for each vertex, the Petal-Ratio is calculated. Following this, the edges are removed based on the value of the PR for every vertex to arrive at the boundaries. Theoretical analysis of determining appropriate values of P Rs under epsilon- sampling and minimal reach sampling models have been presented. Unlike many other algorithms, our approach is non-parametric and non-feature specific that can capture features like disconnected components, multiple holes even with the presence of outliers, self-intersection (only for boundary sample) and open curves (only for boundary sample). Moreover, our algorithms take only one pass to reconstruct the hole boundaries as well as outer boundary irrespective of the object features like the number of holes and the number of components. The comparative analysis shows that our algorithms perform equally well or better than their counterparts for the objects with contrasting features. We also demonstrate that the proposed idea can be easily extended to surface reconstruction. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

This paper proposes a Delaunay triangulation based algorithmic framework for discerning and reconstructing 2D point sets. By introducing the concept of Petal-Ratio, the algorithm can identify the input type of a given point set and design simple reconstruction algorithms to reveal the hidden shape of the object. The non-parametric algorithms are able to capture various features and perform well according to comparative analysis.