一、案例概述

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

二、技(jì )術特色

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

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

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

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

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

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

      建立索引的目的是加快對表中(zhōng)記錄的查找或排序。

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

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

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

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

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