1

私のアプリケーション (Qt ベースのモバイル アプリケーション) は、緯度、経度、説明の形式でサーバーからデータを取得します。

後ですばやく取得できるように、このデータをデータ構造に格納する必要があります。今、私は地図を持っています。ユーザーが地図のポイントをクリックすると、そのポイントの緯度と経度が取得されます。これらの 2 つの値を使用して、データ構造をすばやくスキャンし、関連する説明を取得する必要があります。私の問題は..地図をクリックすると緯度と経度が近似値になることです（タッチデバイスなので、正確な緯度と経度を取得することはできません）ので、データ構造で線形検索を行っても見つかりませんこれらの値。また、データが多すぎると、線形検索は非常に遅くなります。

  1. lat+long+description を格納するためにどのデータ構造を使用すればよいですか (ハッシュが頭に浮かびます..しかし、long+lat を組み合わせてキーを形成する方法がわかりません)

  2. データ構造の近似検索を行うにはどうすればよいですか?

ありがとう！

4

2 に答える 2

1

問題は 2 次元のみで構成されているため、バイナリ ツリーを使用できます。各葉は最大「N」点を持つことができます (緯度、経度を点と見なします)。葉ノードのみが点を持ちます。

ポイントのデータ型

class Point
{
  float Latitude;
  float Longitude;
  string Description;
}

Internal Node (NonLeaf Node) のデータ型

class Node
{
   Float MaxLatitude;
   Float MinLatitude;
   Float MaxLongitude;
   Float MinLongitude;
}

リーフノードのデータ型

class LeafNode
{
   Point points[K]; // Array of points
}

二分木を動的に生成し、さらにポイントを挿入するとノードを分割します。ノードの高さが偶数の場合は緯度に基づいて分割し、そうでない場合は経度に基づいて分割します。

入力ポイントを検索するときに、関連するリーフ ノードを検索すると、そのリーフ ノード内のすべてのポイントが入力ポイントに最も近いポイントになります。

これはよくある問題です - http://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor

于 2011-03-25T11:31:41.770 に答える
1

探しているデータ構造はkd-treeです。本当にハッシュが必要で、小さなエラーが許容される場合は、距離ベースのハッシュのアプローチについて説明しているこの論文 (pdf)を調べることができます。

どちらが自分に適しているかを試す必要があります。私はその論文でアルゴリズムを実装しましたが、私の問題にはうまく機能しませんでした (おそらく、データポイントがあまり均等に分散されていなかったためです)。これはあなたのケースでは異なるかもしれないので、試してみる必要があります。

于 2011-03-24T12:06:46.470 に答える