若转发请于分明处标明出处,若转发请于明显处标明出处

文章版权由小编李晓晖和乐乎共有,若转发请于显明处标明出处:http://www.cnblogs.com/naaoveGIS/

文章版权由小编李晓晖和博客园共有,若转发请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

作品版权由小编李晓晖和博客园共有,若转发请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

1.背景

针对判断一个点落在面图层中哪些要素上的急需,在自己事先的博客:WebGIS中一种依据网格索引判断点面关系的法门http://www.cnblogs.com/naaoveGIS/p/5148185.html)中有详尽的描述。其原理大约为:

             图片 1

其拍卖步骤为:

                     图片 2

1.背景

本着判断一个点落在面图层中哪些要素上的须要,在自我后面的博客:WebGIS中一种根据网格索引判断点面关系的艺术http://www.cnblogs.com/naaoveGIS/p/5148185.html)中有详细的叙说。其规律大概为:

             图片 3

其拍卖步骤为:

                     图片 4

1.背景

在事先的博客中,我分别介绍了按照网格的长空引得(http://www.cnblogs.com/naaoveGIS/p/5148185.html)以及四叉树和网格结合的联合索引(http://www.cnblogs.com/naaoveGIS/p/6641449.html),要解决的问题均是判断一个点落在了面图层中的哪个面要素中。单从算法层面上分析,以上两种索引均有一些弊端:

a.网格索引由于对整个空间拓展网格划分,如若划分粒度太细简单现身索引冗余,如果划分粒度太大则索引效能又极大下滑。

    图片 5

b.四叉树索引同样存在一个图元标识被四个区域所提到,相应地囤积在两个叶子节点上,这样就存在索引的冗余,与网格索引存在同样的坏处。

        图片 6

为进一步优化索引,大家决定利用R树来拓展优化。

2.脚下网格索引的多少个缺陷

a.网格索引方案分为了一个索引文件和一个数据文件,任何请求进入时均会先读取索引文件,再读取数据文件,那么很简单出现资源争抢状态,不便于并发协理。

b.网格的深浅会严重影响到查询效能,但是假使网格建立的丰盛小,那么索引文件不断增大,同样会招致磁盘寻址费用的年月净增。

c.数据的读取一定要经过两遍IO,三次读索引,三回读数据,会影响读取效能。

2.当下网格索引的多少个毛病

a.网格索引方案分为了一个目录文件和一个数据文件,任何请求进入时均会先读取索引文件,再读取数据文件,那么很不难出现资源争抢状态,不便于并发支持。

b.网格的大大小小会严重影响到查询成效,然而要是网格建立的丰硕小,那么索引文件不断增大,同样会招致磁盘寻址开销的年华增添。

c.数据的读取一定要透过一次IO,一回读索引,几次读数据,会潜移默化读取效能。

2.R树介绍

R树紧要运用空间划分的见识,即采纳MBR(Minimal Bounding
Rectangle,最小边界矩形)的不二法门,从叶子结点初叶用矩形(rectangle)将空间框起来,结点越往上,框住的空中就越大,以此对空中举办划分:

        图片 7

具有的原有空间要素均是叶节点,这样便不见面世如四叉树索引和网格索引中冒出的空中要素被多个索引段指点,进而现身多量冗余索引的题材。

3.方案的优化,基于网格索引的索引四叉树划分

四叉树、R树等均是空间索引常用的算法,那里自己选拔拔取四叉索引来举办越发优化。四叉树索引原理相当简单,即将一个范围依照深度,不断平分,如图所示:

                     图片 8

此地优化思路是:将要素首先进行四叉树平分,然后对每个叶子节点包蕴的限制再拓展网格索引生成:

            图片 9

3.方案的优化,基于网格索引的索引四叉树划分

四叉树、R树等均是空间索引常用的算法,那里自己选取使用四叉索引来举办更为优化。四叉树索引原理卓殊不难,即将一个范围根据深度,不断平分,如图所示:

                     图片 10

那里优化思路是:将要素首先举行四叉树平分,然后对各样叶子节点包罗的范围再拓展网格索引生成:

            图片 11

3.基于JTS的切实得以已毕

JTS中提供了构建索引的艺术,其得以构建四叉树索引、R树索引、KD索引等。那里,大家平素利用JTS来构建R树索引。

JTS的介绍:https://en.wikipedia.org/wiki/JTS_Topology_Suite

JTS的源码下载:https://sourceforge.net/projects/jts-topo-suite/?source=navbar

4.优化方案的详细描述

4.优化方案的详细描述

3.1R树的构建

运用GT读取到本地的SHP,获取到独具的要素集,然后遍历要素将envelope和因素音信一一插入至StrTree中,构建R树:

   图片 12

4.1索引的变迁步骤

a.首先生成数据文件。

b.通过安装的四叉树深度,算出叶子节点的个数。然后经过取得到的要素四角坐标,算出叶子节点的四角范围:leafminx、leafminy、leafmaxx、leafmaxy。

c.根据要素个数和网格因子,算出任何范围内网格的个数,用全套范围的四角坐标与网格因子计算,得出一个网格的BlockXsize和BlokcYsize。

d.针对每个叶子节点,建立该节点的网格索引,索引中隐含了网格与要素的附和关系。

转移文书截图:

                        图片 13

4.1索引的变通步骤

a.首先生成数据文件。

b.通过安装的四叉树深度,算出叶子节点的个数。然后经过取得到的要素四角坐标,算出叶子节点的四角范围:leafminx、leafminy、leafmaxx、leafmaxy。

c.依照要素个数和网格因子,算出总体范围内网格的个数,用任何范围的四角坐标与网格因子总计,得出一个网格的BlockXsize和BlokcYsize。

d.针对每个叶子节点,建立该节点的网格索引,索引中包蕴了网格与要素的附和关系。

转移文书截图:

                        图片 14

3.2基于R树的询问

将查询的空中条件构造成一个Envelope在R树中查询,对查询出来的结果再行开展点面关系判断:

   图片 15

4.2数额读取

a.读取配置获取到要素的四角范围mapminx、mapminy、mapmaxx、mapmaxy、leafgeoxsize、leafgeoysize。

b.通过mapminx、mapminy、leafgeoxsize、leafgeoysize参数算出该XY坐标所在的网格索引编号。

c.读取该网格索引,获取到该索引的leafminx、leafminy、leafmaxx、leafmaxy、blockxsize、blockysize。

d.通过leafmaxx、leafmaxy以及blockxsize、blockysize算出XY所在网格索引的字节地方pos,将磁盘指针移动至该pos处。

e.获得到目录中含有的元素新闻,比如要素所在的数据文件中的datapos。

f.读取数据文件,在该文件的datapos处将详细新闻读取再次回到。

4.2多少读取

a.读取配置获取到要素的四角范围mapminx、mapminy、mapmaxx、mapmaxy、leafgeoxsize、leafgeoysize。

b.通过mapminx、mapminy、leafgeoxsize、leafgeoysize参数算出该XY坐标所在的网格索引编号。

c.读取该网格索引,获取到该索引的leafminx、leafminy、leafmaxx、leafmaxy、blockxsize、blockysize。

d.通过leafmaxx、leafmaxy以及blockxsize、blockysize算出XY所在网格索引的字节地点pos,将磁盘指针移动至该pos处。

e.获得到目录中含有的要素音信,比如要素所在的数据文件中的datapos。

f.读取数据文件,在该文件的datapos处将详细新闻读取再次回到。

4.优化

在大家前边的二种索引方法中,大家均将引得文件保留到了当地,每回调用时去加载索引,如此IO是一个很大的瓶颈。现在大家创制一个容器,将StrTree保存至该容器中。查询时,直接从内存中获取到该树。

5.方案优点总计

a.将一个大索引文件分为七个目录文件,在大方随机点并发访问时,可以将压力负载至各文件上,裁减同一文件读取时的资源争抢IO瓶颈。

b.每一个索引文件大小大大减小,读取会更快,磁盘寻址也会更快。

c.为扩充网格命中单个(非多个)要素的几率,可以将种种网格的高低进一步减少,其招致的网格索引增大会平摊至每个网格索引上,从而使副功能变小。

5.方案优点总计

a.将一个大索引文件分为两个目录文件,在大方随机点并发访问时,可以将压力负载至各文件上,减弱同一文件读取时的资源争抢IO瓶颈。

b.每一个目录文件大小大大减小,读取会更快,磁盘寻址也会更快。

c.为伸张网格命中单个(非七个)要素的票房价值,可以将每个网格的轻重进一步减弱,其招致的网格索引增大会平摊至每个网格索引上,从而使副效用变小。

5.作用相比较

6.尤其优化

a.在读取索引基本消息后可以将该新闻缓存至内存中,收缩Config文件的IO次数。

b.生成索引时,如果一个网格只含有了一个要素的音讯,能够将该新闻也构成至网格索引中。那样,查询时,即便查询到的网格只含有单个要素,则足以一直在目录中将要素新闻获取,而不须要再对数据索引做读取操作,裁减对数据索引的IO次数。

                                                                        
—–欢迎转发,但保留版权,请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

                                                                       
    
如若您认为本文确实协理了您,可以微信扫一扫,进行小额的打赏和鞭策,谢谢
^_^

                                                                                                   
        图片 16

6.更为优化

a.在读取索引基本音讯后方可将该新闻缓存至内存中,缩小Config文件的IO次数。

b.生成索引时,若是一个网格只含有了一个因素的音信,可以将该信息也结成至网格索引中。那样,查询时,即便查询到的网格只含有单个要素,则能够直接在目录少校要素消息得到,而不须求再对数据索引做读取操作,收缩对数码索引的IO次数。

                                                                        
—–欢迎转发,但保留版权,请于分明处标明出处:http://www.cnblogs.com/naaoveGIS/

                                                                       
    
如若您认为本文确实支持了你,可以微信扫一扫,进行小额的打赏和鞭策,谢谢
^_^

                                                                                                   
        图片 17

5.1查询功效相比

在测试数据中当选一个特殊点(四个多边形的交接处):

   图片 18

 

各自对利用的二种索引举办了性能比较:

a.本地网格索引:

   图片 19

b.本地混合索引(四叉树与网格索引整合):

 图片 20

c.内存R树索引:

 图片 21

可知查询作用快了一倍左右。

5.2索引构建作用相比较

样本数量有2000七个面要素,从前的三种索引均选择当地工具构建,时间大体是1S光景(没有切实可行总计)。现在应用JTS构建R树索引,成效为:

   图片 22

5.3占用的内存效用

此索引的优化中,大家将数据总体存入了内存。那里不可不着眼内存的占用量有多大。

诚如监控内有所三种方法,通过工具查看或者代码段编写。代码段编写可以经过行使SizeOf.jar完结,工具查看可以透过jvisualvm完毕:

   图片 23

原本的地点SHP数据大小为:3.8M。

网格索引大小为:4.4M。

混合索引文件的轻重缓急为:8.4M。

而读入内存中的R树索引的分寸为:4.3M。

鉴于大家存储了要素所含有的装有音讯,理论上,假如大家将积存新闻更为削减,内存占用会更小。近日来看,SHP数据本身的尺寸,会跟存入内存的音信大小有直接关系。

6.总结

眼前目录格局任然有几点不足:

a.索引构建中的要素获取格局为当地SHP读取,须求扩展成对第三方服务数量的支撑。

b.当R数查询命中唯有一个因素时,因为小小的矩形的界定是大于等于实际要素范围的,所以还要开展一次点面判断。如此,当图层要素个数本身不多时,建立索引不必然可以加快。

 

                             —–欢迎转发,但保留版权,请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

                                                                             
如若你认为本文确实援助了您,可以微信扫一扫,举行小额的打赏和鼓励,谢谢
^_^

                                                                   
                     
图片 24

 

相关文章