摘要
提出了平面散乱数据点集曲线重构的最短路逼近算法，它创造性地把散乱数据点集的曲线重构问题转化为图论中带权连通图的最短路求解问题。新方法根据散乱数据点的分布情况构造平面上的势函数，并对散乱数据点集进行Delaunay三角化。根据势函数对Delaunay三角网格的每条边赋一个权值，生成带权连通图。在带权连通图上生成重构曲线两端点间的逼近路径，简化逼近路径，找出该路径上的关键点。以关键点为控制点，势函数值为权值，生成有理B样条曲线。最短路逼近算法在实验中取得很好的效果，成功解决了移动最小二乘法难以解决的具有尖点特征的数据点集的曲线重构问题。
Curve reconstruction from a set of scattered points is proposed in this paper. Firstly, a potential function is constructed in the plane according to the distribution of the points, then a Delaunay triangulation of the scattered points is produced and each edge is given a value as the weight using the potential function, thus a weighted connected graph is formed. Secondly, the shortest path between two given points in the graph is found. Finally, some critical points along the shortest path are determined and a rational B - spline curve is used to approximate these critical points. Compared with the moving least - square method, the shortest path approximation algorithm gives good experimental results, especially to the scattered points with high curvature segments.
作者
吴佩峰
吕立霞
于家富
Wu Pei - feng, LV Li - xia, YU Jia - fu（1. Shandong TV University,Jinan Shandong 250014 ;2. Shandong Laws School,Jinan Shandong 250014 ）
出处
《山东电大学报》
2008年第1期24-26,共3页
Journal of Shandong TV University
关键词
曲线重构
DELAUNAY三角化
最短路
势函数
curve reconstruction
Delaunay Triangulation
the shortest path
the potential function
