若转发请于显然处注解出处,若转发请于鲜明处标注出处

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

作品版权由笔者李晓晖和天涯论坛共有,若转发请于显明处标记出处:http://www.cnblogs.com/naaoveGIS/

1.背景

针对决断三个点落在面图层中哪些要素上的急需,在小编后边的博客:WebGIS中一种遵照网格索引推断点面关系的点子http://www.cnblogs.com/naaoveGIS/p/5148185.html)中有详实的叙说。其规律大致为:

             图片 1

其拍卖步骤为:

                     图片 2

1.背景

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

a.网格索引由于对全体空间拓宽网格划分,要是划分粒度太细轻松出现索引冗余,假若划分粒度太大则索引功能又很大缩短。

    图片 3

b.四叉树索引一样存在一个图元标志被多少个区域所关联,相应地蕴藏在三个叶子节点上,那样就存在索引的冗余,与网格索引存在同样的弊病。

        图片 4

为更为优化索引,大家决定动用奥德赛树来开展优化。

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

a.网格索引方案分为了三个索引文件和三个数据文件,任何诉求步入时均会先读取索引文件,再读取数据文件,那么很轻便并发财富争抢状态,不方便人民群众并发协助。

b.网格的轻重缓急会严重影响到查询功能,可是假若网格建设构造的足足小,那么索引文件不断叠合,同样会招致磁盘寻址开销的时刻增添。

c.数据的读取绝对要经过四回IO,一回读索引,叁次读数据,会影响读取功效。

2.R树介绍

瑞虎树首要使用空间划分的见识,即选取MBLacrosse(Minimal Bounding
Rectangle,最小边界矩形)的法子,从叶子结点起头用矩形(rectangle)将空间框起来,结点越往上,框住的上空就越大,以此对空中举行私分:

        图片 5

怀有的本来面目空间要素均是叶节点,这样便不会出现如四叉树索引和网格索引中出现的半空中要素被八个索引段教导,进而出现多量冗余索引的主题材料。

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

四叉树、福睿斯树等均是空间索引常用的算法,这里自个儿采纳使用四叉索引来举行更为优化。四叉树索引原理极度轻便,就要叁个限量依照深度,不断平分,如图所示:

                     图片 6

此处优化思路是:将在素首先进行四叉树平分,然后对每一个叶子节点富含的限量再张开网格索引生成:

            图片 7

3.依据JTS的求实贯彻

JTS中提供了营造索引的方法,其能够创设四叉树索引、汉兰达树索引、KD索引等。这里,我们平昔动用JTS来构建LX570树索引。

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

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

4.优化方案的详细描述

3.1CRUISER树的塑造

动用GT读取到本地的SHP,获取到具有的要素集,然后遍历要素将envelope和因素音讯一一插入至StrTree中,塑造Tucson树:

   图片 8

4.1索引的转移步骤

a.首先生成数据文件。

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

c.依据要素个数和网格因子,算出全方位范围内网格的个数,用全数范围的四角坐标与网格因子计算,得出贰个网格的BlockXsize和BlokcYsize。

d.针对种种叶子节点,塑造该节点的网格索引,索引中包罗了网格与要素的照看关系。

变化文书截图:

                        图片 9

3.2依照PRADO树的询问

将查询的长空条件构产生三个Envelope在大切诺基树中查询,对查询出来的结果再行张开点面关系判别:

   图片 10

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.成效相比较

6.特别优化

a.在读取索引基本音信后得以将该音讯缓存至内部存款和储蓄器中,减弱Config文件的IO次数。

b.生成索引时,假如三个网格只含有了三个成分的消息,可以将该音讯也结合至网格索引中。那样,查询时,假诺查询到的网格只包涵单个要素,则能够平昔在目录准将要素音信获取,而不需求再对数码索引做读取操作,裁减对数据索引的IO次数。

                                                                        
—–接待转发,但保留版权,请于显然处标记出处:http://www.cnblogs.com/naaoveGIS/

                                                                       
    
假让你认为本文确实援助了您,能够微信扫一扫,实行小额的打赏和激励,感谢^_^

                                                                                                   
        图片 11

5.1查询功用相比较

在测量试验数据中选中二个特殊点(多个多边形的交接处):

   图片 12

 

各自对利用的三种索引进行了品质比较:

a.当地网格索引:

   图片 13

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

 图片 14

c.内存R树索引:

 图片 15

可知查询成效快了一倍左右。

5.2索引创设效能相比较

样本数量有3000多个面要素,以前的二种索引均选取本地下工作具营造,时间大约是1S前后(未有实际总结)。今后接纳JTS创设卡宴树索引,功效为:

   图片 16

5.3据为己有的内部存款和储蓄器功能

此索引的优化中,我们将数据总体存入了内部存款和储蓄器。这里不可不重点内部存款和储蓄器的占用量有多大。

诚如监察和控制内具有二种方法,通过工具查看只怕代码段编写。代码段编写能够经过行使SizeOf.jar完毕,工具查看可以透过jvisualvm实现:

   图片 17

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

网格索引大小为:4.4M。

混合索引文件的大小为:8.4M。

而读入内部存款和储蓄器中的奥迪Q5树索引的分寸为:4.3M。

由于大家存款和储蓄了要素所包括的有着音信,理论上,假若我们将累积信息更为削减,内部存款和储蓄器占用会越来越小。近来来看,SHP数据作者的分寸,会跟存入内部存储器的新闻大小有直接关联。

6.总结

最近目录格局任然有几点不足:

a.索引塑造中的要素获取格局为本地SHP读取,供给扩张成对第三方服务数据的支撑。

b.当Escort数查询命中唯有一个要素时,因为小小的矩形的界定是超越等于实际要素范围的,所以还要开展一回点面判别。如此,当图层要素个数本身非常的少时,创设索引不肯定可以加快。

 

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

                                                                             
假使你以为本文确实帮助了您,能够微信扫一扫,举办小额的打赏和鼓劲,多谢^_^

                                                                   
                     
图片 18

 

相关文章