R樹作為一種可以存儲(chǔ)高維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)超埋，在時(shí)空數(shù)據(jù)挖掘和空間信息存儲(chǔ)方面得到了廣泛的應(yīng)用卦溢，在這里我將介紹如何利用R樹建立路網(wǎng)的空間索引，并進(jìn)行測(cè)試诱咏。
首先我們必須準(zhǔn)備數(shù)據(jù)苔可，才能開始實(shí)驗(yàn)，這里選取的是北京市的路網(wǎng)數(shù)據(jù)：路網(wǎng)數(shù)據(jù)如何提取請(qǐng)參考我的這篇文章：
在這個(gè)文章的工作中袋狞，我已經(jīng)完成了對(duì)路網(wǎng)信息的提取
1.在實(shí)現(xiàn)R樹的建立之前焚辅，我們首先必須得知道R樹的基本知識(shí)，有關(guān)R樹的詳細(xì)信息苟鸯，許多博客都寫的非常詳細(xì)同蜻，我推薦這篇文章：R樹詳解?
里面詳細(xì)的講述了R樹的知識(shí)。
但是他博客中提及的偽代碼可能大家不太好理解早处，這里我融合自己的理解湾蔓，在他的基礎(chǔ)上，對(duì)他所提及的插入和查詢算法偽代碼做了補(bǔ)充砌梆，并和本項(xiàng)目中R樹路網(wǎng)建立的特點(diǎn)做了少許注釋
這里先結(jié)合本項(xiàng)目的特點(diǎn)針對(duì)性的做簡述：
1.是一種和B樹結(jié)構(gòu)類似默责，存儲(chǔ)高維數(shù)據(jù)的結(jié)構(gòu)；
2.從下往上看咸包，R樹的葉子結(jié)點(diǎn)存儲(chǔ)的是數(shù)據(jù)的最小邊界矩陣的索引桃序，而他們的父親結(jié)點(diǎn)又為包含葉子結(jié)點(diǎn)的最小邊界矩陣，以此類推烂瘫，直到根結(jié)點(diǎn)媒熊；
注：在本項(xiàng)目中，葉子節(jié)點(diǎn)索引為路網(wǎng)中路段
根結(jié)點(diǎn)包括整個(gè)北京市路網(wǎng)的幾個(gè)矩陣
一下是插入和查詢的偽代碼：
##插入
```
先定義兩個(gè)輔助函數(shù)：
1.choose_leaf:
描述：用來幫助插入新記錄時(shí)找到插入位置
輸入：新的記錄E坟比，根結(jié)點(diǎn)T
輸出：一個(gè)葉子節(jié)點(diǎn)
If T為葉子節(jié)點(diǎn)：返回T
Else 遍歷T節(jié)點(diǎn)上的所有矩陣條目X芦鳍，找到添加E擴(kuò)張最小的條目，然后設(shè)T為X的孩子結(jié)點(diǎn)繼續(xù)執(zhí)行choose_leaf
2.adjustTree
描述：葉子結(jié)點(diǎn)的改變向上傳遞至根結(jié)點(diǎn)葛账；
輸入：新的記錄E柠衅，結(jié)點(diǎn)L
輸出：已經(jīng)調(diào)整好各個(gè)條目矩陣大小的R樹
Step1:設(shè)N為L，如果原結(jié)點(diǎn)已經(jīng)分裂為L和LL籍琳，則設(shè)NN為LL
Step2：若N為根結(jié)點(diǎn)茄茁，返回R樹
Step3：調(diào)整N的父親結(jié)點(diǎn)P對(duì)應(yīng)的最小邊界矩陣，使其正好覆蓋N中所有條目
Step4：如果傳遞產(chǎn)生了分裂結(jié)點(diǎn)LL巩割，則新建一個(gè)條目裙顽，為覆蓋LL的最小邊界矩陣，若P結(jié)點(diǎn)能夠容納LL宣谈，則加入大P中愈犹，反之，對(duì)P執(zhí)行分裂操作，產(chǎn)生P和PP
Step5：設(shè)N為P漩怎，若在step4中執(zhí)行了分裂操作勋颖，則設(shè)NN為PP，然后勋锤，從step2開始再次執(zhí)行函數(shù)（遞歸）
然后是主算法：
函數(shù)：Insert
輸入：插入的新記錄E饭玲，R樹
輸出：更新后的R樹
I1：對(duì)于給定E，調(diào)用choose_leaf找到插入的葉子結(jié)點(diǎn)L叁执；
I2：如果L仍有空間茄厘，則將E插入進(jìn)去，如果沒有谈宛，還要
進(jìn)行分裂操作得到L和LL
I3：對(duì)I2中得到結(jié)點(diǎn)進(jìn)行adjust操作次哈，如果分裂了，LL也
要進(jìn)行adjust操作
I4：如果分裂操作導(dǎo)致根結(jié)點(diǎn)分裂吆录，則新建一個(gè)根結(jié)點(diǎn)窑滞，
包含之前的所有結(jié)點(diǎn)
```
##搜索
```
函數(shù)：InterSection
描述：對(duì)給的范圍，返回該范圍內(nèi)的所有路網(wǎng)索引
輸入：一個(gè)查找矩陣X恢筝，R樹根結(jié)點(diǎn)T
輸出：X覆蓋的所有記錄
If T
是葉子節(jié)點(diǎn)：
? then：直接查詢X覆蓋的所有記錄哀卫，并返回
Else T是非葉子節(jié)點(diǎn)：
? then：對(duì)于該結(jié)點(diǎn)上的所有條目，對(duì)它們
? 的孩子進(jìn)行InterSection操作
End
if
```
2.在基本的理論知識(shí)了解以后就是實(shí)際的操作過程了撬槽，在這里我把過程分為以下四步：
1.建立R樹索引文件Rtree.dat和Rtree.idx
2.利用python的pickle庫將路網(wǎng)信息用一個(gè)列表儲(chǔ)存并序列化到磁盤上形成AllData文件
3.打開Rtree聊训，Alldata文件并以路段的最小邊界矩陣作為依據(jù)，將每條路段索引依次插入到R樹中
4.代碼的測(cè)試：輸入給定坐標(biāo)x恢氯，y，以及范圍t鼓寺，調(diào)用InterSection搜索函數(shù)勋拟，得到查詢矩陣[x-t,y-t,x+t,y+t],構(gòu)建小范圍路網(wǎng)（模擬在線匹配中拼車用戶發(fā)出請(qǐng)求，在一定范圍內(nèi)建立路網(wǎng)的情況）妈候。
5.對(duì)2中的省道路網(wǎng)數(shù)據(jù)和4中查詢到的數(shù)據(jù)做可視化處理驗(yàn)證準(zhǔn)確性
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',\
? ? ? ? ? ? '九級(jí)路': 'F:/carpool_item/Beijing/九級(jí)路_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樹索引后敢靡，我們還需要通過驗(yàn)證來檢測(cè)我們的索引文件是否正確，在這里以天安門附近的坐標(biāo)為中心點(diǎn)苦银，在0.64平方千米的范圍內(nèi)進(jìn)行路網(wǎng)數(shù)據(jù)的查詢啸胧，然后把查詢結(jié)果可視化，以驗(yàn)證準(zhǔn)確性幔虏，同樣放出驗(yàn)證的程序代碼：
```
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é)束了想括；
