Curve Reconstruction

Curve Reconstruction

Curve Reconstruction: Given a set of samples from a curve we wish to compute a polygonal reconstruction of the curve, i.e., points should be joined by edges in the order they appear on the curve.

Reconstruction of smooth curves: NN-crust

We provide a very simple nearest neighbor algorithm for reconstructing smooth curves. The algorithm works in any dimension for curve reconstruction. We show a reconstructed curve in 3D below.

T. K. Dey and P. Kumar. A simple provable algorithm for curve reconstruction . Proc. 10th. ACM-SIAM Symposium on Discrete Algorithms (SODA '99) 1999, 893--894

A reconstructed curve in 3D

Check this Program implementation of NN-crust with topological clean-up.

Also check PROGRAM implemented at MPI, Germany.

Reconstruction of curves with or without boundary: Conservative-crust

Smooth curves with boundary points need special attention since the usual methods such as crust and NN-crust cannot handle such curves. We devise an algorithm for reconstructing curves with boundary points.

T. K. Dey, K. Mehlhorn and E. Ramos. Curve reconstruction: connecting dots with good reason . Comput. Geom. Theiry & Appl., Vol. 15 (2000), 229-244. Also in Proc. 15th. Sympos. Computational Geometry 1999, 197--206.

Crust

NN-crust

Conservative crust

Right two pictures are generated with conservative-crust, left two figures with crust, and middle two figures with NN-crust. Check this PROGRAM developed at MPI, Germany.

Reconstruction of curves with corners: Gathan

Nonsmooth curves pose problem for curve reconstruction. The sampling condition required by crust and all other algorithms with guarantee cannot be satisfied near corners. We designed an algorithm to handle curves with corners.

T. K. Dey and R. Wenger. Reconstructing curves with sharp corners. Computational Geometry Theory Applications, vol 19, 2001, 89--99.

T. K. Dey and R. Wenger. Fast reconstruction of curves with sharp corners. Computational Geometry Theory Applications, 2002, to appear.

Output of Gathan

Download this program (guaranteed reconstruction) implemented by R. Wenger

Examples