Curve reconstruction from a set of unorganized points

An efficient method to approximate point cloud data in 2D plane with a smooth curve is presented. The idea of our algorithm is intuitive and simple - we divide the unorganized points into several subsets and the points in each subset are nearly on a line. Each subset is fitted by a conic. All data points are fitted by a C¹ quadratic piecewise curve. Although presented for the 2D case, our method can be extended in a straightforward manner to fit data points by a curve in higher dimensions.