[發明專利]地理圍欄

在審

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

技術領域

本發明屬于共享單車領域，尤其是一種地理圍欄。

背景技術

共享單車的大面積普及，給人們出行帶來了極大地便利，也出現了單車亂停亂放影響交通秩序的現象，增加了政府部門的管理壓力。究其原因，有以下兩點：一，共享單車數量猛增，原有停車位容量擴充跟不上共享單車數量的增長；二，原有的單車所有者和使用者是統一的，用戶對自有單車的使用相對規范。而隨著共享單車的大面積普及，替代作用日益明顯。單車擁有者和使用者分離，部分用戶在使用單車時，并沒有遵守交通規則，車輛亂停亂放，也增加管理壓力。

發明內容

本發明為解決上述技術問題而采用的技術方案是提供一種地理圍欄，其中，具體技術方案是：

包括樹索引法：

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

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

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

①外包矩形表示多邊形

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

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

③查詢；

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

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

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

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

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

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

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

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

射線法，從點水平出發做一條射線，計算該射線與多邊形的邊的相交點個數，當點不在多邊形邊或者是頂點上時，如果是奇數，那么點就一定在多邊形內部，否則，在外部，其中它的算法復雜度是O(N),N為多邊形的邊數。

本發明相對于現有技術具有如下有益效果：實現了圍欄的優化算法，提高了查找電子圍欄電單車出入的效率；設計了電子圍欄的軟件結構和數據庫結構并實現了電子圍欄，因為電子圍欄設計在地圖上直接畫出多邊形，與實際的地理的經緯度有很大的誤差，在繪制電子圍欄的時候，所以盡量先確定幾個角的經緯度，再把相鄰角連接起來，同時，確保地圖是最大倍數，這樣可以保證誤差最小

附圖說明

圖1為地理圍欄的流程示意圖。

圖2-5為射線法的示意圖。

圖6-14為樹索引法的結構示意圖。

具體實施方式

方法分析

本產品的核心問題在于電單車是否成功的停在所規定的區域內，例如凸多邊形、凹多邊形區域。

方法選擇

從數學的方式來看，就是一個點是否在規定的區域內，常見的點與多邊形的算法有點線判斷法、夾角和法、射線法，其中射線法用凹多邊形，點線判斷法、夾角和法用于凸多邊形。

射線法是使用最廣泛的方法之一，相比較其他算法而言，它不但可以正確使用在凹多邊形上，而且不需要考慮精度誤差問題。該算法思想是從點水平出發做一條射線，計算該射線與多邊形的邊的相交點個數，當點不在多邊形邊或者是頂點上時，如果是奇數，那么點就一定在多邊形內部，如圖2所示，否則，在外部，如圖3所示。其中它的算法復雜度是O(N),N為多邊形的邊數。

如圖2所示，射線與多邊形的左右交點數分別為5和3，均是奇數，則點p在多邊形內；如圖3所示，多邊形外部的點p與多邊形交點數是6，則點在多邊形外面。以上所述的是射線法算法的基本思想，適合于大多數被判斷點和多邊形的位置關系，但是也有一些特殊的位置關系的判斷結果是錯誤的。以下將列舉這些特殊情況：

①、射線過水平線

②、射線過頂點

如圖4所示，射線與多邊形的交點為2個和1個，不符合常規的邏輯思維。

如圖5所示，射線與多邊形的交點為2個和1個，不符合常規的邏輯思維。

顯然，根據射線算法基本思想無法判定點與多邊形的位置關系，所以需要改進此算法。

樹索引法