問題タブ [closest-points]

セット A とセット B の 2 セットのノードがあります。各セットのサイズは 25,000 です。

パーセンテージ (20% としましょう) が与えられます。セット A のノードの 20% がセット B の任意のノードの距離内に収まるような最小距離を見つける必要があります。

解決：

セット B のノードに最も近いセット A の 20% を見つけます。答えは、セット B のノードから最も遠い 20% のノードです。

ブルート フォース ソリューション:

これは機能しますが、非常に時間がかかります。(O(n^2 + Sort) かな？)

どうすればこれをスピードアップできますか? できればO(n)を打ちたいです。

複数のターゲットに近いソート済み配列 A内のすべての値インデックスを見つける良い方法はありますか? numpy.searchsorted() を使用すると、複数のターゲットに近いインデックスを効率的に見つけることができます: 最も近い値を見つけて、Python で配列のインデックスを返す ただし、配列 A に繰り返し値がある場合、このメソッドはインデックスの 1 つだけを返します。すべての可能なインデックスではなく。たとえば、次のような配列です。

idx = [2, 11] を返しますが、[[2,3],11] を返したいのですが、idx をループして [A==A[idx[0]] のようなブール値のインデックスを取得するだけです。 ],A==A[idx[1]],...] ただし、ターゲット配列が非常に大きい場合、これは非常に非効率的です。

1 つのことは、最初に numpy.unique() を使用して配列の一意のセットを見つけることができたことです。すべて同じ値を見つける。次に、その一意の配列で searchsorted() を実行すると、時間を節約できます。次に、このインデックスを使用して、すべて同じ値を見つけることができます。

以下に例を示します。

len(ua)<<len(A)Aで最も近いものを直接見つけようとするよりもはるかに効率的だと思います。代替の unique() を作成して、A の各一意の値のインデックス リストを取得できる場合 ([[インデックスの値は ua[0]]、[インデックスの値は ua[2]]...])。それははるかに効率的です：

しかし、 unique2()が期待することを実行できるものがあるかどうかはわかりません。searchsorted 以外のより効率的な方法で同じ結果を得ることができる、まったく異なるアルゴリズムが他にもあるかもしれません。

簡単にするために、A がソートされていると仮定します。ソートされていない配列 A の場合、常に最初に argsort できます。

これを行うためのより効率的な方法を提供できる人はいますか?

ありがとう！

最も近いペア コードを探していたところ、qsort() ライブラリ関数を使用しているコードが見つかりました。基本的に、比較パラメーターがどのように機能するかという概念がわかりませんでした。この特定のコードに関連する説明は、より高く評価されます。ありがとう。

MyPointポイントとポリゴンMyPolygonの間の距離を見つけることができます

明らかに、実際の最も近い点MyPolygonはどこかで計算する必要があります。その最も近いポイントを取得する簡単な方法はありますか? Boost Documentation には何も見つかりません。他の人にもその問題があったと確信しています。

点が点在する 3D マトリックスがあります (Nx4 マトリックス、xyz データ)。私の目的は、最も近いポイントをリンクし、各チェーンを Kx4 配列 (x、y、z、データ) に登録することです。K はチェーンの長さです。チェーンの総数はポイントによって異なります...特定の点は、これらの線が上向き (z+) にのみ移動することです。同じ z 上のポイントをリンクしたり、下向きにしたりしたくありません。

私はこれまでさまざまな戦略を試してきました.1つは別の配列形状です(Mx4xNz - 基本的に、値はすべて2次元行列ではなく、zごとに積み上げられたことを意味します):[delaunay/nearestneighborを使用して、ある程度の進行後に編集]

1. レベル Zn で点をピック
2. レベル Zn+1 に移動し、delaunayTriangulation とnearestNeighbor を使用して座標 x、y の範囲内で最も近い点を探します
3. ポイントをベクトルに登録する

（Nx4マトリックスでnearestNeighborを使用する他の可能性があると思いますが、検索を上向きに「指示」して連続するポイントをチェーンする方法を考えられません...）

私は次の問題を抱えています：上向きの最近点の発見はうまくいくようですが、一方向のみです!!

リンクが機能しない:

リンク作品：

ループ中に警告が表示されます: 警告: 重複データ ポイントが検出され、削除されました。Triangulation インデックスは、delaunayTriangulation プロパティ X の一意のポイント セットに関して定義されます。

Lign=zeros(max_iter,4,s);

i = 1:s;

終わり

なぜこれが起こるのか誰にも考えがありますか？