[發明專利]基于改進四叉樹的范圍判斷方法、裝置、設備

有效

• 申請號: 201911184433.6
• 申請日: 2019-11-27
• 公開（公告）號: CN111061824B
• 公開（公告）日: 2023-07-25
• 發明（設計）人: 馬蘭偉;楊曉明;王巍;張志平;胡道生;夏曙東
• 申請（專利權）人: 北京中交興路信息科技有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/9537
• 代理公司: 北京辰權知識產權代理有限公司 11619
• 代理人: 劉廣達

1.一種基于改進四叉樹的范圍判斷方法，其特征在于，包括：

獲取位置點經緯度坐標集合、興趣點經緯度坐標集合和預設范圍值；

將興趣點經緯度坐標集合中各興趣點經緯度坐標轉換為興趣點矩形坐標，包括：將預設范圍值轉化為對應的經緯度；將興趣點的經度坐標減去預設范圍值對應的經度，作為所述興趣點矩形的第一端點值，將興趣點的經度坐標加上預設范圍值對應的經度，作為所述興趣點矩形的第二端點值；將興趣點的緯度坐標減去預設范圍值對應的緯度，作為所述興趣點矩形的第三端點值，將興趣點的緯度坐標加上預設范圍值對應的緯度，作為所述興趣點矩形的第四端點值；將所述興趣點矩形坐標輸入四叉樹模型，生成改進四叉樹模型；

將位置點經緯度坐標集合中各位置點經緯度坐標轉換為位置點矩形坐標，包括：將位置點的經度坐標作為所述位置點矩形的第一端點值，將位置點的經度坐標作為所述位置點矩形的第二端點值；將位置點的緯度坐標作為所述位置點矩形的第三端點值，將位置點的緯度坐標作為所述位置點矩形的第四端點值；通過所述改進四叉樹模型遍歷每個位置點矩形坐標，并將滿足四叉樹索引條件的興趣點經緯度坐標輸出；

根據輸出的興趣點經緯度坐標和位置點經緯度坐標，計算興趣點與位置點之間的距離，當所述距離小于等于預設范圍值時，確定所述位置點在所述興趣點的預設范圍內。

2.根據權利要求1所述的方法，其特征在于，還包括：

根據輸出的興趣點經緯度坐標和位置點經緯度坐標，計算興趣點與位置點之間的距離，當所述距離大于預設范圍值時，確定所述位置點不在所述興趣點的預設范圍內。

3.根據權利要求1所述的方法，其特征在于，所述獲取位置點經緯度坐標集合、興趣點經緯度坐標集合和預設范圍值之后，還包括：

獲取興趣點的地圖編號集合；

根據位置點的經緯度坐標集合計算位置點的地圖編號集合。

4.根據權利要求3所述的方法，其特征在于，將興趣點的地圖編號集合和位置點的地圖編號集合作為mapreduce模型中map函數輸出的中間鍵值對里的鍵，將所述鍵傳輸到reduce函數中，通過所述鍵將興趣點數據和位置點數據劃分到對應的興趣點操作任務和對應的位置點操作任務，其中，基于四叉樹的范圍判斷方法在reduce函數中進行。

5.一種基于改進四叉樹的范圍判斷裝置，其特征在于，包括：

獲取模塊：用于獲取位置點經緯度坐標集合、興趣點經緯度坐標集合和預設范圍值；

第一轉換模塊，用于將興趣點經緯度坐標集合中各興趣點經緯度坐標轉換為興趣點矩形坐標，包括：將預設范圍值轉化為對應的經緯度；將興趣點的經度坐標減去預設范圍值對應的經度，作為所述興趣點矩形的第一端點值，將興趣點的經度坐標加上預設范圍值對應的經度，作為所述興趣點矩形的第二端點值；將興趣點的緯度坐標減去預設范圍值對應的緯度，作為所述興趣點矩形的第三端點值，將興趣點的緯度坐標加上預設范圍值對應的緯度，作為所述興趣點矩形的第四端點值；將所述興趣點矩形坐標輸入四叉樹模型，生成改進四叉樹模型；

第二轉換模塊，用于將位置點經緯度坐標集合中各位置點經緯度坐標轉換為位置點矩形坐標，包括：將位置點的經度坐標作為所述位置點矩形的第一端點值，將位置點的經度坐標作為所述位置點矩形的第二端點值；將位置點的緯度坐標作為所述位置點矩形的第三端點值，將位置點的緯度坐標作為所述位置點矩形的第四端點值；通過所述改進四叉樹模型遍歷每個位置點矩形坐標，并將滿足條件的興趣點經緯度坐標輸出；

確定模塊，用于根據輸出的興趣點經緯度坐標和位置點經緯度坐標，計算興趣點與位置點之間的距離，當所述距離小于等于預設范圍值時，確定所述位置點在所述興趣點的預設范圍內。

6.根據權利要求5所述的裝置，其特征在于，還包括：

第二確定模塊，用于當所述距離大于預設范圍值時，確定所述位置點不在所述興趣點的預設范圍內。

7.一種計算機可讀介質，其特征在于，其上存儲有計算機可讀指令，所述計算機可讀指令可被處理器執行以實現如權利要求1至4任一項所述的一種基于改進四叉樹的范圍判斷方法。