R树作为一种可以存储高维数据的数据结构，在时空数据挖掘和空间信息存储方面得到了广泛的应用，在这里我将介绍如何利用R树建立路网的空间索引，并进行测试。
首先我们必须准备数据，才能开始实验，这里选取的是北京市的路网数据：路网数据如何提取请参考我的这篇文章：
在这个文章的工作中，我已经完成了对路网信息的提取
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，到这一步就算是结束了；
可视化图
网友评论