×

Reconstructing curves with sharp corners. (English) Zbl 0985.68081

Summary: We present a heuristic to reconstruct nonsmooth curves with multiple components. Experiments with several input data reveals the effectiveness of the algorithm in contrast with the other competing algorithms.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amenta, N.; Bern, M., Surface reconstruction by Voronoi filtering, Discrete Comput. Geom., 22, 481-504 (1999) · Zbl 0939.68138
[2] Amenta, N.; Bern, M.; Eppstein, D., The crust and the \(β\)-skeleton: combinatorial curve reconstruction, Graphical Models Image Process., 60, 125-135 (1998)
[3] Amenta, N.; Choi, S.; Dey, T. K.; Leekha, N., A simple algorithm for homeomorphic surface reconstruction, (Proc. 16th ACM Sympos. Comput. Geom. (2000)), 213-222 · Zbl 1374.68636
[4] Althaus, E.; Mehlhorn, K., Polynomial time TSP-based curve reconstruction, (Proc. 11th ACM-SIAM Sympos. Discrete Algorithms (2000)), 686-695 · Zbl 0954.65011
[5] Attali, D., \(r\)-regular shape reconstruction from unorganized points, (Proc. 13th ACM Sympos. Comput. Geom. (1997)), 248-253 · Zbl 0904.68172
[6] Bernardini, F.; Bajaj, C. L., Sampling and reconstructing manifolds using \(α\)-shapes, (Proc. 9th Canadian Conf. Comput. Geom. (1997)), 193-198
[7] Dey, T. K.; Kumar, P., A simple provable algorithm for curve reconstruction, (Proc. ACM-SIAM Sympos. Discrete Algorithms (1999)), 893-894 · Zbl 1052.65509
[8] Dey, T. K.; Mehlhorn, K.; Ramos, E. A., Curve reconstruction: connecting dots with good reason, Comput. Geom. Theory Appl., 15, 229-244 (2000) · Zbl 0955.68113
[9] Edelsbrunner, H.; Kirkpatrick, D. G.; Seidel, R., On the shape of a set of points in the plane, IEEE Trans. Inform. Theory, 29, 551-559 (1983) · Zbl 0512.52001
[10] de Figueiredo, L. H.; de Miranda Gomes, J., Computational morphology of curves, Visual Comput., 11, 105-112 (1995)
[11] Giesen, J., Curve reconstruction, the TSP, and Menger’s theorem on length, (Proc. 15th ACM Sympos. Comput. Geom. (1999)), 207-216
[12] C. Gold, J. Snoeyink, Crust anti-crust: a one-step boundary and skeleton extraction algorithm, to appear in Algorithmica, 2000; also in: Proc. 15th. ACM Sympos. Comput. Geom., 1999, pp. 189-196; C. Gold, J. Snoeyink, Crust anti-crust: a one-step boundary and skeleton extraction algorithm, to appear in Algorithmica, 2000; also in: Proc. 15th. ACM Sympos. Comput. Geom., 1999, pp. 189-196
[13] Hoppe, H.; DeRose, T.; Duchamp, T.; McDonald, J.; Stuetzle, W., Surface reconstruction from unorganized points, (SIGGRAPH 92 (1992)), 71-78
[14] Melkemi, M., \(A\)-shapes and their derivatives, (Proc. 13th ACM Sympos. Comput. Geom. (1997)), 367-369
[15] O’Rourke, J.; Booth, H.; Washington, R., Connect-the-dots: A new heuristic, Comput. Vision Graph. Image Process., 39, 258-266 (1987) · Zbl 0657.68118
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.