一(yī)、案例概述

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

二、技術特色

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

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

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

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

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

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

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

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

      ② 建立索引可以有效縮短數據的檢索時(shí)間(jiān)

      ③ 建立索引可以加快(kuài)表與表之間(jiān)的連接

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

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