4

指定された幅が与えられた場合、ポイントのパス内にある、たとえば約 5,00 から座標のセットを見つけるための最良のアプローチは何でしょうか。たとえば、いくつかのウェイポイントをたどる航空機。

ルートと同じ順序で並べ替える良い方法はありますか。

私は提案のリストを作成しようとしているので、計算速度は正確さよりも重要です。

私が見てきたことから、それは簡単ではなく、質問は少し広いと思いますが、次のような提案/ポインタは大歓迎です:

  1. 緯度/経度を保存する、または球座標を使用する最良の方法
  2. 座標セットに追加のクラスタリング情報を持つ
  3. 範囲チェックを簡素化するために何らかの変換を使用できますか
  4. ポイントを注文する最良の方法は何ですか

ここでは、パスに沿って等距離にあるいくつかの点で円形/正方形のチェックを行うよりも優れたアプローチがあります。

4

4 に答える 4

2

あなたができる多くの最適化があります：

  • ポイントを固定サイズのタイルに分割して、すべてのポイントをチェックする必要がないようにします（最初に、どのタイルにいるかを判断して、他のタイルのすべてのポイントをスキップできるようにします）。

  • 各ポイントまでの距離を計算するときは、通常、ピタゴラスを使用して距離を取得します。ただし、どのポイントが最も近いかだけを知りたい場合は、平方根を省略できます。これは、コストのかかる操作です（以下のサンプルコードを参照）。

  • 緯度/経度で作業する代わりに、平らな投影法を使用するか、地球が平らであると仮定して計算された距離を概算します。短い距離（数キロメートルまで）の場合、通常は十分に正確であり、WGS84座標を使用するよりもはるかに高速で簡単です。ただし、すべての座標を変換する必要があるかもしれませんが、その事前計算により、実行時に多くのCPUサイクルを節約できます。

-

 // delphi code that would iterate through a set of points to find the index
 // of the point that is the closest to the provided x/y
 function TMatcher.GetIndexOfClosest(X,Y:Double):Integer;
 var
  i : Integer;
  Closest:Double;
  Distance:Double;
begin
  Closest:= MaxInt;
  Result := -1;
  for i:=0 to high(Points) do
  begin
    // taking the square root is not needed here!
    Distance :=Sqr(X-Points[I].X)+Sqr(Y-Points[I].Y);

    if Distance < Closest then
    begin
      Closest := Distance;
      Result := i;
    end; 
  end;
end;
于 2009-01-15T01:21:20.687 に答える
1

ポイントとパスの間の距離を計算する方法を知っていると思います。緯度/経度は単純な (x,y) データですが、単なる整数ではなく小数データです。

5,000 個のデータ ポイントは、各ポイントのパスまでの距離を計算するのにそれほど悪くはありませんが、スケーリングする場合は、四分木などのある種のリレーショナル データ構造がポイントを格納する最善の方法です。そうすれば、パスから遠く離れたポイントをすぐに破棄できます。

于 2009-01-15T00:47:04.157 に答える
1

この種の問題に直面したとき、私はPostGISを使用します。データをデータベースにインポートし、空間 SQL 関数を使用してトラック上にバッファーを作成し、バッファー内にあるポイントを選択します。自分でコーディングするよりもはるかに高速です。

PostGIS (およびPostgreSQL ) は、Windows/OSX/Linux に簡単にインストールできます。彼らには優れたドキュメントがあり、Google での簡単なセッションでほとんどの質問に対する答えが見つかります。

于 2009-01-24T04:02:11.140 に答える
0 
 Best way to store lat / long, or use spherical coordinates

何を保存しようとしていますか？パス、または探しているポイント? パスの場合、ポイントが順序付けられているため、基本的にはある種のリストです。パスを操作する方法/場合に応じて、データ構造が決まります。

座標セットに追加のクラスタリング情報を持つ

どのような情報を保存しようとしていますか? たとえば、データ構造として連結リストを選択した場合、必要な情報を含むクラス オブジェクトの連結リストを作成できます。

範囲チェックを簡素化するために何らかの変換を使用できますか

緯度/経度を UTM またはその他の座標系に変換できます。2 点間の範囲は同じままです。

ポイントを注文する最良の方法は何ですか

パスを保存している場合は、ポイント N-1 -> N -> N+1 などのように順序が重要です...

于 2009-01-15T01:06:44.507 に答える