R樹作為一種可以存儲高維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，在時空數(shù)據(jù)挖掘和空間信息存儲方面得到了廣泛的應(yīng)用，在這里我將介紹如何利用R樹建立路網(wǎng)的空間索引，并進行測試。
首先我們必須準備數(shù)據(jù)，才能開始實驗，這里選取的是北京市的路網(wǎng)數(shù)據(jù)：路網(wǎng)數(shù)據(jù)如何提取請參考我的這篇文章：
在這個文章的工作中，我已經(jīng)完成了對路網(wǎng)信息的提取
1.在實現(xiàn)R樹的建立之前，我們首先必須得知道R樹的基本知識，有關(guān)R樹的詳細信息，許多博客都寫的非常詳細，我推薦這篇文章：R樹詳解?
里面詳細的講述了R樹的知識。
但是他博客中提及的偽代碼可能大家不太好理解，這里我融合自己的理解，在他的基礎(chǔ)上，對他所提及的插入和查詢算法偽代碼做了補充，并和本項目中R樹路網(wǎng)建立的特點做了少許注釋
這里先結(jié)合本項目的特點針對性的做簡述：
1.是一種和B樹結(jié)構(gòu)類似，存儲高維數(shù)據(jù)的結(jié)構(gòu)；
2.從下往上看，R樹的葉子結(jié)點存儲的是數(shù)據(jù)的最小邊界矩陣的索引，而他們的父親結(jié)點又為包含葉子結(jié)點的最小邊界矩陣，以此類推，直到根結(jié)點；
注：在本項目中，葉子節(jié)點索引為路網(wǎng)中路段
根結(jié)點包括整個北京市路網(wǎng)的幾個矩陣
一下是插入和查詢的偽代碼：
##插入
```
先定義兩個輔助函數(shù)：
1.choose_leaf:
描述：用來幫助插入新記錄時找到插入位置
輸入：新的記錄E，根結(jié)點T
輸出：一個葉子節(jié)點
If T為葉子節(jié)點：返回T
Else 遍歷T節(jié)點上的所有矩陣條目X，找到添加E擴張最小的條目，然后設(shè)T為X的孩子結(jié)點繼續(xù)執(zhí)行choose_leaf
2.adjustTree
描述：葉子結(jié)點的改變向上傳遞至根結(jié)點；
輸入：新的記錄E，結(jié)點L
輸出：已經(jīng)調(diào)整好各個條目矩陣大小的R樹
Step1:設(shè)N為L，如果原結(jié)點已經(jīng)分裂為L和LL，則設(shè)NN為LL
Step2：若N為根結(jié)點，返回R樹
Step3：調(diào)整N的父親結(jié)點P對應(yīng)的最小邊界矩陣，使其正好覆蓋N中所有條目
Step4：如果傳遞產(chǎn)生了分裂結(jié)點LL，則新建一個條目，為覆蓋LL的最小邊界矩陣，若P結(jié)點能夠容納LL，則加入大P中，反之，對P執(zhí)行分裂操作，產(chǎn)生P和PP
Step5：設(shè)N為P，若在step4中執(zhí)行了分裂操作，則設(shè)NN為PP，然后，從step2開始再次執(zhí)行函數(shù)（遞歸）
然后是主算法：
函數(shù)：Insert
輸入：插入的新記錄E，R樹
輸出：更新后的R樹
I1：對于給定E，調(diào)用choose_leaf找到插入的葉子結(jié)點L；
I2：如果L仍有空間，則將E插入進去，如果沒有，還要
進行分裂操作得到L和LL
I3：對I2中得到結(jié)點進行adjust操作，如果分裂了，LL也
要進行adjust操作
I4：如果分裂操作導致根結(jié)點分裂，則新建一個根結(jié)點，
包含之前的所有結(jié)點
```
##搜索
```
函數(shù)：InterSection
描述：對給的范圍，返回該范圍內(nèi)的所有路網(wǎng)索引
輸入：一個查找矩陣X，R樹根結(jié)點T
輸出：X覆蓋的所有記錄
If T
是葉子節(jié)點：
? then：直接查詢X覆蓋的所有記錄，并返回
Else T是非葉子節(jié)點：
? then：對于該結(jié)點上的所有條目，對它們
? 的孩子進行InterSection操作
End
if
```
2.在基本的理論知識了解以后就是實際的操作過程了，在這里我把過程分為以下四步：
1.建立R樹索引文件Rtree.dat和Rtree.idx
2.利用python的pickle庫將路網(wǎng)信息用一個列表儲存并序列化到磁盤上形成AllData文件
3.打開Rtree，Alldata文件并以路段的最小邊界矩陣作為依據(jù)，將每條路段索引依次插入到R樹中
4.代碼的測試：輸入給定坐標x，y，以及范圍t，調(diào)用InterSection搜索函數(shù)，得到查詢矩陣[x-t,y-t,x+t,y+t],構(gòu)建小范圍路網(wǎng)（模擬在線匹配中拼車用戶發(fā)出請求，在一定范圍內(nèi)建立路網(wǎng)的情況）。
5.對2中的省道路網(wǎng)數(shù)據(jù)和4中查詢到的數(shù)據(jù)做可視化處理驗證準確性
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',\
? ? ? ? ? ? '鄉(xiāng)鎮(zhèn)村道': 'F:/carpool_item/Beijing/鄉(xiāng)鎮(zhèn)村道_polyline.shp'}
#處理每種路網(wǎng)
#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平方千米的范圍內(nèi)進行路網(wǎng)數(shù)據(jù)的查詢，然后把查詢結(jié)果可視化，以驗證準確性，同樣放出驗證的程序代碼：
```
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
```
下圖是可視化的結(jié)果，OK，到這一步就算是結(jié)束了；
