一、案例概述

      主要爲解決監測物(wù)體是否在指定區域内，可(kě)實現離開區域報警，或在内部區域中不聽從指令等，可(kě)解決多(duō)種利用(yòng)空間控制載體的(de)方案。算(suàn)法要求計算(suàn)速度要快(kuài)，并且計算(suàn)精準。配套區域規劃軟件，可(kě)實現空間數據提取，規劃等。與區域識别算(suàn)法形成閉環産品。

二、技術特色

      區域搜索算(suàn)法進行自主研發，不依賴與第三方軟件，算(suàn)法采用(yòng)标準C語言自主編寫，算(suàn)法的(de)編寫共分(fēn)爲兩個部分(fēn)，一個是建立索引，一個是點與多(duō)邊形的(de)比較。

      空間索引是對存儲在介質上的(de)數據位置信息的(de)描述，因此系統的(de)設計者必須将數據在磁盤上的(de)位置加以 記錄和(hé)組織，通(tōng)過在内存中的(de)一些計算(suàn)來取代對磁盤漫無目的(de)的(de)訪問，才能提高(gāo)系統的(de)效率 ，尤其是GIS涉及的(de)是各種海量的(de)複雜數據，索引對于處理(lǐ)的(de)效率是至關重要的(de)，用(yòng)來提高(gāo)系統對數據獲取的(de)效率。

      空間數據索引就是指依據空間對象的(de)位置和(hé)形狀或空間對象 之間的(de)某種空間關系，按一定順序排列的(de)一種數據結構，其中包含空間對象的(de)概要信息，如對象的(de)标識、外接矩形及指向空間對象實體的(de)指針。作爲一種輔助性的(de)空間數據結構，空間索引介于空間操作算(suàn)法和(hé)空間對象之間，它通(tōng)過篩選作用(yòng)，大(dà)量與特定空間操作無關的(de)空間對象被排除，從而提高(gāo)空間操作的(de)速度和(hé)效率。空間索引性能的(de)優劣直接影(yǐng)響空間數據庫和(hé)地理(lǐ)信息系統的(de) 整體性能，它是空間數據庫和(hé)地理(lǐ)信息系統的(de)一項關鍵技術。

      空間索引一般是自頂向下(xià)、逐級劃分(fēn)空間的(de)各種數據結構，早期的(de)空間數據管理(lǐ)軟件，大(dà)多(duō)采用(yòng)文件系統存儲空間信息，屬性則存儲在關系數據庫中。空間數據索引一般采用(yòng)網格索引。網格索引主要用(yòng)來對點的(de)集合進行索引（盡管它們也(yě)能用(yòng)來處理(lǐ)區域），可(kě)擴展哈希形式目錄用(yòng)于對空間數據進行索引。許多(duō)索引結構 （Bang文件、Buddy樹和(hé)多(duō)級别網格文件）的(de)提出都是對這個基本思想進行深化(huà)而得(de)的(de)。

      對一些非常自然地處理(lǐ)區域數據，應用(yòng)最廣泛的(de)是R樹，已經可(kě)以在商用(yòng)的(de)DBMS中看到R樹索引。這是由于R樹相對簡單，能同時處理(lǐ)點和(hé)區域數據，而且它的(de)性能至少不比那些更複雜的(de)索引結構差。R樹是多(duō)維空間的(de)遞歸子劃分(fēn)。與區域四叉樹相比 （區域四叉樹是基于多(duō)維空間的(de)遞歸子分(fēn)解并獨立于實際數據集合這樣的(de)索引方法），R樹中的(de)空間分(fēn)解依賴于索引的(de)數據集。可(kě)以把R樹想像成是B+樹的(de)思想應用(yòng)到空間數據上，R樹的(de)許多(duō)變形包括BSP樹、K-D-B樹、Cell樹、HilbertR樹、Packed樹、R * 樹、R+樹、TV樹和(hé)X樹同時處理(lǐ)區域數據和(hé)點數據的(de)索引。

      索引一般以文件形式存在磁盤中（也(yě)可(kě)以存于内存中），存儲的(de)索引的(de)原理(lǐ)大(dà)緻概括爲以空間換時間，數據庫在未添加索引的(de)時候進行查詢默認的(de)是進行全量搜索，也(yě)就是進行全局掃描，有多(duō)少條數據就要進行多(duō)少次查詢，然後找到相匹配的(de)數據就把他(tā)放到結果集中，直到全表掃描完。而建立索引之後，會将建立索引的(de)KEY值放在一個n叉樹上（BTree）。因爲B樹的(de)特點就是适合在磁盤等直接存儲設備上組織動态查找表，每次以索引進行條件查詢時，會去樹上根據key值直接進行搜索。

      建立索引的(de)目的(de)是加快(kuài)對表中記錄的(de)查找或排序。

      ① 建立索引的(de)列可(kě)以保證行的(de)唯一性，生成唯一的(de)rowId

      ② 建立索引可(kě)以有效縮短數據的(de)檢索時間

      ③ 建立索引可(kě)以加快(kuài)表與表之間的(de)連接

      ④ 爲用(yòng)來排序或者是分(fēn)組的(de)字段添加索引可(kě)以加快(kuài)分(fēn)組和(hé)排序順序 區域搜索算(suàn)法索引部分(fēn)主要采用(yòng)四叉樹索引、網格索引、R樹索引。

      整體算(suàn)法邏輯爲爲預先對多(duō)邊形進行三角剖分(fēn)，建立多(duō)邊形的(de)索引。當進行點判斷時，首先通(tōng)過索引篩選出需要判斷的(de)多(duō)邊形，然後使用(yòng)射線法、角度和(hé)判别法、三角剖分(fēn)法判斷是否在多(duō)邊形内。