V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
marshluca
V2EX  ›  数学

关于周边搜索的计算问题

  •  
  •   marshluca · 2010-11-11 10:23:41 +08:00 · 6597 次点击
    这是一个创建于 4877 天前的主题,其中的信息可能已经有所发展或是发生改变。
    问题背景:地球上有很多形形色色的点,而这些所有的点也近似上构成了这个地球集R

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

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

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

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

    现在的问题是:

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

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

    算法的事情好晦涩……对“很多实际周边搜索都是基于这个地球集R计算的”感到很惊讶。
    我胡乱插嘴一下:不能直接按照点的经纬来分解集合吗?比如按照经纬度的高位排序之后不就可以很自然地把点分成一组一组了么……然后查到经纬度接近的组就好了。忽略我的胡扯……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5627 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 06:33 · PVG 14:33 · LAX 23:33 · JFK 02:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.