这是一个创建于 5155 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题背景：地球上有很多形形色色的点，而这些所有的点也近似上构成了这个地球集R
现在的智能手机都具备定位功能 (通过GPS,蜂窝，基站等)，获取经纬度，于是可以支持周边搜索。
而现在很多实际周边搜索都是基于这个地球集R计算的，而存在的问题是：每搜索一次，都要从地球集R出发，找出周边的点，这样，当搜索比较频繁时，不属于周边的那些点都会被重复计算，带来了不必要的查询冗余，而且效率不是很高。
如果可以把这个地球集，提前按区域切分成若干个相同的面积，每一块贴上范围索引，映射成字典。
这样在每次搜索的时候，就可以直接去搜索这个范围索引所在的集合，找到了对应的范围索引，就找到了对应的区域块，也即是这个点的周边区域。
现在的问题是：
对于这么一个庞大的地球集R，如何选择切分形状（面积提前指定，比方100平方公里），才能保证：
1.每一个点都会有象跟它对应
2.切分的区域之间交集最小，以避免数据重复查询。（可能会存在一对多，也就是一个点，被切到周边的多个区域里去了）
现在的智能手机都具备定位功能 (通过GPS,蜂窝，基站等)，获取经纬度，于是可以支持周边搜索。
而现在很多实际周边搜索都是基于这个地球集R计算的，而存在的问题是：每搜索一次，都要从地球集R出发，找出周边的点，这样，当搜索比较频繁时，不属于周边的那些点都会被重复计算，带来了不必要的查询冗余，而且效率不是很高。
如果可以把这个地球集，提前按区域切分成若干个相同的面积，每一块贴上范围索引，映射成字典。
这样在每次搜索的时候，就可以直接去搜索这个范围索引所在的集合，找到了对应的范围索引，就找到了对应的区域块，也即是这个点的周边区域。
现在的问题是：
对于这么一个庞大的地球集R，如何选择切分形状（面积提前指定，比方100平方公里），才能保证：
1.每一个点都会有象跟它对应
2.切分的区域之间交集最小，以避免数据重复查询。（可能会存在一对多，也就是一个点，被切到周边的多个区域里去了）
 |
1
marshluca OP v2ex的geekers们，有没什么好的思路
|
 |
2
darkovic 2010-11-11 12:48:55 +08:00
geekers们...
|
 |
3
lianghai 2010-11-11 20:55:29 +08:00
“geekers”这说法好非主流……
算法的事情好晦涩……对“很多实际周边搜索都是基于这个地球集R计算的”感到很惊讶。 我胡乱插嘴一下：不能直接按照点的经纬来分解集合吗？比如按照经纬度的高位排序之后不就可以很自然地把点分成一组一组了么……然后查到经纬度接近的组就好了。忽略我的胡扯…… |
Select Language