0

集めた gps ポイントがたくさんあるので、これらのポイントを 18000 ポイントと一致させる必要があります。これらは2つの配列リストにあります。検索する良い方法はありますか？私はJavaでこれを実行しています。

これは巨大なデータのサンプルです。それらには、ポイントのセットをグループ化できるもう 1 つの追加パラメータ 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

として知られる空間インデックスを使用することもできますRTREE。通常は よりも高速ですquadtree。

たとえば、この論文では、Oracle データベースでは 2 ～ 3 倍高速であることがわかります。

Java Topology Suite (JTS) には、次の優れた実装が含まれていますrtree: http://www.vividsolutions.com/jts/javadoc/com/vividsolutions/jts/index/strtree/STRtree.html

GeoToolsJTSに基づいていることに注意してください。そのためrtree、その空間インデックス機能の内部にも潜んでいる可能性があります: http://docs.geotools.org/latest/userguide/library/main/collection.html

于 2012-09-28T12:24:54.547 に答える
1

完全一致を探している場合は、ポイントをセットに配置して (HashSet と TreeSet の両方が機能します)、交差点を見つけることができます: set1.intersect(set2). それに応じて compare() または hashcode() を実装する必要があり、いずれにせよ equals() を実装する必要がありますが、それは簡単なシナリオです。

「X より近い」を探している場合は、quadtreeを使用する必要があります。クアッドツリーの最初の配列リストにすべてのノードを配置し、このデータ構造を使用してクイック ルックアップを実行します (総当たりアプローチのルックアップごとの O(N) ではなく、ルックアップごとに O(log N) で最も近い点を生成できます)。 ）。たとえば、geotoolsには、四分木のオープンソース実装があります。

于 2012-09-21T20:18:52.987 に答える