Peeling the longest: A simple generalized curve reconstruction algorithm
| Autor: | Subhasree Methirumangalath, Ramanathan Muthuganapathy, Amal Dev Parakkat |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Vertex (graph theory)
Computer science Delaunay triangulation Point set General Engineering 020207 software engineering 02 engineering and technology Computer Graphics and Computer-Aided Design Graph Human-Computer Interaction Planar Outlier 0202 electrical engineering electronic engineering information engineering Curve reconstruction 020201 artificial intelligence & image processing Algorithm Piecewise linear approximation |
| Zdroj: | Computers & Graphics. 74:191-201 |
| ISSN: | 0097-8493 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect