一、案例概述

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

二、技術(shù)特色

      區域搜索算法進(jìn)行自主研發(fā)，不依賴(lài)與第三方軟件，算法采用標準C語(yǔ)言自主編寫(xiě)，算法的編寫(xiě)共分為兩個(gè)部分，一個(gè)是建立索引，一個(gè)是點(diǎn)與多邊形的比較。

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

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

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

      對一些非常自然地處理區域數據，應用最廣泛的是R樹(shù)，已經(jīng)可以在商用的DBMS中看到R樹(shù)索引。這是由于R樹(shù)相對簡(jiǎn)單，能同時(shí)處理點(diǎn)和區域數據，而且它的性能至少不比那些更復雜的索引結構差。R樹(shù)是多維空間的遞歸子劃分。與區域四叉樹(shù)相比 （區域四叉樹(shù)是基于多維空間的遞歸子分解并獨立于實(shí)際數據集合這樣的索引方法），R樹(shù)中的空間分解依賴(lài)于索引的數據集?？梢园裄樹(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ù)同時(shí)處理區域數據和點(diǎn)數據的索引。

      索引一般以文件形式存在磁盤(pán)中（也可以存于內存中），存儲的索引的原理大致概括為以空間換時(shí)間，數據庫在未添加索引的時(shí)候進(jìn)行查詢(xún)默認的是進(jìn)行全量搜索，也就是進(jìn)行全局掃描，有多少條數據就要進(jìn)行多少次查詢(xún)，然后找到相匹配的數據就把他放到結果集中，直到全表掃描完。而建立索引之后，會(huì )將建立索引的KEY值放在一個(gè)n叉樹(shù)上（BTree）。因為B樹(shù)的特點(diǎn)就是適合在磁盤(pán)等直接存儲設備上組織動(dòng)態(tài)查找表，每次以索引進(jìn)行條件查詢(xún)時(shí)，會(huì )去樹(shù)上根據key值直接進(jìn)行搜索。

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

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

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

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

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

      整體算法邏輯為為預先對多邊形進(jìn)行三角剖分，建立多邊形的索引。當進(jìn)行點(diǎn)判斷時(shí)，首先通過(guò)索引篩選出需要判斷的多邊形，然后使用射線(xiàn)法、角度和判別法、三角剖分法判斷是否在多邊形內。