A unified approach towards reconstruction of a planar point set. (October 2015)

• Record Type: Journal Article
• Authors: Methirumangalath, Subhasree; Parakkat, Amal Dev; Muthuganapathy, Ramanathan
• Is Part Of: Computers & graphics. Volume 51(2015)
• Page Start: 90
• Page End: 97
• Publication Date: 2015-10
• Subjects: Delaunay Triangulation -- Reconstruction -- Dot pattern -- Boundary sample; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2015.05.025
• Languages: English
• ISSNs: 0097-8493

Abstract

Abstract: Reconstruction problem in R 2 computes a polygon which best approximates the geometric shape induced by a given point set, S . In R 2, 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 ( n log n ) and O ( n ) respectively, where n is the number of points in S . Abstract : Graphical abstract: Abstract : Highlights: The algorithm works for boundary samples as well as dot patterns. Theoretical guarantee has been provided. Extensive experimentation shows that this approach works well.