問題タブ [closest-points]

これを解決する方法については、ウィキペディアのエントリを見ています。それは5つのステップをリストします

1.x座標に沿ってポイントを並べ替える

2.点のセットを垂直線 x = xmid で 2 つの等しいサイズのサブセットに分割します。

3.左部分集合と右部分集合で再帰的に問題を解きます。これにより、左側と右側の最小距離 dLmin と dRmin がそれぞれ得られます。

4.1 つの点が分割垂直線の左側にあり、2 番目の点が右側にある点のペアの間で最小距離 dLRmin を見つけます。

5.最終的な答えは、dLmin、dRmin、dLRmin の最小値です。

4番目のステップが理解できません。線の右側の点と比較する線の左側の点を選択するにはどうすればよいですか。すべてのポイントを比較する必要はないことは承知していますが、比較するポイントをどのように選択すればよいかわかりません。リンクを送信しないでください。検索し、多数のリンクにアクセスしましたが、ステップ 4 を理解するのに役立つ説明が見つかりませんでした。

ありがとう

アーロン

こんにちは、データベースに点群があります (Sql サーバー 2008 空間)。それは約600万件のレコードです。id、value、geom の 3 つの列があります。入力緯度経度で「値」を取得する最も最適化された方法は何ですか??

SQL Server 2008 での空間クエリは初めてです。geom 列のポイントを見つける簡単な例を投稿して、入力緯度から一致または最も近いものを投稿できますか?

ありがとう

SQL Server 2008 R2 Express データベースには約 7,500 万のレコードがあります。それぞれは、ある値に対応する緯度経度です。テーブルには geography 列があります。特定の緯度経度 (ポイント) の最近傍を見つけようとしています。空間インデックスを使用したクエリが既にあります。ただし、レコードがデータベース内のどこにあるか (たとえば、第 1 四半期か前四半期か) によっては、クエリが最近傍を見つけるのに約 3 秒から 30 秒かかる場合があります。クエリまたは空間インデックスを最適化することで、これを最適化してより高速な結果を得ることができると思います。現在、デフォルト設定でいくつかの空間インデックスを適用しています。これが私のテーブルとクエリの外観です。

私が使用している空間インデックス:

私が使用しているクエリは次のとおりです。

これは、私のデータベースの緯度経度のサンプルです。精度と密度のアイデアを提供します。7,000 万件のレコードはすべて 1 つの都市のものです (Lidar データ)

このクエリでは、上記の結果が得られますが、パフォーマンスを可能な限り改善したいと考えています。私の推測では、空間インデックスのデフォルト値を微調整することで、パフォーマンスを改善できる可能性があります。何か手がかりはありますか？

バッファを 10 から 1000 まで変えてみましたが、結果はほぼ同じでした。

また、パフォーマンスを改善するためのその他の提案も歓迎します。

私が現在使用しているシステムは次のとおりです。

誰かがソートされていない共線点の最短距離のペアを見つけるアルゴリズムを提案できますか?

2Dで最も近い点のペアを実行し、線に適用するだけで、O(nlogn)でこれを行う1つのソリューションがあります。しかし、これをより効率的に行うことはできますか?

雲の中の3点の最も近いグループを見つけるための既知の効率的なアルゴリズムはありますか?

これは、最も近い点のペアの問題に似ていますが、2 点ではなく 3 点を探しています。

編集
「最も近い」の定義は、アルゴリズムの複雑さに影響します。ジャックが指摘したように、三角形の最小面積を見つけることは3和が難しく、いずれにしても私のアプリケーションにはあまり適していません。

最小境界線(つまり |AB|+|AC|+|BC|) 三角形または同様のもの (最小 |AB|²+|AC|²+|BC|² など)を見つけるためのより効率的なアルゴリズムがあることを願っています。 ) 他の場所に 3 つの同一線上の点が存在しても結果に影響しないため、これを 3 サム ハードにする理由はわかりません。

注: 私のポイントは 8 次元であるため、より少ない次元に制限されているアルゴリズムは適切ではありません。

このアルゴリズムの単純なバージョンを実装しようとしていますが、二次アルゴリズムよりもうまく機能します。私の考えは基本的に、ポイントを x 座標のみでソートし、そこから解決しようとすることです。ポイントの配列を x 座標で並べ替えたら、配列を反復処理し、基本的に、最初に取得した 2 つのポイントよりも距離が大きいポイントをスキップします。

たとえば、私の currentminDist = x;

見ている 2 つの点のペアの距離が x より大きい場合 (その x 座標距離のみ)、その点を無視して、配列内でその点を通り過ぎます。

私はアイデアを持っていますが、これを実際に実装する方法に固執しています（特に条件部分）。x座標に基づいて2点間の距離を返す関数があります。

距離が遠すぎる場合にポイントを無視し、各 i の最も近いポイントの回答を含む配列に入力したいので、ループの条件を実際に記述する方法について混乱しています (i は現在のポイントです)。見ています）。

ヒントや指示は大歓迎です。私はアルゴリズムのコーディングにあまり詳しくないので、かなりイライラします。

ここに私のコードの一部があります:

distbyX は​​、2 点間の距離を返すだけの関数です。

ありがとう！

時系列 (unix タイムスタンプ) を含む numpy 配列が 2 つあります。差がしきい値内にあるタイムスタンプのペア(各配列から 1 つ)を見つけ
たいです。

これを実現するには、2 つの時系列データを 2 つの配列に配置して、各インデックスが最も近いペアを持つようにする必要があります。（配列内の2つのタイムスタンプが別の配列内の別のタイムスタンプに等しく近い場合、ペアの数が実際の値よりも重要であるため、どちらを選択してもかまいません。）

したがって、アラインされたデータ セットには、同じサイズの2 つの配列と、空のデータで埋められた小さい方の配列があります。

timeseriesパッケージとalign関数を使用することを考えていました。しかし、時系列である私のデータに整列を使用する方法がわかり
ません。

例では、2 つの時系列配列を考えます。

出力サンプル:

の場合ts2[2] (1311257033.0)、その最も近いペアはts1[4] (1311251330.0)、差が5703.0で、これは 内にthresholdあり、最小であるためです。ts2[2]とts1[4] はすでにペアになっているので、他の計算から除外する必要があります。

そのようなペアが見つかるはずなので、出力配列は実際の配列よりも長くなる可能性があります

abs(ts1[0]-ts2[0]) = 16060
abs(ts1[0]-ts2[1]) = 15820 //ペア
abs(ts1[0]-ts2[2]) = 14212
abs(ts1[0 ]-ts2[3]) = 14273
abs(ts1[0]-ts2[4]) = 38444

---

abs(ts1[1]-ts2[0]) = 16121
abs(ts1[1]-ts2[1]) = 15881
abs(ts1[1]-ts2[2]) = 14151
abs(ts1[1]-ts2 [3]) = 14212
abs(ts1[1]-ts2[4]) = 38383

---

abs(ts1[2]-ts2[0]) = 17264
abs(ts1[2]-ts2[1]) = 17024
abs(ts1[2]-ts2[2]) = 13008
abs(ts1[2]-ts2 [3]) = 13069
abs(ts1[2]-ts2[4]) = 37240

---

abs(ts1[3]-ts2[0]) = 17384
abs(ts1[3]-ts2[1]) = 17144
abs(ts1[3]-ts2[2]) = 12888
abs(ts1[3]-ts2 [3]) = 17144
abs(ts1[3]-ts2[4]) = 37120

---

abs(ts1[4]-ts2[0]) = 24569
abs(ts1[4]-ts2[1]) = 24329
abs(ts1[4]-ts2[2]) = 5703 //ペア
abs( ts1[4] ]-ts2[3]) = 5764
abs(ts1[4]-ts2[4]) = 29935

---

abs(ts1[5]-ts2[0]) = 55794
abs(ts1[5]-ts2[1]) = 55554
abs(ts1[5]-ts2[2]) = 25522
abs(ts1[5]-ts2 [3]) = 25461
abs(ts1[5]-ts2[4]) = 1290 //ペア

---

abs(ts1[6]-ts2[0]) = 55853
abs(ts1[6]-ts2[1]) = 55613
abs(ts1[6]-ts2[2]) = 25581
abs(ts1[6]-ts2 [3]) = 25520
abs(ts1[6]-ts2[4]) = 1349

---

したがって、ペアは次のとおりです: ( ts1[0],ts2[1]), (ts1[4],ts2[2]), (ts1[5],ts2[4])
残りの要素はnullペアとして持つ必要があり
ます 最後の 2 つの配列のサイズは 9 になります。

この質問が明確かどうか教えてください。

2 つの uiviewimages が交差しているかどうかを判断するにはどうすればよいですか? 自動スナップ機能を実行したい。小さな画像が大きな画像と交差するか、それに近い場合（距離<= xと言います）、小さな画像が交差する点で大きな画像に自動的にスナップ（接続）します。

これに対する最善の解決策は何だろうと思っています。マウスがクリックされたときに、Web ページ上の最も近いハイパーリンクを返して表示します。

この例には 3 つDIVの があります。それぞれにハイパーリンクが含まれています。.のない別のハイパーリンク (ハイパーリンク D) もありDIVます。そして、赤い点がマウスクリックだとしましょう。

例えば

私が考えることができる解決策は、次のようにしてすべてのリンクを反復処理することです

次に、距離方程式 を使用して距離を計算しc^2 = a^2 + b^2ます。

このアプローチは確かに O(N) 時間の複雑さを要します。ここで、N は私たちが持っているリンクの数です。もっとうまくやれるか？

私は2次元配列を持っています:

最初の 2 つの要素MyArray[0]とMyArray[1]は、点のX座標とY座標です。

配列内のすべての要素について、半径X単位で最も近い 1 つの要素を返す最も簡単な方法を見つけたいと思います。これは 2D 空間にあると仮定しています。

この例で言いましょうX = 6。

すべての要素を他のすべての要素と比較することで問題を解決しましたが、リストが 22k ポイントの長さの場合、これには 15 分ほどかかります。最終的には、約 3000 万ポイントのリストでこれを実行したいと考えています。

Kd ツリーについて読んで、基本的な概念は理解しましたが、それらをスクリプト化する方法を理解するのに苦労しました。