收稿日期:20230615;修回日期:20230713基金项目:国家重点研发计划项目(2020YFFO304105)作者简介:李纯(1979—),男,正高级工程师,2003年毕业于武汉大学遥感信息工程学院信息工程专业,工学学士,主要从事测绘与数字化技术研发应用工作,E-mail:253893@qq.com。第67卷第10期2023年10月铁道标准设计RAILWAYSTANDARDDESIGNVol.67No.10Oct.2023文章编号:10042954(2023)10019407基于优先级队列的隧道无序点云快速法线全局定向方法李纯,黄新文,周清华,薛宇腾,杨璟林,宋浩(中铁工程设计咨询集团有限公司,北京100055)摘要:针对目前隧道无序点云法线全局定向方法存在的问题,提出一种基于优先级队列的快速法线全局定向方法。首先,针对传统方法采用近邻搜索方法算法复杂度为O(lgn)的问题,提出一种新的SearchDataStruct(SDS)空间搜索数据结构用于近邻搜索,将算法复杂度降低到O(n),提升了海量点云的搜索效率;其次,针对传统方法计算复杂且不鲁棒等问题,提出一种新的优先级队列结构,优先级队列容纳多级类别,克服了传统方法的缺点;最后,针对传统方法需要对全局点云进行多次判断和效率低的问题,采用优先级队列策略和区域增长方法,引导点云沿着最平坦的方向进行法线定向,保证点云在奇异情况下定向正常,确保点云整体法线方向的一致性,同时每个点仅需进行一次判断即可完成定向,将算法复杂度降低到O(n),提高了法线全局定向的效率。试验结果表明,本文提出的算法效果与商业软件GeoMagic的效果相当,能够处理隧道无序点云的各种奇异情况,算法在平缓区域、尖锐特征区域和高曲率区域能得到正确的法线方向,且效率相对GeoMagic提高了14倍,大幅提升了无序点云处理的工程化水平。关键词:隧道点云;法线定向;空间搜索结构;近邻搜索;优先级队列中图分类号:U25;TP391;U456.3文献标识码:ADOI:10.13238/j.issn.1004-2954.202306150004AFastGlobalNormalOrientationMethodforTunnelUnorderedPointCloudBasedonPriorityQueueLIChun,HUANGXinwen,ZHOUQinghua,XUEYuteng,YANGJinglin,SONGHao(ChinaRailwayEngineeringDesignandConsultingGroupCo.,Ltd.,Beijing100055,China)Abstract:Thepaperproposesafastglobalnormalorientationmethodbasedonapriorityqueue,aimingtoaddresstheproblemsexistingincurrentunorderedpointcloudnormalestimationmethodsfortunnels.Firstly,anewSearchDataStruct(SDS)spatialsearchdatastructureisintroducedtoreplacethetraditionalnearestneighborsearchmethod,red...
