[發明專利]地理圍欄

在審

• 申請號: 201710797549.1
• 申請日: 2017-09-06
• 公開（公告）號: CN107562895A
• 公開（公告）日: 2018-01-09
• 發明（設計）人: 劉純陽;鮑士要;張國濤
• 申請（專利權）人: 上海享騎電動車服務有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種地理圍欄，其特征在于：

包括樹索引法：

首先通過粗篩的方法快速找到符合條件的少量多邊形，然后對粗篩后的多邊形使用射線法判斷；

對于一維數據使用索引的方法，通過B樹索引找到某一個范圍區間段，然后對此范圍區間段進行遍歷查找，對于二維空間數據常常使用空間索引的方法，比如通過R樹找到范圍區間內的多邊形，然后對此范圍內的多邊形進行精確判斷；

下面介紹最常使用的空間索引R樹的解決思路。

①外包矩形表示多邊形

由于多邊形形狀各異，我們需要以一種統一的方式來對多邊形進行近似，最簡單的方式就是用最小外包矩形來表示多邊形；

②對最小外包矩形建立R樹索引；

③查詢；

首先通過R樹迅速判斷用戶所在位置是否被外包矩形覆蓋；

如果不被任何外包矩形覆蓋則返回不在地理圍欄多邊形內；

如果被外包矩形覆蓋則還需要進一步判斷是否在此外包矩形的多邊形內部，采用射線法判斷；

①多邊形邊數比較多時的解決辦法；

對多邊形的每條邊構建最小外包矩形；

在這些最小外包矩形基礎上構建R樹索引；

通過R樹判斷射線是否與外包矩形相交；

R樹粗篩后的邊進行精確求交判斷,時間復雜度從O(N)降到O(Log(N))，大大提高了計算效率。

2.如權利要求1所述的地理圍欄，其特征在于：射線法，從點水平出發做一條射線，計算該射線與多邊形的邊的相交點個數，當點不在多邊形邊或者是頂點上時，如果是奇數，那么點就一定在多邊形內部，否則，在外部，其中它的算法復雜度是O(N),N為多邊形的邊數。