散乱数据点集曲线重构的最短路逼近算法

给出了散乱数据点集曲线重构的最短路逼近算法．算法根据数据点的分布构造带权连通图，通过求解带权连通图的最短路径，将散乱数据点集的曲线重构问题转化为有序数据点集的曲线重构问题．算法可以对单连通、多连通和封闭的数据点集进行重构．重构曲线较好地保持了数据点集的形状和走向，尤其是带尖点的数据点集的形状特征．最后给出不同拓扑结构的数据点集的重构曲线实例．

Curve Reconstruction from a Set of Scattered Points with Shortest-Path Approximation Algorithm

A new method named shortest path approximation algorithm is presented to reconstruct a curve from a set of scattered points. This method builds a weighted graph from the given scattered points using the distribution knowledge of these points. By computing a shortest path in the weighted graph, the problem of curve reconstruction from scattered data points is transformed into the problem of curve reconstruction from a set of ordered data points. The method can reconstruct curves from data set with arbitrary topology, such as simply connected, multiple connected and closed scattered points. Compared with other methods, the new method keeps the shape characteristic of point set well, especially the segments with high curvature. Several examples are given in the end to illustrate the performance of the new method.