[發明專利]一種基于二維地圖網格劃分的路徑規劃方法和系統

有效

• 申請號: 202010070752.0
• 申請日: 2020-01-21
• 公開（公告）號: CN111310984B
• 公開（公告）日: 2023-09-26
• 發明（設計）人: 王智奇;李為民
• 申請（專利權）人: 成都智庫二八六一信息技術有限公司
• 主分類號: G06Q10/047
• 分類號: G06Q10/047;G06T11/20;G06F16/29
• 代理公司: 成都行之專利代理有限公司 51220
• 代理人: 熊曦

本發明公開了一種基于二維地圖網格劃分的路徑規劃方法和系統，包括以下步驟：構建一個網格集合X，使得網格集合X包含地理位置A所在的網格a和地理位置B所在的網格b，并獲取網格集合X內每一個網格所在地理位置的地形特征值；在網格集合X內構建一個包含網格a和網格b的網格集合Y，使得網格a和網格b在網格集合Y內連通，且網格集合Y內的網格特征值之和最小。本發明提供了一種基于二維地圖網格劃分的路徑規劃方法和系統，將地理區域進行網格劃分，并將每個網格量化為一組特征值，通過尋求兩地理位置之間的最小特征值之和，可以準確、快速的得到兩個地理位置之間的路徑規劃。

技術領域

本發明涉及地理數據量化分析應用技術領域，尤其涉及一種基于二維地圖網格劃分的路徑規劃方法和系統。

背景技術

對任何一個地理區域都可以被一個或多個類似規格的網格全覆蓋。反而言之，將二維地圖用網格覆蓋后，任意大小和連通性的區域都能找到對應的網格將其覆蓋。而覆蓋這個區域的網格集合，則可近似代表這個區域。對地圖上任何的一個點，也能被一個唯一的網格覆蓋。

每一個網格均有類似的規格，網格間是無縫且沒有重疊的，所以在地圖上的相對位置可以表示其唯一性，每一個網格均采用多組維度不同的數據量化，對于一個網格特征的定量，就是該網格的多維向量中對應位置的標量值。

路徑規劃是指，在一個地理區域內，對任意兩個網格，找到一條連通兩個網格的路線，并且使這條路徑滿足路徑規劃的目標，即路徑中的網格特征值滿足某特定條件(一般為特征和最小)。

在對這個特定的領域進行路徑規劃時，現有的方法多以點線結合的模型，將特征化為線的權重，考慮是否成環，是否有向等特點；然而并沒有以網格形式存在的路徑規劃模型，以及網格路徑規劃模型的量化解決方案。

發明內容

本發明提供了一種基于二維地圖網格劃分的路徑規劃方法和系統，將地理區域進行網格劃分，并將每個網格量化為一組特征值，通過尋求兩地理位置之間的最小特征值之和，可以準確、快速的得到兩個地理位置之間的路徑規劃。

本發明通過下述技術方案實現：

一種基于二維地圖網格劃分的路徑規劃方法，包括以下步驟：

S1：構建一個網格集合X，使得網格集合X包含地理位置A所在的網格a和地理位置B所在的網格b，并獲取網格集合X內每一個網格所在地理位置的地形特征值；

S2：在網格集合X內構建一個包含網格a和網格b的網格集合Y，使得網格a和網格b在網格集合Y內連通，且網格集合Y內的網格特征值之和最小。

將地理區域進行網格劃分，并使得每個網格量化為一組特征值，該特征值可以根據目標規劃的實際需求進行選取，可以是兩個地理位置之間的距離，也可以是兩個地理位置之間的連通性或者其他。從其中一個地理位置出發，不斷的向四周尋求相鄰網格，可以使得兩個地理位置之間有若干條路徑連通，選擇連通路徑中特征值之和滿足要求的，可以準確、快速的得到兩個地理位置之間的目標路徑。

進一步地，所述S1具體包括：

S11：任意選取一個能覆蓋地理位置A和地理位置B的地理區域Q；

S12：將地理區域Q劃分為若干個大小形狀均相同的網格，以構建網格集合X；

S13：獲取網格集合X內每一個網格所在地理位置的地形特征值。

進一步地，所述S2具體包括：

S21：在網格集合X內，選擇網格a作為起始點D，網格b作為終點F；

S22：構建集合S，使得S＝{a}；

S23：找到集合S中所有網格的相鄰網格，用以構建集合O；