摘要
提出一种基于最小生成树的切片数据点排序算法,该算法建立散乱点云空间索引结构,基于该结构快速获取切片邻域数据,依据邻域数据与切片的位置关系将其划分为正负2个区域,通过正负邻域配对点连线与切片求交获取切片数据点,构造切片数据点的无向完全连通图,求解该图最小生成树,并将最小生成树的各分枝首尾相连,实现切片数据点的排序,实例证明该算法可对逆向工程中各种复杂型面切片数据点排序,排序结果准确,算法运行效率高。
A sorting algorithm of slicing data based on minimum spanning tree is proposed, which has five steps： firstly, the slicing neighbour points are obtained based on the special index structure; secondly, the slicing neighbour points are divided into two parts; thirdly, the slicing points are obtained by the intersecting between matching points of slicing neighbour data and the slice; fourthly, the connected undirected graph of slicing data is constructed; fifthly, for sorting the slice data, the minimum spanning tree of the graph is solved, which connect the different branches. It is proved that it has strong adaptability of slice data in reverse engineering and can get accurate result of sorting.
出处
《武汉理工大学学报》
CAS
CSCD
北大核心
2010年第2期68-71,共4页
Journal of Wuhan University of Technology
基金
国家高技术研究发展计划项目(863计划
2006AA04Z105)
关键词
逆向工程
切片数据点
空间索引结构
无向完全连通图
最小生成树
排序
reverse engineering
slice data
spacial index structure
connected undirected graph
minimum spanning tree
sorting
