社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
网格索引就是在一个地图图层上，按每个小网格宽△w,高△h打上均匀的格网，计算每个图元所占据的网格或者所经过的网格单元集合。这篇文章主要是我在查找网格索引算法的时候，看到一位仁兄在csdn发表的文章http://blog.csdn.net/libinfei8848/article/details/7292096
但是我把他的代码下载完之后运行的效果并不是很好，主要体现在，测试时搜索的结果差距很大，有很多不在范围内的数据也出来了。
问题：给定经度和维度范围，查出在中国的区域，要求性能尽可能的快。
这里，我对他的代码进行了改进，把整块区域按照0.5*1的大小进行划分，把在此区域的对象放入到字典中，因为在字典中的索引可以是字符串，这样可以使x,y的坐标我作为索引。
对于结果的查询，由于网格存储的是一个范围的数据对象，所以我们在查询时，可能输入的数据比网格的范围要小，但是仍然会输出整个网格的范围，如图。这就给我们提出了问题，如何使中间的空白部分变小，我们可以通过细分网格的粒度来减少，具体的感兴趣的一起可以交流。也希望大家提出继续改进的方法。
#encoding=utf-8
'''
Created on 2016年11月23日
@author: tim
此处使用网格索引算法查找，网格划分越细，查找效率越高，可能内存会越大，需要权衡.
还可以使用四叉树算法来做空间索引，但是考虑四叉树可能稍微复杂，使用网格算法
'''
import codecs
from msilib.schema import SelfReg
#空间对象
class GeoObject:
def __init__(self, name, x, y):
self.name = name
self.x = x
self.y = y
#网格索引查找类
class GeoSearch:
def __init__(self):
try:
file = codecs.open("./data.txt", 'r')
except IOError:
print "Can't open the file!"
#读取空间数据到内存中,并获取整个空间数据的外接矩形范围
objArray = [] #objArray 存放的是地理信息对象
dXMax = -999.0 #初始化一个无穷小的范围
dXMin = 999.0
dYMax = -999.0
dYMin = 999.0
file.readline();
for cursor in file:
info = []
for Str in cursor.split(" "):
if Str == "" or Str == " ":
continue
info.append(Str)
if len(info) < 3:
#print info[0], info[1], info[2], info[3], len(info)
continue
mydXMax = mydXMin = float(info[1])
mydYMax = mydYMin = float(info[2])
objArray.append(GeoObject(info[0], mydXMax, mydYMax))
if dXMax < mydXMax:
dXMax = mydXMax
if dXMin > mydXMin:
dXMin = mydXMin
if dYMax < mydYMax:
dYMax = mydYMax
if dYMin > mydYMin:
dYMin = mydYMin
# print '起始的x,y坐标：', dXMin, dYMin,'最大的 x,y坐标', dXMax,dYMax
#将整个空间范围划分等份的网格 self.m_dOriginX，self.m_dOriginY分别代+表网格的起始坐标
#self.dSizeX，self.dSizeY分别代表每个网格的长和宽+++++++++++++++
self.dSizeX=0.5
self.dSizeY=1
self.m_dOriginX = dXMin
self.m_dOriginY = dYMin
self.m_xGridCount = int ((dXMax - dXMin) / self.dSizeX +1) #每行网格的个数
self.m_yGridCount = int ((dYMax - dYMin) / self.dSizeY +1) #每列网格的个数
self.m_vIndexCells = {} #m_vIndexCells 存放网格的id和网格里面的实体对象
for i in range(0, self.m_xGridCount):
for j in range(0, self.m_yGridCount):
self.m_vIndexCells.update({str(i)+str(j):[]}) #将所有网格放入到m_vIndexCells字典中，每个网格又对应一个列表，初始化为空
#将每个对象注册到空间索引中
for obj in objArray:
nXCol = int((obj.x - self.m_dOriginX) / self.dSizeX)
nYCol = int((obj.y - self.m_dOriginY) / self.dSizeY)
if nXCol < 0:
nXCol = 0
if nXCol >= self.m_xGridCount:
nXCol = self.m_xGridCount - 1
if nYCol < 0:
nYCol = 0
if nYCol >= self.m_yGridCount:
nYCol = self.m_yGridCount - 1
iIndex= str(nXCol)+str(nYCol)
all=self.m_vIndexCells.get(iIndex) #设置索引iIndex和追加obj
all.append(obj)
def Search(self, dXMin, dYMin, dXMax, dYMax):
#计算输入外接矩形所在网格的范围,即计算网格的索引位置
nXMin = int((dXMin - self.m_dOriginX) / self.dSizeX)
nXMax = int((dXMax - self.m_dOriginX) / self.dSizeX) #四舍五入
nYMin = int((dYMin - self.m_dOriginY) / self.dSizeY)
nYMax = int((dYMax - self.m_dOriginY) / self.dSizeY)
#遍历这些网格得到所有符合条件的地区
if nXMin==nXMax and nYMin==nYMax:
iIndex = str(nXMin)+str(nYMin)
self.GetObj(iIndex)
elif nXMin==nXMax and nYMin!=nYMax:
for m in range(nYMin, nYMax):
iIndex = str(nXMin)+str(m)
self.GetObj(iIndex)
elif nXMin!=nXMax and nYMin==nYMax:
for n in range(nXMin, nXMax):
iIndex = str(n)+str(nYMin)
self.GetObj(iIndex)
else:
for n in range(nXMin, nXMax):
for m in range(nYMin, nYMax):
iIndex = str(n)+str(m)
print '查找的网格坐标为：' , iIndex
for obj in self.m_vIndexCells.get(iIndex):
print obj.name
for i in (0,1):
print i
#获得网格内对象的的函数
def GetObj(self,iIndex):
for obj in self.m_vIndexCells.get(iIndex):
print obj.name
if __name__ == '__main__':
geoSearch = GeoSearch();
geoSearch.Search( 116.13, 39.75, 116.22, 39.9)
data文件
区县 经度 纬度
北京市 116.4 39.9
天安门 116.38 39.9
东城区 116.42 39.93
西城区 116.37 39.92
崇文区 116.43 39.88
宣武区 116.35 39.87
朝阳区 116.43 39.92
丰台区 116.28 39.85
石景山区 116.22 39.9
海淀区 116.3 39.95
门头沟区 116.1 39.93
房山区 116.13 39.75
通州区 116.65 39.92
顺义区 116.65 40.13
昌平区 116.23 40.22
大兴区 116.33 39.73
怀柔区 116.63 40.32
平谷区 117.12 40.13
密云县 116.83 40.37
延庆县 115.97 40.45
天津市 117.2 39.12
和平区 117.2 39.12
河东区 117.22 39.12
河西区 117.22 39.12
南开区 117.15 39.13
河北区 117.18 39.15
红桥区 117.15 39.17
塘沽区 117.65 39.02
汉沽区 117.8 39.25
大港区 117.45 38.83
东丽区 117.3 39.08
西青区 117.0 39.13
津南区 117.38 38.98
北辰区 117.13 39.22
武清区 117.03 39.38
宝坻区 117.3 39.72
滨海新区 117.68 39.03
宁河县 117.82 39.33
静海县 116.92 38.93
蓟县 117.4 40.05
石家庄市 114.52 38.05
长安区 114.52 38.05
桥东区 114.5 38.05
桥东区 114.9 40.78
桥东区 114.5 37.07
桥西区 114.47 37.05
桥西区 114.87 40.83
桥西区 114.47 38.03
新华区 114.47 38.05
新华区 116.87 38.32
井陉矿区 114.05 38.08
裕华区 114.52 38.02
井陉县 114.13 38.03
正定县 114.57 38.15
栾城县 114.65 37.88
行唐县 114.55 38.43
灵寿县 114.37 38.3
高邑县 114.6 37.6
深泽县 115.2 38.18
赞皇县 114.38 37.67
无极县 114.97 38.18
平山县 114.2 38.25
元氏县 114.52 37.75
赵县 114.77 37.75
辛集市 115.22 37.92
藁城市 114.83 38.03
晋州市 115.03 38.03
新乐市 114.68 38.35
鹿泉市 114.3 38.08
唐山市 118.2 39.63
路南区 118.17 39.63
路北区 118.22 39.63
古冶区 118.42 39.73
开平区 118.27 39.68
丰南区 118.1 39.57
丰润区 118.17 39.83
滦县 118.7 39.75
滦南县 118.68 39.5
乐亭县 118.9 39.42
迁西县 118.32 40.15
玉田县 117.73 39.88
唐海县 118.45 39.27
遵化市 117.95 40.18
迁安市 118.7 40.02
秦皇岛市 119.6 39.93
海港区 119.6 39.93
山海关区 119.77 40.0
北戴河区 119.48 39.83
青龙满族自治县 118.95 40.4
昌黎县 119.17 39.7
抚宁县 119.23 39.88
卢龙县 118.87 39.88
邯郸市 114.48 36.62
邯山区 114.48 36.6
丛台区 114.48 36.63
复兴区 114.45 36.63
峰峰矿区 114.2 36.42
邯郸县 114.53 36.6
临漳县 114.62 36.35
成安县 114.68 36.43
大名县 115.15 36.28
涉县 113.67 36.57
磁县 114.37 36.35
肥乡县 114.8 36.55
永年县 114.48 36.78
邱县 115.17 36.82
鸡泽县 114.87 36.92
广平县 114.93 36.48
馆陶县 115.3 36.53
魏县 114.93 36.37
曲周县 114.95 36.78
武安市 114.2 36.7
邢台市 114.48 37.07
桥东区 114.5 38.05
桥东区 114.9 40.78
桥东区 114.5 37.07
桥西区 114.87 40.83
桥西区 114.47 38.03
桥西区 114.47 37.05
邢台县 114.5 37.08
临城县 114.5 37.43
内丘县 114.52 37.3
柏乡县 114.68 37.5
隆尧县 114.77 37.35
任县 114.68 37.13
南和县 114.68 37.0
宁晋县 114.92 37.62
巨鹿县 115.03 37.22
新河县 115.25 37.53
广宗县 115.15 37.07
平乡县 115.03 37.07
威县 115.25 36.98
清河县 115.67 37.07
临西县 115.5 36.85
南宫市 115.38 37.35
沙河市 114.5 36.85
保定市 115.47 38.87
新市区 115.45 38.87
北市区 115.48 38.87
南市区 115.5 38.85
满城县 115.32 38.95
清苑县 115.48 38.77
涞水县 115.72 39.4
阜平县 114.18 38.85
徐水县 115.65 39.02
定兴县 115.77 39.27
唐县 114.98 38.75
高阳县 115.78 38.68
容城县 115.87 39.05
涞源县 114.68 39.35
望都县 115.15 38.72
安新县 115.93 38.92
易县 115.5 39.35
曲阳县 114.7 38.62
蠡县 115.57 38.48
顺平县 115.13 38.83
博野县 115.47 38.45
雄县 116.1 38.98
涿州市 115.97 39.48
定州市 114.97 38.52
安国市 115.32 38.42
高碑店市 115.85 39.33
张家口市 114.88 40.82
桥东区 114.5 38.05
桥东区 114.9 40.78
桥东区 114.5 37.07
桥西区 114.87 40.83
桥西区 114.47 38.03
桥西区 114.47 37.05
宣化区 115.05 40.6
下花园区 115.27 40.48
宣化县 115.02 40.55
张北县 114.7 41.15
康保县 114.62 41.85
沽源县 115.7 41.67
尚义县 113.97 41.08
蔚县 114.57 39.85
阳原县 114.17 40.12
怀安县 114.42 40.67
万全县 114.72 40.75
怀来县 115.52 40.4
涿鹿县 115.22 40.38
赤城县 115.83 40.92
崇礼县 115.27 40.97
承德市 117.93 40.97
双桥区 117.93 40.97
双滦区 117.78 40.95
鹰手营子矿区 117.65 40.55
承德县 118.17 40.77
兴隆县 117.52 40.43
平泉县 118.68 41.0
滦平县 117.33 40.93
隆化县 117.72 41.32
丰宁满族自治县 116.65 41.2
宽城满族自治县 118.48 40.6
围场满族蒙古族自治县 117.75 41.93
沧州市 116.83 38.3
新华区 114.47 38.05
新华区 116.87 38.32
运河区 116.85 38.32
沧县 116.87 38.3
青县 116.82 38.58
东光县 116.53 37.88
海兴县 117.48 38.13
盐山县 117.22 38.05
肃宁县 115.83 38.43
南皮县 116.7 38.03
吴桥县 116.38 37.62
献县 116.12 38.18
孟村回族自治县 117.1 38.07
泊头市 116.57 38.07
任丘市 116.1 38.72
黄骅市 117.35 38.37
河间市 116.08 38.43
廊坊市 116.7 39.52
安次区 116.68 39.52
广阳区 116.72 39.53
固安县 116.3 39.43
永清县 116.5 39.32
香河县 117.0 39.77
大城县 116.63 38.7
文安县 116.47 38.87
大厂回族自治县 116.98 39.88
霸州市 116.4 39.1
三河市 117.07 39.98
衡水市 115.68 37.73
桃城区 115.68 37.73
枣强县 115.72 37.52
武邑县 115.88 37.82
武强县 115.98 38.03
饶阳县 115.73 38.23
安平县 115.52 38.23
故城县 115.97 37.35
景县 116.27 37.7
阜城县 116.15 37.87
冀州市 115.57 37.57
深州市 115.55 38.02
太原市 112.55 37.87
小店区 112.57 37.73
迎泽区 112.57 37.87
杏花岭区 112.57 37.88
尖草坪区 112.48 37.93
万柏林区 112.52 37.87
晋源区 112.48 37.73
清徐县 112.35 37.6
阳曲县 112.67 38.07
娄烦县 111.78 38.07
古交市 112.17 37.92
大同市 113.3 40.08
城区 113.28 40.08
城区 113.6 37.85
城区 113.12 36.22
城区 112.83 35.5
矿区 113.17 40.03
矿区 113.57 37.87
南郊区 113.13 40.0
新荣区 113.15 40.27
阳高县 113.75 40.37
天镇县 114.08 40.42
广灵县 114.28 39.77
灵丘县 114.23 39.43
浑源县 113.68 39.7
左云县 112.7 40.0
大同县 113.6 40.03
阳泉市 113.57 37.85
城区 113.28 40.08
城区 113.6 37.85
城区 113.12 36.22
城区 112.83 35.5
矿区 113.17 40.03
矿区 113.57 37.87
郊区 113.58 37.93
郊区 113.12 36.2
平定县 113.62 37.8
盂县 113.4 38.08
长治市 113.12 36.2
城区 113.28 40.08
城区 113.6 37.85
城区 113.12 36.22
城区 112.83 35.5
郊区 113.58 37.93
郊区 113.12 36.2
长治县 113.03 36.05
襄垣县 113.05 36.53
屯留县 112.88 36.32
平顺县 113.43 36.2
黎城县 113.38 36.5
壶关县 113.2 36.12
长子县 112.87 36.12
武乡县 112.85 36.83
沁县 112.7 36.75
沁源县 112.33 36.5
潞城市 113.22 36.33
晋城市 112.83 35.5
城区 113.28 40.08
城区 113.6 37.85
城区 113.12 36.22
城区 112.83 35.5
沁水县 112.18 35.68
阳城县 112.42 35.48
陵川县 113.27 35.78
泽州县 112.83 35.5
高平市 112.92 35.8
朔州市 112.43 39.33
朔城区 112.43 39.33
山阴县 112.82 39.52
应县 113.18 39.55
右玉县 112.47 39.98
怀仁县 113.08 39.83
晋中市 112.75 37.68
榆次区 112.75 37.68
榆社县 112.97 37.07
左权县 113.37 37.07
和顺县 113.57 37.33
昔阳县 113.7 37.62
寿阳县 113.18 37.88
太谷县 112.55 37.42
祁县 112.33 37.35
平遥县 112.17 37.18
灵石县 111.77 36.85
介休市 111.92 37.03
运城市 110.98 35.02
盐湖区 110.98 35.02
临猗县 110.77 35.15
万荣县 110.83 35.42
闻喜县 111.22 35.35
稷山县 110.97 35.6
新绛县 111.22 35.62
绛县 111.57 35.48
垣曲县 111.67 35.3
夏县 111.22 35.15
平陆县 111.22 34.83
芮城县 110.68 34.7
河津市 110.7 35.6
忻州市 112.73 38.42
忻府区 112.73 38.42
定襄县 112.95 38.48
五台县 113.25 38.73
代县 112.95 39.07
繁峙县 113.25 39.18
宁武县 112.3 39.0
静乐县 111.93 38.37
神池县 112.2 39.08
五寨县 111.85 38.9
岢岚县 111.57 38.7
河曲县 111.13 39.38
偏关县 111.5 39.43
原平市 112.7 38.73
临汾市 111.52 36.08
尧都区 111.52 36.08
曲沃县 111.47 35.63
翼城县 111.72 35.73
襄汾县 111.43 35.88
洪洞县 111.67 36.25
古县 111.92 36.27
安泽县 112.25 36.15
浮山县 111.83 35.97
吉县 110.68 36.1
乡宁县 110.83 35.97
大宁县 110.75 36.47
隰县 110.93 36.7
永和县 110.63 36.77
蒲县 111.08 36.42
汾西县 111.57 36.65
侯马市 111.35 35.62
霍州市 111.72 36.57
吕梁市 111.13 37.52
离石区 111.13 37.52
文水县 112.02 37.43
交城县 112.15 37.55
兴县 111.12 38.47
临县 110.98 37.95
柳林县 110.9 37.43
石楼县 110.83 37.0
岚县 111.67 38.28
方山县 111.23 37.88
中阳县 111.18 37.33
交口县 111.2 36.97
孝义市 111.77 37.15
汾阳市 111.78 37.27
呼和浩特市 111.73 40.83
新城区 111.65 40.87
回民区 111.6 40.8
玉泉区 111.67 40.75
赛罕区 111.68 40.8
土默特左旗 111.13 40.72
托克托县 111.18 40.27
和林格尔县 111.82 40.38
清水河县 111.68 39.92
武川县 111.45 41.08
包头市 109.83 40.65
东河区 110.02 40.58
昆都仑区 109.83 40.63
青山区 109.9 40.65
石拐区 110.27 40.68
九原区 109.97 40.6
土默特右旗 110.52 40.57
固阳县 110.05 41.03
达尔罕茂明安联合旗 110.43 41.7
乌海市 106.82 39.67
海勃湾区 106.83 39.7
海南区 106.88 39.43
乌达区 106.7 39.5
赤峰市 118.92 42.27
红山区 118.97 42.28
元宝山区 119.28 42.03
松山区 118.92 42.28
阿鲁科尔沁旗 120.08 43.88
巴林左旗 119.38 43.98
巴林右旗 118.67 43.52
林西县 118.05 43.6
克什克腾旗 117.53 43.25
翁牛特旗 119.02 42.93
喀喇沁旗 118.7 41.93
宁城县 119.33 41.6
敖汉旗 119.9 42.28
通辽市 122.27 43.62
科尔沁区 122.27 43.62
科尔沁左翼中旗 123.32 44.13
科尔沁左翼后旗 122.35 42.95
开鲁县 121.3 43.6
库伦旗 121.77 42.73
奈曼旗 120.65 42.85
扎鲁特旗 120.92 44.55
霍林郭勒市 119.65 45.53
鄂尔多斯市 109.8 39.62
东胜区 110.0 39.82
达拉特旗 110.03 40.4
准格尔旗 111.23 39.87
鄂托克前旗 107.48 38.18
鄂托克旗 107.98 39.1
杭锦旗 108.72 39.83
乌审旗 108.85 38.6
伊金霍洛旗 109.73 39.57
呼伦贝尔市 119.77 49.22
海拉尔区 119.77 49.22
阿荣旗 123.47 48.13
鄂伦春自治旗 123.72 50.58
鄂温克族自治旗 119.75 49.13
陈巴尔虎旗 119.43 49.32
新巴尔虎左旗 118.27 48.22
新巴尔虎右旗 116.82 48.67
满洲里市 117.45 49.58
牙克石市 120.73 49.28
扎兰屯市 122.75 47.98
额尔古纳市 120.18 50.23
根河市 121.52 50.78
巴彦淖尔市 107.42 40.75
临河区 107.4 40.75
五原县 108.27 41.1
磴口县 107.02 40.33
乌拉特前旗 108.65 40.72
乌拉特中旗 108.52 41.57
乌拉特后旗 107.07 41.1
杭锦后旗 107.15 40.88
乌兰察布市 113.12 40.98
集宁区 113.1 41.03
卓资县 112.57 40.9
化德县 114.0 41.9
商都县 113.53 41.55
兴和县 113.88 40.88
凉城县 112.48 40.53
察哈尔右翼前旗 113.22 40.78
察哈尔右翼中旗 112.63 41.27
察哈尔右翼后旗 113.18 41.45
四子王旗 111.7 41.52
丰镇市 113.15 40.43
兴安盟 122.05 46.08
乌兰浩特市 122.05 46.08
阿尔山市 119.93 47.18
科尔沁右翼前旗 121.92 46.07
科尔沁右翼中旗 121.47 45.05<
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
