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

有效

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

本發明公開了一種基于改進四叉樹的范圍判斷方法，包括：獲取位置點經緯度坐標集合、興趣點經緯度坐標集合和預設范圍值，將興趣點經緯度坐標集合中各興趣點經緯度坐標轉換為興趣點矩形坐標，將興趣點矩形坐標輸入四叉樹模型，生成改進四叉樹模型，將位置點經緯度坐標集合中各位置點經緯度坐標轉換為位置點矩形坐標，通過改進四叉樹模型遍歷每個位置點矩形坐標，并將滿足四叉樹索引條件的興趣點經緯度坐標輸出，根據輸出的興趣點經緯度坐標和位置點經緯度坐標，計算興趣點與位置點之間的距離，當距離小于等于預設范圍值時，確定位置點在興趣點的預設范圍內。通過上述方法，可以快速判斷位置點是否在興趣點的范圍內，而且可以提高判斷的準確率。

技術領域

本發明涉及數據處理技術領域，特別涉及一種基于改進四叉樹的范圍判斷方法、裝置、設備。

背景技術

目前，人們在出行的過程中，常常需要查看周圍是否有超市、加油站、服務區等興趣點，因此，快速判斷地理位置點是否在興趣點范圍內，可以給我們的日常生活帶來很大的便捷。

現有技術中，判斷位置點是否在興趣點范圍內時，一種方法是直接采用笛卡爾積分別計算所有位置點與所有興趣點的距離，然后進行判斷，當位置點的數據量特別大的時候，就會產生非常大的計算量，而且耗費的時間也比較長；另一種方法是，采用四叉樹模型進行范圍判斷，但是傳統方法中，四叉樹模型用的是基于距離的直角坐標系，對于基于角度的經緯度坐標的位置點，誤差比較大。

發明內容

本公開實施例提供了一種基于改進四叉樹的范圍判斷方法、裝置、設備。為了對披露的實施例的一些方面有一個基本的理解，下面給出了簡單的概括。該概括部分不是泛泛評述，也不是要確定關鍵/重要組成元素或描繪這些實施例的保護范圍。其唯一目的是用簡單的形式呈現一些概念，以此作為后面的詳細說明的序言。

在一些可選地實施例中，一種基于改進四叉樹的范圍判斷方法，包括：

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

將興趣點經緯度坐標集合中各興趣點經緯度坐標轉換為興趣點矩形坐標，將興趣點矩形坐標輸入四叉樹模型，生成改進四叉樹模型；

將位置點經緯度坐標集合中各位置點經緯度坐標轉換為位置點矩形坐標，通過改進四叉樹模型遍歷每個位置點矩形坐標，并將滿足四叉樹索引條件的興趣點經緯度坐標輸出；

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

可選地，還包括：

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

可選地，將興趣點經緯度坐標集合中各興趣點經緯度坐標轉換為興趣點矩形坐標，包括：

將預設范圍值轉化為對應的經緯度；

將興趣點的經度坐標減去預設范圍值對應的經度，作為興趣點矩形的第一端點值，將興趣點的經度坐標加上預設范圍值對應的經度，作為興趣點矩形的第二端點值；

將興趣點的緯度坐標減去預設范圍值對應的緯度，作為興趣點矩形的第三端點值，將興趣點的緯度坐標加上預設范圍值對應的緯度，作為興趣點矩形的第四端點值。

可選地，將位置點經緯度坐標集合中各位置點經緯度坐標轉換為位置點矩形坐標，包括：

將位置點的經度坐標作為位置點矩形的第一端點值，將位置點的經度坐標作為位置點矩形的第二端點值；

將位置點的緯度坐標作為位置點矩形的第三端點值，將位置點的緯度坐標作為位置點矩形的第四端點值。