关于这个问题的详细说明，但有更多限制。
这个想法是相同的，为 2 维欧几里得的 k 最近邻找到一个简单、快速的算法。如果您能找到合适的网格大小来对数据进行分区，则分桶网格似乎工作得很好。但是，如果数据不是均匀分布的，而是具有非常高和非常低密度的区域（例如，美国人口），那么没有固定的网格大小可以保证足够的邻居和效率怎么办？这种方法还能挽回吗？
如果没有，其他建议会有所帮助，但我希望答案比转移到 kd-trees 等复杂。
问问题
1399 次
2 回答
1
如果您没有太多元素，只需将每个元素与所有其他元素进行比较。这可能比您想象的要快得多；今天的机器速度很快。不幸的是，平方因子迟早会抓住你。我认为对一百万个对象进行线性搜索不会花费太长时间，因此最多可以使用 1000 个元素。使用网格，甚至条纹，可能会大大提高这个数字。
但我认为你被四叉树（kd 树的一种特定形式）困住了。您的整个地图是一个块，其中可以包含四个子块（左上、右上、左下、右下）。当一个块填充的元素多于您想要对其进行线性搜索时，将其分解为更小的元素并传输元素。（只有叶节点有元素。）在给定点的给定半径内搜索很容易。从顶部开始，如果块的一部分在该点的范围内，则以相同的方式检查它的子块（如果有的话）。如果没有，请检查其元素。
（在搜索“最近”时，请注意。方形网格表示较近的对象可能位于较远的块中。您必须在给定半径内获取所有内容，然后全部检查。如果您想要 10 个最近的对象和您的半径of 20 只捡了 5 个，你需要尝试更大的半径。你可能有一个被拒绝的项目证明在 30 之外，并认为你应该抓住它和其他一些来弥补你的 10。但是，可能有一些25 以外的项目，它们的整个街区都被拒绝了，而你想要它们。应该有更好的解决方案，但我还没有弄清楚。我只是猜测半径并将其翻倍直到我得到足够。）
四叉树很有趣。如果您可以设置数据然后访问它，那就很容易了。当您试图找出谁在什么附近时，当您的映射元素出现、消失和移动时，问题就出现了。
于 2012-07-12T17:41:29.870 回答
0
你看过这个吗？
http://www.cs.sunysb.edu/~algorith/major_section/1.4.shtml
kd-trees 实现起来非常简单，有标准的 java/c 实现。
还：
您可能想在此处发布您的问题：
于 2012-07-11T18:41:58.097 回答