0

デカルト平面のポイントのリストとテスト ポイントがあります。テスト ポイントに最も近い 3 つのポイントのリスト インデックスを検索します。これらのインデックスを見つけるより良い方法は何ですか? ツアーの返信ありがとうございます。

=== 編集 ===

C++で解決策を見つけました。まず、ベクトルを作成します。

typedef struct
{
  int iIndex;
  double dSqrDistance;
} IndexedDistance;

std::vector<IndexedDistance> xDistanceVector;

そして、その要素をソートする関数

bool compareIndexedDistance(IndexedDistance xD1, IndexedDistance xD2)
{
  return (xD1.dSqrDistance < xD2.dSqrDistance);
}

次に、ループですべての距離を計算し、並べ替えて、最後に最初の 3 つの要素を取得します。

IndexedDistance xDistanceElement;
for (int i = 0; i < xPointList.size(); i++)
{
  dSqrDistance = xPointList.at(i).sqrDistance(xTestPoint);
  xDistanceElement.iIndex = i;
  xDistanceElement.dSqrDistance = dSqrDistance;
  xDistanceVector.push_back(xDistanceElement);
}

std::sort(xDistanceVector.begin(), xDistanceVector.end(), compareIndexedDistance);
xDistanceVector.resize(3);

このようにして、私は必要なものを見つけました。それが最善の方法かどうかはわかりませんが、うまくいくようです。

4

1 に答える 1

0

バイナリ スペース パーティショニングは、O(log n * log n) のアルゴリズムの複雑さを提供する場合があります。

  1. ポイント セットの境界を決定します。無限ポイントと最高ポイントは、セット内のすべてのポイントを含む軸に沿った正方形を提供します。
  2. 任意の軸で境界正方形を 2 つに分割します。各正方形に含まれる点の個別のリストを作成します。各境界正方形を親正方形にリンクします。
  3. 包含ポイントの対応するリストが十分に小さくなり、徹底的な検索を利用できるようになるまで、境界正方形の分割 (ステップ 2) を繰り返します。

これで、ツリー検索を使用して、関心のあるポイント周辺のスペースをローカライズできるようになり、距離テストの数が大幅に削減されます。

注意が必要なのは、最も近い点がそれらのいずれかにある可能性があるため、関心のある点の周りのすべての隣接境界正方形をスキャンする必要があることです。

于 2014-07-22T14:23:55.103 に答える