0

我收集了一堆 gps 点，现在我需要将这些点与 18000 点进行匹配。我在两个数组列表中有这些。有没有更好的搜索方式？我正在用 Java 执行此操作。

这是一个巨大的数据样本。它们包含一个额外的参数 ID1，通过它可以对一组点进行分组。

ID1     ID2     ID3      longi          lati,
2   1   1   -79.911635  39.609849,
2   1   2   -79.91151   39.60956,
2   1   3   -79.9115    39.609489,
2   1   4   -79.911496  39.609433,
3   1   1   -79.908162  39.609841,
3   1   2   -79.908447  39.610019,
4   1   1   -79.911136  39.608433,
4   1   2   -79.910961  39.608446,
4   1   3   -79.910629  39.608451,
4   1   4   -79.910064  39.608493,
4   1   5   -79.909117  39.608586,
4

2 回答 2

1

如果您正在寻找完全匹配，那么您可以将点放在一个集合中（HashSet 和 TreeSet 都可以），并找到交点：set1.intersect(set2)。您将不得不相应地实现 compare() 或 hashcode() 以及 equals() 在任何情况下，但这是简单的场景。

如果您正在寻找“比 X 更接近”，您应该使用四叉树。将所有节点放在四叉树的第一个数组列表中，然后使用此数据结构执行快速查找（每次查找可以产生 O(log N) 中的最近点，而不是蛮力方法的每次查找 O(N) ）。例如，在geotools中有一个四叉树的开源实现。

于 2012-09-21T20:18:52.987 回答
1

您还可以使用称为RTREE. 它通常比quadtree.

例如，本文发现它在 Oracle 数据库中的速度提高了 2 -3 倍：http: //pdf.aminer.org/000/300/406/incorporating_updates_in_domain_indexes_experiences_with_oracle_spatial_r.pdf

Java Topology Suite (JTS) 包含一个很好的实现rtree： http: //www.vividsolutions.com/jts/javadoc/com/vividsolutions/jts/index/strtree/STRtree.html

请注意，它GeoTools是基于 JTS 的，因此它rtree的空间索引功能中可能还隐藏着一个：http ://docs.geotools.org/latest/userguide/library/main/collection.html

于 2012-09-28T12:24:54.547 回答