一(yī)、案例概述
主要為(wèi)解決監測物(wù)體是否在指定區域内，可實現離開(kāi)區域報(bào)警，或在内部區域中不聽從(cóng)指令等，可解決多(duō)種利用空間控制載體的方案。算(suàn)法要求計算(suàn)速度要快，并且計算(suàn)精準。配套區域規劃軟件(jiàn)，可實現空間數據提取，規劃等。與區域識别算(suàn)法形成閉環産品。
二、技(jì)術(shù)特色
區域搜索算(suàn)法進行自(zì)主研發，不依賴與第三方軟件(jiàn)，算(suàn)法采用标準C語言自(zì)主編寫，算(suàn)法的編寫共分為(wèi)兩個(gè)部分，一(yī)個(gè)是建立索引，一(yī)個(gè)是點與多(duō)邊形的比較。
空間索引是對存儲在介質上(shàng)的數據位置信息的描述，因此系統的設計者必須将數據在磁盤上(shàng)的位置加以 記錄和組織，通(tōng)過在内存中的一(yī)些計算(suàn)來取代對磁盤漫無目的的訪問，才能(néng)提高(gāo)系統的效率 ，尤其是GIS涉及的是各種海量的複雜(zá)數據，索引對于處理的效率是至關重要的，用來提高(gāo)系統對數據獲取的效率。
空間數據索引就(jiù)是指依據空間對象的位置和形狀或空間對象 之間的某種空間關系，按一(yī)定順序排列的一(yī)種數據結構，其中包含空間對象的概要信息，如對象的标識、外接矩形及指向空間對象實體的指針。作為(wèi)一(yī)種輔助性的空間數據結構，空間索引介于空間操作算(suàn)法和空間對象之間，它通(tōng)過篩選作用，大量與特定空間操作無關的空間對象被排除，從(cóng)而提高(gāo)空間操作的速度和效率。空間索引性能(néng)的優劣直接影響空間數據庫和地理信息系統的 整體性能(néng)，它是空間數據庫和地理信息系統的一(yī)項關鍵技(jì)術(shù)。
空間索引一(yī)般是自(zì)頂向下(xià)、逐級劃分空間的各種數據結構，早期的空間數據管理軟件(jiàn)，大多(duō)采用文件(jiàn)系統存儲空間信息，屬性則存儲在關系數據庫中。空間數據索引一(yī)般采用網格索引。網格索引主要用來對點的集合進行索引（盡管它們也能(néng)用來處理區域），可擴展哈希形式目錄用于對空間數據進行索引。許多(duō)索引結構 （Bang文件(jiàn)、Buddy樹和多(duō)級别網格文件(jiàn)）的提出都是對這個(gè)基本思想進行深化而得的。
對一(yī)些非常自(zì)然地處理區域數據，應用最廣泛的是R樹，已經可以在商用的DBMS中看(kàn)到(dào)R樹索引。這是由于R樹相(xiàng)對簡單，能(néng)同時處理點和區域數據，而且它的性能(néng)至少不比那些更複雜(zá)的索引結構差。R樹是多(duō)維空間的遞歸子劃分。與區域四叉樹相(xiàng)比 （區域四叉樹是基于多(duō)維空間的遞歸子分解并獨立于實際數據集合這樣的索引方法），R樹中的空間分解依賴于索引的數據集。可以把R樹想像成是B+樹的思想應用到(dào)空間數據上(shàng)，R樹的許多(duō)變形包括BSP樹、K-D-B樹、Cell樹、HilbertR樹、Packed樹、R * 樹、R+樹、TV樹和X樹同時處理區域數據和點數據的索引。
索引一(yī)般以文件(jiàn)形式存在磁盤中（也可以存于内存中），存儲的索引的原理大緻概括為(wèi)以空間換時間，數據庫在未添加索引的時候進行查詢默認的是進行全量搜索，也就(jiù)是進行全局掃描，有多(duō)少條數據就(jiù)要進行多(duō)少次查詢，然後找到(dào)相(xiàng)匹配的數據就(jiù)把他放(fàng)到(dào)結果集中，直到(dào)全表掃描完。而建立索引之後，會(huì)将建立索引的KEY值放(fàng)在一(yī)個(gè)n叉樹上(shàng)（BTree）。因為(wèi)B樹的特點就(jiù)是适合在磁盤等直接存儲設備上(shàng)組織動态查找表，每次以索引進行條件(jiàn)查詢時，會(huì)去樹上(shàng)根據key值直接進行搜索。
建立索引的目的是加快對表中記錄的查找或排序。
① 建立索引的列可以保證行的唯一(yī)性，生(shēng)成唯一(yī)的rowId
② 建立索引可以有效縮短數據的檢索時間
③ 建立索引可以加快表與表之間的連接
④ 為(wèi)用來排序或者是分組的字段添加索引可以加快分組和排序順序 區域搜索算(suàn)法索引部分主要采用四叉樹索引、網格索引、R樹索引。
整體算(suàn)法邏輯為(wèi)為(wèi)預先對多(duō)邊形進行三角剖分，建立多(duō)邊形的索引。當進行點判斷時，首先通(tōng)過索引篩選出需要判斷的多(duō)邊形，然後使用射線法、角度和判别法、三角剖分法判斷是否在多(duō)邊形内。
