关于周边搜索的计算问题

2010-11-11 10:23:41 +08:00
marshluca  marshluca
问题背景:地球上有很多形形色色的点,而这些所有的点也近似上构成了这个地球集R

现在的智能手机都具备定位功能 (通过GPS,蜂窝,基站等),获取经纬度,于是可以支持周边搜索。

而现在很多实际周边搜索都是基于这个地球集R计算的,而存在的问题是:每搜索一次,都要从地球集R出发,找出周边的点,这样,当搜索比较频繁时,不属于周边的那些点都会被重复计算,带来了不必要的查询冗余,而且效率不是很高。

如果可以把这个地球集,提前按区域切分成若干个相同的面积,每一块贴上范围索引,映射成字典。

这样在每次搜索的时候,就可以直接去搜索这个范围索引所在的集合,找到了对应的范围索引,就找到了对应的区域块,也即是这个点的周边区域。

现在的问题是:

对于这么一个庞大的地球集R,如何选择切分形状(面积提前指定,比方100平方公里),才能保证:

1.每一个点都会有象跟它对应
2.切分的区域之间交集最小,以避免数据重复查询。(可能会存在一对多,也就是一个点,被切到周边的多个区域里去了)
6915 次点击
所在节点   数学  数学
3 条回复
marshluca
marshluca
2010-11-11 10:25:58 +08:00
v2ex的geekers们,有没什么好的思路
darkovic
darkovic
2010-11-11 12:48:55 +08:00
geekers们...
lianghai
lianghai
2010-11-11 20:55:29 +08:00
“geekers”这说法好非主流……

算法的事情好晦涩……对“很多实际周边搜索都是基于这个地球集R计算的”感到很惊讶。
我胡乱插嘴一下:不能直接按照点的经纬来分解集合吗?比如按照经纬度的高位排序之后不就可以很自然地把点分成一组一组了么……然后查到经纬度接近的组就好了。忽略我的胡扯……

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/4352

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX