3

我有一个带有一堆经纬度坐标的 csv 文件。我还有一个 csv 文件，其中包含特定人将站在的一堆位置。对于第二个文件中的每个点，我需要确定它们是否靠近（1 英里以下）第一个文件中的任何点。我在每个文件中大约有 500 分。

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

4

3 回答 3

0

这就是我要做的。

按纬度顺序对两个文件中的所有点进行排序。然后同时遍历这两个列表，这样对于文件 1 中的每个点，您都会得到文件 2 中的点列表，其纬度圆在文件 1 的点的一英里范围内。您可能可以使用某处的subList方法List一路走来这里。

仍然在文件 1 中的点的上下文中，从该子列表中过滤掉经度与点 1 相差超过一英里的点。然后，您将拥有一对点，它们都在一英里的经度和一英里的纬度范围内。

对于每一对这样的对，进行精确计算，看看它们是否真的在彼此之间一英里的“真实距离”内。

于 2013-10-30T18:39:21.907 回答
0

最简单的方法是定义一个粗网格并将您的点从第一个列表分桶到网格单元中。您需要为每个点计算一个单元格“id”并根据该 id 放入一个哈希表中。一旦你有了它，你可以通过找到正确的单元格并枚举其内容（以及相邻单元格的内容）来轻松查找给定纬度/经度的附近点。诀窍是将纬度/经度转换为单元格 ID。一种方法是四舍五入纬度/经度。因此，例如，将 (47.43402067, -121.89068567) 对转换为“47_-121”字符串。这可能太粗略了，因为赤道的 1 度大约是 70 英里。您可以通过四舍五入到某个小数点来收紧它：例如“47.43_-122.89”。请注意，随着您向北或向南移动，单元格宽度会变窄。

您还可以使用 JTS Topology Suite 等库中的现有地理空间索引，从而提供更大的灵活性。

于 2013-10-31T00:26:07.287 回答
0

听起来您想根据纬度和经度将您的点存储在kd 树中。

如果我们知道我们想要某个点的某个设定距离内的所有D点(lat, lon)，那么计算对应于北/南距离单位的纬度d_lat差异D和d_lon对应于D东/西距离单位的经度差异很简单纬度lat-d_lat或lat+d_lat最接近极点。使用它，我们在树中对纬度在和之间、经度在和之间的所有点执行正交范围搜索。然后我们需要计算每一个的距离，并拒绝那些远离lat-d_latlat+d_latlon-d_lonlon+d_lonD(lat, lon)- 但是我们不需要像没有树那样做那么多的计算（我们最终应该只拒绝大约 1-pi/4 = 21.5% 的点到达这个阶段）。

当然，您需要考虑边缘情况，如果它们与您相关：

  • 如果您在d_lon180 度经度范围内，则需要在树中进行两次不同的搜索（180 度的任一侧）。
  • 如果在极点的纬度(lat, lon)范围内d_lat，只需寻找距离极点最远lat-d_lat或lat+d_lat最远的北/南的所有内容。
于 2013-10-31T12:07:10.050 回答