星空体育·(中国)官方网站GREENMAX NO.1

一、案例概述

      主要为解决监测物体是否在指定区域内，可实现离开区域报警，或在内部区域中不听从指令等，可解决多种利用空间控制载体的方案。算法要求计算速度要快，并且计算精准。配套区域规划软件，可实现空间数据提取，规划等。与区域识别算法形成闭环产品。

二、技术特色

      区域搜索算法进行自主研发，不依赖与第三方软件，算法采用标准C语言自主编写，算法的编写共分为两个部分，一个是建立索引，一个是点与多边形的比较。

      空间索引是对存储在介质上的数据位置信息的描述，因此系统的设计者必须将数据在磁盘上的位置加以 记录和组织，通过在内存中的一些计算来取代对磁盘漫无目的的访问，才能提高系统的效率 ，尤其是GIS涉及的是各种海量的复杂数据，索引对于处理的效率是至关重要的，用来提高系统对数据获取的效率。

      空间数据索引就是指依据空间对象的位置和形状或空间对象 之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间索引性能的优劣直接影响空间数据库和地理信息系统的 整体性能，它是空间数据库和地理信息系统的一项关键技术。

      空间索引一般是自顶向下、逐级划分空间的各种数据结构，早期的空间数据管理软件，大多采用文件系统存储空间信息，属性则存储在关系数据库中。空间数据索引一般采用网格索引。网格索引主要用来对点的集合进行索引（尽管它们也能用来处理区域），可扩展哈希形式目录用于对空间数据进行索引。许多索引结构 （Bang文件、Buddy树和多级别网格文件）的提出都是对这个基本思想进行深化而得的。

      对一些非常自然地处理区域数据，应用最广泛的是R树，已经可以在商用的DBMS中看到R树索引。这是由于R树相对简单，能同时处理点和区域数据，而且它的性能至少不比那些更复杂的索引结构差。R树是多维空间的递归子划分。与区域四叉树相比 （区域四叉树是基于多维空间的递归子分解并独立于实际数据集合这样的索引方法），R树中的空间分解依赖于索引的数据集。可以把R树想像成是B+树的思想应用到空间数据上，R树的许多变形包括BSP树、K-D-B树、Cell树、HilbertR树、Packed树、R * 树、R+树、TV树和X树同时处理区域数据和点数据的索引。

      索引一般以文件形式存在磁盘中（也可以存于内存中），存储的索引的原理大致概括为以空间换时间，数据库在未添加索引的时候进行查询默认的是进行全量搜索，也就是进行全局扫描，有多少条数据就要进行多少次查询，然后找到相匹配的数据就把他放到结果集中，直到全表扫描完。而建立索引之后，会将建立索引的KEY值放在一个n叉树上（BTree）。因为B树的特点就是适合在磁盘等直接存储设备上组织动态查找表，每次以索引进行条件查询时，会去树上根据key值直接进行搜索。

      建立索引的目的是加快对表中记录的查找或排序。

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

      ② 建立索引可以有效缩短数据的检索时间

      ③ 建立索引可以加快表与表之间的连接

      ④ 为用来排序或者是分组的字段添加索引可以加快分组和排序顺序 区域搜索算法索引部分主要采用四叉树索引、网格索引、R树索引。

      整体算法逻辑为为预先对多边形进行三角剖分，建立多边形的索引。当进行点判断时，首先通过索引筛选出需要判断的多边形，然后使用射线法、角度和判别法、三角剖分法判断是否在多边形内。