R树建立路网索引（附代码）

R树作为一种可以存储高维数据的数据结构，在时空数据挖掘和空间信息存储方面得到了广泛的应用，在这里我将介绍如何利用R树建立路网的空间索引，并进行测试。

首先我们必须准备数据，才能开始实验，这里选取的是北京市的路网数据：路网数据如何提取请参考我的这篇文章：

提取shapefile文件的路网信息

在这个文章的工作中，我已经完成了对路网信息的提取

1.在实现R树的建立之前，我们首先必须得知道R树的基本知识，有关R树的详细信息，许多博客都写的非常详细，我推荐这篇文章：R树详解 

里面详细的讲述了R树的知识。

但是他博客中提及的伪代码可能大家不太好理解，这里我融合自己的理解，在他的基础上，对他所提及的插入和查询算法伪代码做了补充，并和本项目中R树路网建立的特点做了少许注释

这里先结合本项目的特点针对性的做简述：

1.是一种和B树结构类似，存储高维数据的结构；

2.从下往上看，R树的叶子结点存储的是数据的最小边界矩阵的索引，而他们的父亲结点又为包含叶子结点的最小边界矩阵，以此类推，直到根结点；

注：在本项目中，叶子节点索引为路网中路段

根结点包括整个北京市路网的几个矩阵

一下是插入和查询的伪代码：

##插入

```

先定义两个辅助函数：

1.choose_leaf:

描述：用来帮助插入新记录时找到插入位置

输入：新的记录E，根结点T

输出：一个叶子节点

If T为叶子节点：返回T

Else 遍历T节点上的所有矩阵条目X，找到添加E扩张最小的条目，然后设T为X的孩子结点继续执行choose_leaf

2.adjustTree

描述：叶子结点的改变向上传递至根结点；

输入：新的记录E，结点L

输出：已经调整好各个条目矩阵大小的R树

Step1:设N为L，如果原结点已经分裂为L和LL，则设NN为LL

Step2：若N为根结点，返回R树

Step3：调整N的父亲结点P对应的最小边界矩阵，使其正好覆盖N中所有条目

Step4：如果传递产生了分裂结点LL，则新建一个条目，为覆盖LL的最小边界矩阵，若P结点能够容纳LL，则加入大P中，反之，对P执行分裂操作，产生P和PP

Step5：设N为P，若在step4中执行了分裂操作，则设NN为PP，然后，从step2开始再次执行函数（递归）

然后是主算法：

函数：Insert

输入：插入的新记录E，R树

输出：更新后的R树

I1：对于给定E，调用choose_leaf找到插入的叶子结点L；

I2：如果L仍有空间，则将E插入进去，如果没有，还要

进行分裂操作得到L和LL

I3：对I2中得到结点进行adjust操作，如果分裂了，LL也

要进行adjust操作

I4：如果分裂操作导致根结点分裂，则新建一个根结点，

包含之前的所有结点

```

##搜索

```

函数：InterSection

描述：对给的范围，返回该范围内的所有路网索引

输入：一个查找矩阵X，R树根结点T

输出：X覆盖的所有记录

If T

是叶子节点：

  then：直接查询X覆盖的所有记录，并返回

Else T是非叶子节点：

  then：对于该结点上的所有条目，对它们

  的孩子进行InterSection操作

End

if

```

2.在基本的理论知识了解以后就是实际的操作过程了，在这里我把过程分为以下四步：

1.建立R树索引文件Rtree.dat和Rtree.idx

2.利用python的pickle库将路网信息用一个列表储存并序列化到磁盘上形成AllData文件

3.打开Rtree，Alldata文件并以路段的最小边界矩阵作为依据，将每条路段索引依次插入到R树中

4.代码的测试：输入给定坐标x，y，以及范围t，调用InterSection搜索函数，得到查询矩阵[x-t,y-t,x+t,y+t],构建小范围路网（模拟在线匹配中拼车用户发出请求，在一定范围内建立路网的情况）。

5.对2中的省道路网数据和4中查询到的数据做可视化处理验证准确性

1-4步骤的代码如下：

```

import shapefile

import csv

from rtree import index

dirname = 'F:/carpool_item/Beijing/xydata/AllData.csv'

rtreename = 'F:/carpool_item/Beijing/xydata/Rtree'

fileNames = {'城市快速路': 'F:/carpool_item/Beijing/城市快速路_polyline.shp',\

            '高速': 'F:/carpool_item/Beijing/高速_polyline.shp',\

            '国道': 'F:/carpool_item/Beijing/国道_polyline.shp',\

            '九级路': 'F:/carpool_item/Beijing/九级路_polyline.shp',\

            '省道': 'F:/carpool_item/Beijing/省道_polyline.shp',\

            '县道': 'F:/carpool_item/Beijing/县道_polyline.shp',\

            '乡镇村道': 'F:/carpool_item/Beijing/乡镇村道_polyline.shp'}

#处理每种路网

#write csvfile name

csvFile = open(dirname,'w',newline = '')

writer = csv.writer(csvFile)

name = ['id','roadkind','roadname','bbox','points','other']

writer.writerow(name)

#build Rtree

fileIdx = index.Rtree(rtreename)

id = 0

for key,value in fileNames.items():

#read shapefile

    sf = shapefile.Reader(value)

    shapeRecords = sf.shapeRecords()

#continue write csvfile and bulid rtree

    for shapeRecord in shapeRecords:

        temp = [str(id),str(key),shapeRecord.record[1],str(shapeRecord.shape.bbox),str(shapeRecord.shape.points)]

        fileIdx.insert(id,shapeRecord.shape.bbox)

        id += 1

        writer.writerow(temp)

csvFile.close()

```

3.在建立R树索引后，我们还需要通过验证来检测我们的索引文件是否正确，在这里以天安门附近的坐标为中心点，在0.64平方千米的范围内进行路网数据的查询，然后把查询结果可视化，以验证准确性，同样放出验证的程序代码：

```

from rtree import index

import csv

import pickle

backName = 'F:/carpool_item/Beijing/xydata/'

rtreename = 'F:/carpool_item/Beijing/xydata/Rtree'

pickleName =  'F:/carpool_item/Beijing/xydata/AllData_pickle.txt'

fileIdx = index.Rtree(rtreename)

while 1:

    # autitude = float(input('please input autitude: '))

    # longitude = float(input('please input longitude: '))

    autitude = 116.3974750042

    longitude = 39.9087239839

    if autitude == 0:

        print('exit...')

        break

    xmin = autitude - 0.004

    xmax = autitude + 0.004

    ymin = longitude - 0.004

    ymax = longitude + 0.004

    IdxData = list(fileIdx.intersection((xmin,ymin,xmax,ymax)))

    print(len(IdxData))

    print(IdxData)

#write csvFile

    csvName = backName + str(autitude) + '_' + str(longitude) + '.csv'

    csvFileW = open(csvName,'w',newline = '')

    writer = csv.writer(csvFileW)

    writer.writerow(['adress','autitude','longitude','phone'])

    file = open(pickleName,'rb')

    reader = pickle.load(file)

    file.close()

    for id in IdxData:

        adress = reader[id + 1][2]

        points = list(eval(str(reader[id + 1][4])))

        for point in points:

            autitude = point[0]

            longitude = point[1]

            temp = [adress,str(autitude),str(longitude),str(id)]

            writer.writerow(temp)

    csvFileW.close()

    break

```

下图是可视化的结果，OK，到这一步就算是结束了；

可视化图