問題: 2D 平面に点の集合があるとします。この点のセットが通常のグリッド上にあるかどうか (それらが 2D ラティスのサブセットである場合) を知りたいです。これを行う方法についていくつかのアイデアが欲しいです。
今のところ、これらの点が軸に沿った長方形のグリッドを形成しているかどうか (下にある格子が x 軸と y 軸に沿った長方形である) と、それが完全な長方形 (格子には穴のない長方形の境界があります)。N は数十万または数百万になる可能性があるため、すべてのソリューションは非常に効率的でなければなりません (O(N^2) よりも優れている)。
コンテキスト:任意にサンプリングされたベクトル フィールドに対して機能する 2D ベクトル フィールド プロット ジェネレーターを作成しました。サンプリングが通常のグリッド上にある場合、プロットを生成するためのより単純で効率的な補間スキームがあります。この特殊なケースをいつ使用できるか知りたいです。特別なケースは、実行する価値があるほど十分に優れています。プログラムはCで書かれています。
これはばかげているかもしれませんが、ポイントが通常のグリッド上にある場合、座標のフーリエ変換のピークはすべてグリッド解像度の正確な倍数ではないでしょうか? X座標とY座標を個別にフーリエ変換できます。グリッドに穴がない場合、FT はデルタ関数になると思います。FFT は O(nlog(n)) です。
psこれをコメントとして残していたでしょうが、私の担当者は低すぎます..
これがあなたが求めているものであるかどうかはよくわかりませんが、平面上の2Dポイントのコレクションの場合、いつでも長方形のグリッドにフィットさせることができます（とにかくポイントの精度まで）、問題はそれらがフィットするグリッドにある可能性がありますポイントがあまりにも少なく設定されているため、アルゴリズムにメリットがありません。
点のセットに適合する長方形のグリッドを見つけるには、基本的にすべてのx座標のGCDとxmin、yminを原点とするすべてのy座標のGCDを見つける必要があります。これはO（n（log n）^ 2）である必要があります。 ） おもう。
ただし、このグリッドがまばらすぎるかどうかをどのように判断するかは明確ではありません。
すべてのポイントがグリッド上の交差点からのみ発生する場合は、ポイントのセットのハフ変換が役立つ場合があります。2つの相互に垂直な線のセットが最も頻繁に発生し（つまり、すべて90度離れたシータの4つの値にピークがあります）、ガンマ空間に繰り返しピークがある場合は、グリッドがあります。そうでなければそうではありません。
グリッドが方向Or(0 ～ 90 度) と解像度によって定義されているとしますRes。(Or, Res)グリッドがポイントにくっついているかどうかを評価するコスト関数を計算できます。たとえば、各ポイントからグリッドの最も近いポイントまでの平均距離を計算できます。
問題は、コスト関数を最小化する (Or, Res) ペアを見つけることです。検索スペースを狭めて を改善するために、「良い」候補グリッドをテストするヒューリスティックを使用できます。
このアプローチは、ジルによって提案されたハフ変換で使用されるものと同じです。(Or, Res) 空間は、ハフのガンマ空間に匹敵します。