<分区>
我问这个是因为我确定以前有人提出过但不确定如何调用它。 我需要一种有效的方法来搜索和存储度量空间中的某个点。具体来说，我需要查找空间和时间中某些点的天气。我有一个 API 可以做到这一点，但如果我过去已经查询过距新点几英寸远的点和几秒钟之前的点，我不想再发出请求，因为那里的天气会一样。
所以当我收到一个新点时，我需要问 - 我在缓存中是否有一个“足够近”的点(与新点的距离低于阈值)？ 如果我这样做 - 获取与该点相关的数据。否则，缓存新点。 这可以使用串行检查轻松完成，但我对更有效地完成它的方法很感兴趣。
谢谢!
最佳答案
假设你的阈值是t，你可以将你的搜索空间分割成一个网格，
单元格的宽度和高度为 t。
每个单元格都会有一个位于其中的点列表。
现在，当给定一个新点时，您计算它落入哪个单元格， 假设这是单元格 [i,j]，你检查这个单元格和它的所有邻居 (即总共 9 个单元格)，它们是否包含任何点，如果包含， 这些是您接近阈值点的候选对象。 您现在将计算所有这些的距离。
由于单元格的宽度为 t，高度为 t，因此所有点的距离
躺在任何其他单元格中至少是 t。
您可以将网格单元存储在 TreeMap 中，比较器基于 [i,j] 对。 (您只存储其中至少有一个点的单元格)。
关于java - 有效地搜索 "close point"，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20459572/