Peeling the longest: A simple generalized curve reconstruction algorithm. (August 2018)

• Record Type: Journal Article
• Authors: Parakkat, Amal Dev; Methirumangalath, Subhasree; Muthuganapathy, Ramanathan
• Is Part Of: Computers & graphics. Volume 74(2018)
• Page Start: 191
• Page End: 201
• Publication Date: 2018-08
• Subjects: Curve reconstruction -- Delaunay triangulation -- Noise simplification -- Self-intersection; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2018.05.015
• Languages: English
• ISSNs: 0097-8493

Abstract

Highlights: A generalized Delaunay triangulation based algorithm is proposed for curve reconstruction. Theoretical guarantee has been provided using ϵ-sampling. Procedure has been devised for reconstructing self-intersections. The algorithm can identify the presence of noise in the data, simplify the data and perform reconstruction. Extensive comparative studies demonstrated that our algorithm is comparable or better than other existing methods. Graphical abstract: Abstract: Given a planar point set sampled from a curve, the curve reconstruction problem computes a polygonal approximation of the curve. In this paper, we propose a Delaunay triangulation-based algorithm for curve reconstruction, which removes the longest edge of each triangle to result in a graph. Further, each vertex of the graph is checked for a degree constraint to compute simple closed/open curves. Assuming ϵ-sampling, we provide theoretical guarantee which ensures that a simple closed/open curve is a piecewise linear approximation of the original curve. Input point sets with outliers are handled as part of the algorithm, without pre-processing. We also propose strategies to identify the presence of noise and simplify a noisy point set, identify self-intersections and enhance our algorithm to reconstruct such point sets. Perhaps, this is the first algorithm to identify the presence of noise in a point set. Our algorithm is able to detect closed/open curves, disconnected components, multiple holes and sharp corners. The algorithm is simple to implement, independent of the type of input, non-feature specific and hence it is a generalized one. We have performed extensive comparative studies to demonstrate that our method is comparable or better than other existing methods. Limitations of our approach have also been discussed.