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

摘要

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