グリッド内のランダムなポイントのコレクションが与えられた場合、それらがすべて他のポイントの固定範囲内にあることを効率的にチェックするにはどうすればよいでしょうか。つまり、グリッド内の任意のポイントに移動できる任意のポイントを 1 つ選択します。
さらに明確にするために: 1000 x 1000 のグリッドに 100 個のポイントがランダムに配置されている場合、あるポイントが隣のポイントから 100 単位以内にあり、あるポイントから別のポイントまで歩いてすべてのポイントにアクセスできることをどのように証明できますか?
私はいくつかのコードを書いていて、興味深い問題を思いつきました: 非常にまれに (これまでに一度だけ)、残りのポイントからの最大範囲を超えるポイントの島が作成されます。この問題を解決する必要がありますが、ブルート フォースでは解決できないようです。
これは Java で書かれていますが、私は疑似コードまたは C++ のどちらかが得意です。
@ joel.neelyの構築アプローチが好きですが、より均一な密度を確保したい場合は、これが機能する可能性が高くなります（ただし、全体的に均一な密度ではなく、より多くのクラスターが生成される可能性があります）。
P_jているものを選択し、以前に配置された点を特定しますP_idistance（P_i、 ）<100であるランダムな点を選択します。P_jP_iP_i）= coords（P_j）+（dx、dy）を計算します。P_i全体的に有効なグリッド内にある場合に有効です。新規および改善 ;-)
もう少し考えさせられたコメントをくれたGuillaumeとJasonSに感謝します。これにより、統計が大幅に改善された2番目の提案が作成されました。
ギヨームは、私が投稿した以前の戦略では均一な密度が失われると述べました。もちろん、彼は正しいです。なぜなら、それは本質的に元のポイントを周回する傾向がある「酔っぱらいの散歩」だからです。ただし、ポイントを均一にランダムに配置すると、「パス」要件に失敗する可能性が高くなります（すべてのポイントは、100を超えるステップのないパスで接続できます）。その状態のテストには費用がかかります。1つが通過するまで純粋にランダムな解を生成することはさらにそうです。
Jason Sはバリエーションを提供しましたが、多数のシミュレーションにわたる統計的検定により、彼のバリエーションは、最初の提案と同じようにクラスター化されたパターンを生成すると結論付けました（座標値の平均と標準偏差の調査に基づく）。
以下の改訂されたアルゴリズムは、統計が純粋に（均一な）ランダム配置の統計と非常に似ているが、パス要件を満たすように構築によって保証されているポイントセットを生成します。残念ながら、口頭で説明するよりも視覚化する方が少し簡単です。事実上、ポイントは漠然と一貫した方向（NE、SE、SW、NW）にランダムによろめき、「壁に跳ね返る」ときにのみ方向を変える必要があります。
大まかな概要は次のとおりです。
ランダムに始点を選び、水平移動を右に、垂直移動を下に設定します。
残りのポイント数（たとえば、元の仕様では99）について繰り返します。
2.1。距離が50から100の間のdxとdyをランダムに選択します。（私の試行実装では、ユークリッド距離（二乗和の平方根）を想定しましたが、「タキシカブ」距離（絶対値の合計）はさらに簡単です。コード化する。）
2.2。水平方向と垂直方向の移動に基づいて、dxとdyを前のポイントに適用します（右/下->加算、左/上->減算）。
2.3。いずれかの座標が範囲外（0未満または少なくとも1000）になった場合は、違反した境界の周囲の座標を反映し、その移動を反対方向に置き換えます。これは、4つのケース（2つの座標x 2つの境界）を意味します。
2.3.1. if x < 0, then x = -x and reverse LEFT/RIGHT horizontal travel.
2.3.2. if 1000 <= x, then x = 1999 - x and reverse LEFT/RIGHT horizontal travel.
2.3.3. if y < 0, then y = -y and reverse UP/DOWN vertical travel.
2.3.4. if 1000 <= y, then y = 1999 - y and reverse UP/DOWN vertical travel.
ステップ2.3での反射は、新しいポイントを前のポイントから100単位以内に残すことが保証されているため、パス要件が維持されることに注意してください。ただし、水平方向と垂直方向の移動の制約により、ポイントの生成は空間全体でランダムに「スイープ」され、元の純粋な「酔っぱらいの歩行」アルゴリズムよりも全体的な分散が大きくなります。
既存の点のセットを評価する限り、これは一種のユークリッド最小全域木問題のように見えます。ウィキペディアのページには、これはドロネー三角形分割のサブグラフであると記載されています。したがって、ドロネー三角形分割（前のリファレンスまたはグーグルの「計算幾何学」を参照）を計算してから、最小全域木を計算し、すべてのエッジの長さが100未満であることを確認するだけで十分だと思います。
参考文献を読むと、これはO（N log N）であるように見えます。おそらくもっと速い方法がありますが、これで十分です。
より単純な（ただしおそらく効率が低い）アルゴリズムは、次のようになります。
j<0またはの場合P[i].x - P[j].x > R、失敗して停止します。（ギャップがあり、半径Rですべてのポイントに到達することはできません）(P[i].x-P[j].x)^2 + (P[i].y-P[j].y)^2 <。R^2`の場合、ポイントP [i]は半径R内の前のポイントの1つから到達可能であり、手順4に戻ります。編集：これはO（N log N）であるはずの何かに変更される可能性がありますが、よくわかりません：
j<iP[i].xRとP[i].xの間のx座標を持つすべての点P[j]はセットYLISTにあります。私があなたの問題を正しく理解している場合、サイトのセットが与えられた場合、各サイトの最近傍 (L1 距離、つまりグリッド距離) が値 K 未満の距離にあるかどうかをテストする必要があります。
これは、一連のポイントの Delaunay 三角形分割を計算することにより、ユークリッド距離について簡単に取得できます。サイトの最近傍は、Delaunay 三角形分割におけるその近傍の 1 つです。興味深いことに、L1 距離はユークリッド距離よりも大きくなっています (係数 sqrt(2) 内)。
あなたの状態をテストする方法は次のとおりです。
このアルゴリズムは、いくつかの方法で改善できます。
簡単な考え: グリッドを 50x50 のパッチに分割し、最初のポイントを配置すると、それらがどのパッチに属しているかも記録されます。ここで、新しいポイントが他のポイントから 100 ピクセル以内にあるかどうかを確認したい場合は、パッチとその周囲の 8 ピクセルをチェックして、ポイント数が一致するかどうかを確認するだけです。
たとえば、100 個のランダム ポイントがあり、各パッチに含まれるポイントの数が含まれていることがわかっている場合、単純に合計して、実際に 100 であるかどうかを確認できます。これは、すべてのポイントに到達可能であることを意味します。
他にも方法はあると思います、難しいです。
編集: 50x50 パッチの左上点から右下点までの距離は sqrt(50^2 + 50^2) = 70 ポイントなので、おそらく小さいパッチ サイズを選択する必要があります。多分 35 か 36 で十分でしょう (50^2 = sqrt(x^2 + x^2) => x=35.355...)。
構造によって望ましい状態を強制します。乱数を描画するだけですべてのポイントを配置する代わりに、次のように座標を制限します。
初期点をランダムに配置します。
残りのポイント数 (例: 99) について繰り返します。
2.1. 前の点からある範囲 (たとえば 90) 内の x 座標をランダムに選択します。
2.2. 前の点から 100 単位以内になる y 座標の有効な範囲を計算します。
2.3. その範囲内の y 座標をランダムに選択します。
原点を完全に隠したい場合は、ポイントを座標ペアで並べ替えます。
これは、純粋なランダム性に比べて多くのオーバーヘッドを必要としませんが、各ポイントが少なくとも 1 つの他のポイントの 100 単位以内にあることを保証します (実際には、最初と最後の点を除いて、各ポイントは他の2 つのポイントの 100 単位以内になります)。
上記のバリエーションとして、ステップ 2 で、既に生成されたポイントをランダムに選択し、前のポイントの代わりに参照として使用します。