平面散乱数据点焦曲线重构的新方法  

A New Method for Planar Curve Reconstruction from a Set of Scattered Points

作　　者：吴佩峰[1] 吕立霞 于家富[1] Wu Pei - feng, LV Li - xia, YU Jia - fu（1. Shandong TV University,Jinan Shandong 250014 ;2. Shandong Laws School,Jinan Shandong 250014 ）

机构地区：[1]山东广播电视大学,山东济南250014 [2]山东省法律学校,山东济南250014

出　　处：《山东电大学报》2008年第1期24-26,共3页Journal of Shandong TV University

摘　　要：提出了平面散乱数据点集曲线重构的最短路逼近算法，它创造性地把散乱数据点集的曲线重构问题转化为图论中带权连通图的最短路求解问题。新方法根据散乱数据点的分布情况构造平面上的势函数，并对散乱数据点集进行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.

关 键 词：曲线重构 DELAUNAY三角化 最短路 势函数 

分 类 号：TP302.4[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]