Reconstructing curves without Delaunay computation
A new non-Delaunay-based approach is presented to reconstruct a curve, lying in 2- or 3-space, from a sampling of points. The underlying theory is based on bounding curvature to determine monotone pieces of the curve. Theoretical guarantees are established. The implemented algorithm, based heuristically on the theory, proceeds by iteratively partitioning the sample points using an octree data structure. The strengths of the approach are (a) simple implementation, (b) efficiency-experimental performance compares favorably with Delatmay-based algorithms, (c) robustness-curves with multiple components and sharp corners are reconstructed satisfactorily, and (d) potential extension to surface reconstruction.
curvature octree surface reconstruction computational geometry curve reconstruction local feature size