A unified approach towards reconstruction of a planar point set

• The algorithm works for boundary samples as well as dot patterns.
• Theoretical guarantee has been provided.
• Extensive experimentation shows that this approach works well.

Reconstruction problem in R2R2 computes a polygon which best approximates the geometric shape induced by a given point set, S  . In R2R2, the input point set can either be a boundary sample or a dot pattern. We present a Delaunay-based, unified method for reconstruction irrespective of the type of the input point set. From the Delaunay Triangulation (DT) of S, exterior edges are successively removed subject to circle and regularity constraints to compute a resultant boundary which is termed as ec-shape and has been shown to be homeomorphic to a simple closed curve. Theoretical guarantee of the reconstruction has been provided using r  -sampling. In practice, our algorithm has been shown to perform well independent of sampling models and this has been illustrated through an extensive comparative study with existing methods for inputs having varying point densities and distributions. The time and space complexities of the algorithm have been shown to be O(nlogn) and O(n) respectively, where n is the number of points in S.

Figure optionsDownload high-quality image (398 K)Download as PowerPoint slide