一种必经结点最短路径搜索方法专利查询专利号|摘要-满商公司网

一种必经结点最短路径搜索方法

基本信息

申请号	CN201911129998.4	申请日	-
公开（公告）号	CN110887502B	公开（公告）日	2020-03-17
申请公布号	CN110887502B	申请公布日	2020-03-17
分类号	G01C21/34(2006.01)I	分类	-
发明人	卢玉南;魏金占;朱兆旻;吴宁;覃伟荣;陆韦春;陈明辉;唐媛	申请（专利权）人	广西华蓝岩土工程有限公司
代理机构	广西中知科创知识产权代理有限公司	代理人	广西华蓝岩土工程有限公司
地址	530022广西壮族自治区南宁市望州路北二里38号
法律状态	-

摘要

本发明公开了一种必经结点最短路径搜索方法，该方法包括如下处理步骤：S1、构建泰森多边形；S2、起点必经结点和终点必经结点不是同一必经结点进行S3处理；S3、以起点必经结点所在的泰森多边形为起始，查询相邻的泰森多边形合并成第一合并多边形；S4、以第一合并多边形为基准，查询相邻的未处理泰森多边形合并成第二合并多边形；S5、将孤立的泰森多边形合并到相邻共边的某个合并多边形中；S6、将Denaulay三角形中两个顶点不在同一个合并多边形中的边删除；S7、若合并多边形中剩余的边线不存在节点度大于等于三的情况，则进行S8处理；S8、将每个合并多边形中边线首尾相连，连线短者为结果。通过本发明能够有效降低处理难度、成本和时间，提高搜索效率。