java - 查找距特定经纬度java距离的所有点

Question

我有一个 csv 文件，其中包含一堆经纬度坐标。我还有一个 csv 文件，其中包含特定人将站立的一堆位置。对于第二个文件中的每个点，我需要弄清楚它们是否靠近(不到 1 英里)第一个文件中的任何点。我的每个文件中大约有 500 点。

我正在尝试用Java解决这个问题，我想我会使用类似读取第一个文件并将其放入某种易于搜索的结构中的方法，这样我就不需要保留进行IO操作。我不清楚应该将点保存在什么类型的数据结构中，以便我可以轻松搜索给定点半径内的点。有人能指出我正确的方向吗？有什么方法可以组织这个，这样我就不需要进行 n^2 比较？

Answer 1

听起来您想将积分存储在 k-d tree 中基于纬度和经度。

如果我们知道我们想要某个点 (lat, lon) 的某个设定距离 D 内的所有点，那么计算纬度差 就很简单d_lat 对应于正北/正南距离的 D 单位，经度差 d_lon 对应于正北/正南距离的 D 单位东/西纬度 lat-d_lat 或 lat+d_lat 最接近极点。使用它我们执行 orthogonal range search在树中查找纬度介于 lat-d_lat 和 lat+d_lat 之间、经度介于 lon-d_lon 和 lon+d_lon 之间的点。然后，我们需要计算其中每一个的距离，并拒绝距 (lat, lon) 超过 D 的距离 - 但我们不需要进行那么多计算与没有树一样(我们最终应该只拒绝大约 1-pi/4 = 21.5% 到达此阶段的点)。

当然，如果边缘情况与您相关，您需要考虑这些情况:

• 如果您位于 180 度经度的 d_lon 范围内，则需要在树中执行两次不同的搜索(180 度的任一侧)。
• 如果 (lat, lon) 位于极点的 d_lat 纬度范围内，则只需查找 lat-d_lat 中以北/南的所有区域> 或 lat+d_lat 距离极点最远。