一(yī)、案例概述

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

二、技術特色

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

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

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

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

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

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

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

      ① 建立索引的列可以保證行的唯一(yī)性，生(shēng)成唯一(yī)的rowId

      ② 建立索引可以有效縮短數據的檢索時間

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

      ④ 爲用來排序或者是分(fēn)組的字段添加索引可以加快分(fēn)組和排序順序 區域搜索算法索引部分(fēn)主要采用四叉樹(shù)索引、網格索引、R樹(shù)索引。

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