java - 用于获取 "in memory"地理位置的 "around me"数据结构

Question

我需要创建寻找兴趣点的方法(类)，位于给定距离内。

类似这样的事情:

Collection <Position>  getAroundMe(Position myPosition, int distInMeters); 

该方法应使用“内存数据”(而不是数据库)。

Position 类是:

Position {
    double latitude;
    double longitude;
}

我想使用 TreeSet 来存储兴趣点，但我未能为两个(纬度和经度)字段定义比较器。

请您提出建议。

评论:“内存数据”很少更新，但大约有每分钟调用 getArroundMe 方法 1000 次(目前适用于 DB)。

Answer 1

当您的位置发生变化时，您必须不断更新 map ，因此这可能不是一个选择。

方法 1

一种简单的方法可能是维护两个按经度和纬度排序的列表。当获取距当前位置 x 的位置时，您可以执行以下操作:

• 获取间隔 current.longitude +/- x 并在经度列表中查找该间隔，例如通过使用二分搜索。
• 对纬度执行相同的操作。
• 仅保留两个时间间隔中都存在的头寸。
• 根据距当前位置的距离对位置进行排序。
• 使用二分查找查找并删除距离大于 x 的所有位置。

方法 2

另一种更复杂的方法可能是四叉树，您可以在其中定义一个包含所有位置的矩形区域，将其分割为 4 个大小相等的较小矩形，继续分割，直到达到合理的级别(不要太深，因为你的方 block 将会呈指数增长)并将位置分配给它们各自的叶子方 block 。

然后，通过自上而下的检查，检查哪些叶子方 block 被边长为 x 的方框所接触，并且中心位于当前位置。执行此操作后，您将获得可能位于您位置周围直径为x的圆中的位置列表，因此您需要检查它们并删除所有距离较远的位置。结果。

方法 3

您可以尝试的另一种选择是所谓的哈希网格(参见此处的示例: http://www.gicentre.net/utils/hashgrid/ )。这样，您基本上就可以根据(粗略)位置定义一个哈希函数，即将位置截断为某个“单元大小”，并计算该较低精度位置的哈希值。您最终会发现附近的位置具有相同的哈希值，因此位于同一个虚拟单元中。由于您不想使用与单元格一样多的存储桶，因此您的哈希值最终可能会回绕，并且最终会得到每个存储桶中彼此不靠近的单元格列表。

检查位置时，您首先计算当前位置周围的圆圈将接触哪些单元格，然后在 HashMap 中查找它们。然后您将像以前一样检查这些单元格中的位置。