规则格网内插中的J邻近点快速搜索算法

引入KD-Tree的二维索引结构,提出一种基于优先队列的改进J邻近点搜索策略,针对规则格网内插中的固定点数和固定距离这两种搜索原则,分别设计其J邻近点搜索算法,并以反距离加权法为例实现了整个内插过程。实验表明,该算法具有较高的运行效率,并在大数据量的情况下性能更优。

基于优先级队列的隧道无序点云快速法线全局定向方法

针对目前隧道无序点云法线全局定向方法存在的问题,提出一种基于优先级队列的快速法线全局定向方法。首先,针对传统方法采用近邻搜索方法算法复杂度为O(lgn)的问题,提出一种新的Search Data Struct(SDS)空间搜索数据结构用于近邻搜索,将算法复杂度降低到O(n),提升了海量点云的搜索效率;其次,针对传统方法计算复杂且不鲁棒等问题,提出一种新的优先级队列结构,优先级队列容纳多级类别,克服了传统方法的缺点;最后,针对传统方法需要对全局点云进行多次判断和效率低的问题,采用优先级队列策略和区域增长方法,引导点云沿着最平坦的方向进行法线定向,保证点云在奇异情况下定向正常,确保点云整体法线方向的一致性,同时每个点仅需进行一次判断即可完成定向,将算法复杂度降低到O(n),提高了法线全局定向的效率。试验结果表明,本文提出的算法效果与商业软件GeoMagic的效果相当,能够处理隧道无序点云的各种奇异情况,算法在平缓区域、尖锐特征区域和高曲率区域能得到正确的法线方向,且效率相对GeoMagic提高了14倍,大幅提升了无序点云处理的工程化水平。

什么是多段图最短路径问题?

设图G=(V,E)是一个带权有向连通图,如果把顶点集合V划分成k个互不相交的子集Vi(2≤k≤n,1≤i≤k),使得E中的任何一条边(u,v),必有u∈Vi,v∈Vi+m(1≤i【k,1【i+m≤k),则称图G为多段图,称s∈V1为源点,t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。分支限界法常是用最小耗费(最大效益)或以广度优先的方法搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。