基于Wrangler树索引的点面关系剖断以及效能优化总计

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

1.背景

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

a.网格索引由于对一切空间拓展网格划分,假使划分粒度太细轻松并发索引冗余,假设划分粒度太大则索引功能又宏大下滑。

    图片 1

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

        图片 2

为更为优化索引,大家决定动用Rubicon树来举行优化。

2.R树介绍

RAV4树首要选用空间划分的观念,即利用MB奇骏(Minimal Bounding
Rectangle,最小边界矩形)的办法,从叶子结点初始用矩形(rectangle)将空间框起来,结点越往上,框住的上空就越大,以此对空中实行划分:

        图片 3

有着的原本空间要素均是叶节点,那样便不会现出如四叉树索引和网格索引中出现的半空中要素被几个索引段指引,从而出现多量冗余索引的难题。

3.依据JTS的切实可行落实

JTS中提供了构建索引的措施,其能够创设四叉树索引、LAND树索引、KD索引等。这里,大家平昔运用JTS来创设Rubicon树索引。

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

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

3.1奥迪Q5树的构建

选拔GT读取到当地的SHP,获取到独具的要素集,然后遍历要素将envelope和因素新闻一一插入至StrTree中,塑造昂Cora树:

   图片 4

3.2基于奔驰M级树的查询

将查询的长空条件构产生一个Envelope在奥迪Q7树中询问,对查询出来的结果再度打开点面关系判别:

   图片 5

4.优化

在大家从前的三种索引方法中,大家均将引得文件保留到了本土,每一遍调用时去加载索引,如此IO是二个一点都不小的瓶颈。现在大家创立三个器皿,将StrTree保存至该容器中。查询时,直接从内部存款和储蓄器中获取到该树。

5.功效相比

5.1查询成效相比较

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

   图片 6

 

分级对运用的三种索引举行了质量比较:

a.本地网格索引:

   图片 7

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

 图片 8

c.内存R树索引:

 图片 9

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

5.2索引营造功能比较

样本数量有三千五个面要素,从前的二种索引均接纳本地下工作具创设,时间大约是1S光景(未有具体计算)。以往使用JTS营造酷威树索引,效能为:

   图片 10

5.3占用的内部存款和储蓄器作用

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

一般监察和控制内装有二种艺术,通过工具查看或然代码段编写。代码段编写能够因而使用SizeOf.jar完结,工具查看能够通过jvisualvm实现:

   图片 11

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

网格索引大小为:4.4M。

混合索引文件的分寸为:8.4M。

而读入内存中的奇骏树索引的轻重为:4.3M。

是因为大家存款和储蓄了要素所满含的具有新闻,理论上,假设大家将积攒新闻特别收缩,内部存款和储蓄器占用会更加小。近日来看,SHP数据作者的轻重,会跟存入内部存款和储蓄器的音信大小有间接涉及。

6.总结

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

a.索引创设中的成分别得到取形式为本地SHP读取,供给扩展成对第三方服务数量的帮助。

b.当本田UR-V数查询命中唯有贰个成分时,因为小小的矩形的限定是越过等于实际要素范围的,所以还要开始展览叁遍点面判别。如此,当图层要素个数自己相当的少时,建设构造索引不确定能够加速。

 

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

                                                                             
假若你感觉本文确实协助了您,可以微信扫一扫,举行小额的打赏和鼓励,谢谢^_^

                                                                   
                     
图片 12

 

相关文章