CN105067004A - 一种基于地形的路径搜索方法 - Google Patents

Abstract

本发明涉及一种路径搜索方法，属于GIS导航方法及设备领域，具体涉及一种基于地形的路径搜索方法。该方法将搜索区域表示为由若干个通行单元构成的包含有通行代价信息的通行代价图，然后根据通行代价图生成由通行单元边串联构成的通行代价最小的通行路径。因此，本发明能够以较低的成本实现快速搜索已知和未知路线的能力，不需要特有的设备支持，技术难度较低，因此在应急指挥、野外搜救等活动中可以有效降低成本，性价比更高。

Description

一种基于地形的路径搜索方法

技术领域

本发明涉及一种路径搜索方法，属于GIS导航方法及设备领域，具体涉及一种基于地形的路径搜索方法。

背景技术

计算机技术的高速发展促进了专业测绘领域的GIS系统功能迅速在大众领域普及，随着手机等移动设备的高速发展，通常在专业GIS领域才使用的路径分析功能已经在车载移动设备、手机中大量普及。

大众领域的路径分析功能都是基于道路网数据，一些专有领域也会利用电路网、水路网、管道网、通讯网等网络数据进行各种路径分析应用。虽然这些网路数据稍有区别，但是本质上仍是对点、边构成的矢量网络数据进行分析。这种基于矢量网络的路径分析功能具有数据量小、运算简单、计算速度快的特点。

基于矢量网络的路径分析功能需要通过预先建立的矢量网络数据进行分析，而在一些没有预先建立网络数据的区域将会导致传统的路径分析功能无法使用。如图1所示，传统的基于网络数据的路径搜索在网络不通的情况下无能为力。在应急指挥、野外搜救领域可能会面临一些传统的网络路径分析功能无法使用的情况。例如在地质灾害发生后可能造成已有连通的路网无法连通，这样使用传统的网络路径分析手段就会因为计算的起点终点因为无法连通导致功能无法使用。

在机器人控制、人工智能领域会采用栅格地形数据结合实时的传感器扫描结果等手段在没有网络数据的情况下计算出机器人、汽车等实例可以前进的路线。这样的路径分析方式可以很好的解决传统路径分析中完全依赖与网络数据的弱点，但是这样的方式需要高难度的技术支撑，成本上也更加高昂，同时这样的分析方式更多是在局部区域内进行分析，难于做到全局范围的路径分析。

在应急指挥领域一些突发的状况会对路径搜索造成很大的影响，例如大雨可能造成干枯河床成为汪洋，道路可能因为滑坡临时阻断，一片区域可能因为积雪融化而成为沼泽。在应急指挥的活动中这些突发的状况都可能在几个小时甚至几分钟内发生，那么这就意味着在这样的场景下做路径的搜索需要随时加入各种阻碍、通畅要素的能力。传统的基于网络数据的路径搜索在实时改动网络数据方面只能设置障碍点、增加临时边等操作，如图2所示将某个区域范围作为避让区域显然无法做到。本专利所采用的技术可以非常容易做到将任意的面或者线的区域在路径搜索过程中作为障碍或者快速通道。

发明内容

本发明主要是解决现有技术所存在的没有预先建立网络数据的区域将会导致传统的路径分析功能无法使用的技术问题，提供了一种基于地形的路径搜索方法。该路径搜索方法将区域内的地形数据和已有道路网路数据以及障碍数据相结合进行路径搜索，能够以较低的成本实现快速搜索已知和未知路线的能力。

本发明还有一目的是解决现有技术中基于地形和传感器扫描搜索路径需要依赖于复杂设备并且成本高昂等技术问题，提供了一种基于地形的路径搜索方法。该路径搜索方法将网络数据和地形数据融合为一体后进行统一的搜索，不需要特有的设备支持，技术难度较低，因此在应急指挥、野外搜救等活动中可以有效降低成本，性价比更高。

本发明的上述技术问题主要是通过下述技术方案得以解决的：

一种基于地形的路径搜索方法，包括以下步骤：

通行代价图生成步骤，用于将搜索区域表示为由若干个通行单元构成的包含有通行代价信息的通行代价图；

目的路径搜索步骤，用于根据通行代价图生成由通行单元边串联构成的通行代价最小的通行路径；

其中，所述通行代价图生成步骤具体包括以下子步骤：

单元格划分子步骤，将搜索区域若干的通行单元，通行单元的边可串连形成通行路线；通行单元的大小可以根据地形数据的精度以及最终需要分析的精度界定；

通行代价定义子步骤，通过搜索区域的地形数据和/或矢量数据来为通行单元的边定义通行代价，通行代价代表通行这条边的难度；

所述目的路径搜索步骤具体包括以下子步骤：

搜索图生成子步骤，用于获取包含目标区域的通行代价图，根据获取的通行代价图得到由若干个搜索单元构成的搜索图，其中，搜索单元划分方式与通行单元的划分相同，每个搜索单元记录该搜索单元到目标搜索单元的总代价和；

行进路线计算子步骤，从搜索起点所在的搜索单元遍历周边值最小的搜索单元，依次递归遍历直到找到值为0的搜索单元格，将整个搜索的路线作为最终的行进路线输出。

优化的，上述的一种基于地形的路径搜索方法，所述通行单元为正方形或正三角。

优化的，上述的一种基于地形的路径搜索方法，所述通行代价定义子步骤中利用的地形数据以格网形式表示，并且通过将地形数据的格网与通行单元套合以得到通行单的边所跨越的地形数据。

优化的，上述的一种基于地形的路径搜索方法，所述搜索图生成子步骤中，搜索目标所在通行单元为目标单元格，并且生成搜索图时，以目标单元格为起点计算其到周边的通行单元的代价，通过广度和/或深度搜索的方式填充所有通行单元到目标单元格的代价，最终得到搜索图。

优化的，上述的一种基于地形的路径搜索方法，还包括：

通行代价图修正步骤，将标绘了最新的道路和/或地形信息的数据参照通行代价图生产的方式形成一个临时标绘层，这个临时标绘图层与原始的通行代价图叠加形成了一个能反映最新实时状况的通行代价图；

并且在目的路径搜索步骤中，优先从临时标绘图层实时计算通行代价，如果临时标绘图层无法获取则从原始的通行代价图获取通行代价。

优化的，上述的一种基于地形的路径搜索方法，在通行代价图生成步骤中，同时生成多个级别的通行代价图，级别较小的通行代价图所包含的单个通行单元的面积越大；

并且在目的路径搜索步骤中，优先利用数量小的级别进行搜索，然后一级一级的细化，最终得到通行路径。

因此，本发明具有如下优点：1、将完全基于栅格的路径搜索和完全基于矢量的栅格搜索完全融合为一体，充分利用了两种搜索的特点；2、本发明的对于数据的变化有很好的适应性，非常适合应急指挥领域经常发生突发状况的需要；3、本发明不依赖特定的复杂算法，也不依赖特别的硬件，因此整体实施成本并不高。

附图说明

附图1是传统的基于网络数据的路径搜索示意图；

附图2是设置避让区域后的路径分析示意图；

附图3是本发明实施例1的流程示意图；

附图4是本发明实施例1的通行单元划分示意图；

附图5是本发明实施例1的另一种通行单元划分示意图；

附图6是采用格网的形式表示某个网格范围内的地形高度示意图；

附图7通过跨越地形格网计算条边通行平坦程度的示意图；

附图8通矢量数据计算通行单元条边的通行代的示意图；

附图9是采用矢量及地形数据叠加计算通行代价的示意图；

附图10是利用通行代价图进行路径搜索的流程示意图；

附图11是本发明实施例1的搜索图示意图；

附图12是本发明实施例1的利用临时标绘图生成通行代价图的示意图；

附图13是混合使用道路网和地形进行路径分析的示意图。

具体实施方式

下面通过实施例，并结合附图，对本发明的技术方案作进一步具体的说明。

实施例1

如图3所示，本发实施例的路径搜索主要有两个部分构成，第一部分将原始数据生产为可用于路径搜索的通行代价图，第二部分使用通行代价图进行路径搜索。

1、通行代价图计算

原始数据生产目的是将路径搜索区域的地形数据以及矢量数据生产为通行代价图。生产通行代价图的数据文件的流程如下：

步骤101，将搜索区域划分为若干的通行单元，如图4所示，一个通行单元可以是一个简单的正方形，正方形的边串连形成了通行路线。通行单元正方形的大小可以根据地形数据的精度以及最终需要分析的精度界定。例如地形数据的分辨率为5米，那么通行单元的大小可以采用5X5米，也可以采用更低的精度10X10米等。

如图4中通行单元的四条边(A，B，C，D)串连形成了可通行的路线，如果某个边无法通行则可以绕行其他边。

以四边形划分通行单元的好处是容易处理，不足之处则是容易造成一些通行路线最终为锯齿状，因此通行单元的划分也可以采用正三角形的形式如图5所示，整个搜索区域的可以最终以蜂窝状分割。

分割通行单元的方式是采用正方形还是正三角形可以根据最终路径搜索的要求来定，如果要求最终的规划路线比较平滑可以采用计算和数据存储都比较复杂的正三角形分割方式，如果要求不太高可以采用正方形的分割方式。

步骤102，通行单元分割之后需要为通行单元的边定义通行代价，通行代价代表通行这条边的难度，使用一个数字来表示这个难度，因为通行单元的数量非常庞大，因此通行代价使用一个字节【1,254】范围来表示。数字越大则通行难度越大，255用于标示完全不可通行。

通行代价的计算可以通过搜索区域的地形数据以及矢量数据来计算。对于地形数据(以DEM数字高程模型数据)为例，如图6所示，DEM数据采用格网的形式表示某个网格范围内的地形高度。

通过将地形和通行单元套合可以得到任何通行单元的边跨越了那些地形网格，如图7所示通过跨越的地形格网可以计算条边通行的平坦程度作为通行的难度。平坦的路线则通行代价低，颠簸或者过于坡度大的通行代价值高，过于陡峭则可以设置代价值为255，无法通行。

具体的计算通行代价的方法不在本发明的范畴之内，采用什么样的算法来计算通行代价可以在实际应用中根据需要使用。

通行代价也可以通过矢量数据计算得到，如图8所示，通过对矢量数据的线、面设置其通行代价，矢量也被通行单元分割用于计算通行单元的通行代价。

在生成通行代价图时，也可以同时使用地形、矢量等数据来生成通行代价图，如图9所示。

2、目的路径搜索

第一步数据生产的目标是将地形、矢量等原始数据按照优先级顺序计算通行代价叠加成为可用于路径分析用的分析数据文件通行代价图。

通行代价图计算完成之后，则可以使用通行代价图进行路径搜索。利用通行代价图进行路径搜索主要分为两个过程，如图10所示第一个过程是当明确搜索目标之后则根据搜索目标以通行代价图为基础生成搜索目标对应的搜索图。第二个过程则是不断根据当前位置从搜索图中获取当前位置到搜索目标位置的行进路线。

搜索图是和通行代价图相同的方式用正方形或者三角形划分为大量的搜索单元，每个搜索单元记录该搜索单元到目标搜索单元的总代价和。如图11所示搜索图中，每个搜索单元中存储的数值为该单元格到目标位置的总代价和，如此形成的搜索图，在搜索路径的时候值需要简单从搜索七点简单遍历周边值最小的单元格，依次递归遍历直到找到值为0的单元格，则整个搜索的路线就是最终的行进路线。

其中，搜索图的计算需要和通行代价图相互套合，以搜索目标为起点计算周边的单元格到起点的代价。通过广度或者深度搜索的方式实现填充所有搜索单元的代价。

3、临时标绘层

在应急指挥野外搜救活动中，很容易产生突发状况从而影响到搜索过程，例如山洪暴发造成浅滩变汪洋。简单的说各种突发状况可能造成了原本通畅的路线可能不通了，原本不通的路线也可能变得通畅，这样的突发状况都可能造成路径搜索所使用的通行代价图与实际的情况不符合。如果将这些新的状态以矢量数据形式记录并从数据生产的环节将通行代价图重新生产一遍的确可以解决，但这样会造成时间成本上难于承受。

因此在确定了搜索目标的情况下建立搜索图的时候并不一定要完全从原始的通行代价图中获取通行代价数据。如图12所示，创建搜索图的时候可以将危险区域、通畅道路等标绘的矢量数据参照通行代价图生产的方式形成一个临时标绘层，这个临时标绘层与原始的通行代价图叠加形成了一个能反映最新实时状况的通行代价图。

计算搜索图的时候优先从临时标绘图层实时计算通行代价，如果临时标绘图层无法获取则从原始的通行代价图获取通行代价。

在应急指挥、野外搜救等实际应用中，一旦确立了搜索的目标则可以根据通行代价图快速建立起搜索图，只要搜索目标不变的情况下则可以实时根据当前车辆、人员的位置从搜索图中快速获取行进路线。

采用上述方法后，而本发明的技术能够实现混合使用道路网和地形进行路径分析并最终指引为合理的行进路线，如图13所示。

实施例2

实施例1的流程也可以存在一种变通的方法来实现，即通行代价图的生成方法和实施例1所定义的一致，但是生成通行代价图的时候需要同时生成多分的通行代价图。例如按照5x5米，10X10米，20X20米生成多个级别的通行代价图，具体生成多少个级别的通行代价图可以由具体的数量来确定。

生成多个级别的通行代价图之后则路径搜索可以采用传统的矢量网络路径搜索算法，优先对数量小的级别进行搜索，然后一级一级的细化，这样可以避免直接搜索最精细级别的通行代价图速度慢的问题。

本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。

Claims (6)

1.一种基于地形的路径搜索方法，其特征在于，包括以下步骤：

通行代价图生成步骤，用于将搜索区域表示为由若干个通行单元构成的包含有通行代价信息的通行代价图；

目的路径搜索步骤，用于根据通行代价图生成由通行单元边串联构成的通行代价最小的通行路径；

其中，所述通行代价图生成步骤具体包括以下子步骤：

单元格划分子步骤，将搜索区域若干的通行单元，通行单元的边可串连形成通行路线；通行单元的大小可以根据地形数据的精度以及最终需要分析的精度界定；

通行代价定义子步骤，通过搜索区域的地形数据和/或矢量数据来为通行单元的边定义通行代价，通行代价代表通行这条边的难度；

所述目的路径搜索步骤具体包括以下子步骤：

搜索图生成子步骤，用于获取包含目标区域的通行代价图，根据获取的通行代价图得到由若干个搜索单元构成的搜索图，其中，搜索单元划分方式与通行单元的划分相同，每个搜索单元记录该搜索单元到目标搜索单元的总代价和；

行进路线计算子步骤，从搜索起点所在的搜索单元遍历周边值最小的搜索单元，依次递归遍历直到找到值为0的搜索单元格，将整个搜索的路线作为最终的行进路线输出。

2.根据权利要求1所述的一种基于地形的路径搜索方法，其特征在于，所述通行单元为正方形或正三角。

3.根据权利要求1所述的一种基于地形的路径搜索方法，其特征在于，所述通行代价定义子步骤中利用的地形数据以格网形式表示，并且通过将地形数据的格网与通行单元套合以得到通行单的边所跨越的地形数据。

4.根据权利要求1所述的一种基于地形的路径搜索方法，其特征在于，所述搜索图生成子步骤中，搜索目标所在通行单元为目标单元格，并且生成搜索图时，以目标单元格为起点计算其到周边的通行单元的代价，通过广度和/或深度搜索的方式填充所有通行单元到目标单元格的代价，最终得到搜索图。

5.根据权利要求1所述的一种基于地形的路径搜索方法，其特征在于，还包括：

通行代价图修正步骤，将标绘了最新的道路和/或地形信息的数据参照通行代价图生产的方式形成一个临时标绘层，这个临时标绘图层与原始的通行代价图叠加形成了一个能反映最新实时状况的通行代价图；

并且在目的路径搜索步骤中，优先从临时标绘图层实时计算通行代价，如果临时标绘图层无法获取则从原始的通行代价图获取通行代价。

6.根据权利要求1所述的一种基于地形的路径搜索方法，其特征在于，

在通行代价图生成步骤中，同时生成多个级别的通行代价图，级别较小的通行代价图所包含的单个通行单元的面积越大；

并且在目的路径搜索步骤中，优先利用数量小的级别进行搜索，然后一级一级的细化，最终得到通行路径。