3

固定空間内に均等に分散された一連の K ポイントを生成しようとしています。単位球または立方体が最も簡単であると考えました。2 次元の場合は簡単でしたが、残念ながら任意の次元 D に行くとかなり難しくなります。

これは「準モンテカルロ法」で行われていると思いますが、これが扱いやすい問題であるかどうかについての公式や声明さえ見つけることができませんでした。任意の入力をいただければ幸いです。

4

4 に答える 4

7

最良のケースを計算することは「些細なことではない」ことを確認するには、3D キューブ内の点のサブケースに対処する論文「Dense Packings of Equal Spheres in a Cube 」を参照してください。28 個までの正確な解と「最もよく知られている」解があります。ポイント。

それは、「確率的ビリヤード」手順と呼ばれる、これらの最適な間隔の構成を見つけるためのアルゴリズムを提示します。ただし、これが球体、高次元、またはより多くの点に適応できるかどうかはわかりません。

また、より一般的なケースのいくつかの側面は、Finite Packing and Covering - (私はコピーを持っていないため、確認できません)という本でカバーされているようです。

2D の場合ははるかに扱いやすく、正方形と円の詳細についてはウィキペディアを参照してください。

于 2013-05-30T00:51:24.133 に答える
4

「均等に」の意味によって異なります。1 つのアプローチは、ポイントをランダムに配置し、ニュートンの運動方程式の数値積分器を使用して減衰媒体内の粒子の動きをシミュレートすることです。この場合、粒子と境界は相互に反発します。もちろん、これにより任意の境界形状が許可されます。

于 2013-05-29T23:42:31.420 に答える
1

立方体の方が簡単なので考えてみましょう（最初は簡単と言っていました笑）。これがあなたが望むものだと思います（3Dで）：

ここに画像の説明を入力

辺のポイント数は n = floor(K 1/D ) です。コーナーとエッジが含まれると仮定すると、ポイント間の間隔は 1 / (n - 1) になります。このグリッド アプローチのコードをいくつか提供するつもりでしたが、それは非常に見苦しく、ソリューションは理想的ではありません。

于 2013-05-29T23:41:41.850 に答える
1

私はあなたの質問を完全に理解したとは確信していませんが、ここに私の行き方があります.

public static List<int[]> getEvenSpacedPoints(int x0, int x1, int y0,
        int y1, int z0, int z1, int samplePerSide) {

    List<int[]> list = new ArrayList<>();
    int xSpacing = (x1 - x0) / samplePerSide;
    int ySpacing = (y1 - y0) / samplePerSide;
    int zSpacing = (z1 - z0) / samplePerSide;

    for (int i = 0; i < samplePerSide; i++) {
        for (int j = 0; j < samplePerSide; j++) {
            for (int w = 0; w < samplePerSide; w++) {
                int xPoint = xSpacing * i;
                int yPoint = ySpacing * j;
                int zPoint = zSpacing * w;
                int[] point = new int[] { xPoint, yPoint, zPoint };
                list.add(point);
            }
        }

    }
    return list;
}

と

List<int[]> setOfSamplesFromCube = getEvenSpacedPoints(0, 10, 0, 10, 0,
            10, 5);
    for (int[] point : setOfSamplesFromCube) {
        String ret = "";
        for (int value : point) {
            ret += value + ",";
        }
        System.out.println(ret);
    }

外：

0,0,0,
0,0,2,
0,0,4,
0,0,6,
0,0,8,
0,2,0,
0,2,2,
0,2,4,
0,2,6,
0,2,8,
0,4,0,
0,4,2,
0,4,4,
0,4,6,
0,4,8,
0,6,0,
0,6,2,
0,6,4,
0,6,6,
0,6,8,
0,8,0,
0,8,2,
0,8,4,
0,8,6,
0,8,8,
2,0,0,
2,0,2,
2,0,4,
2,0,6,
2,0,8,
2,2,0,
2,2,2,
2,2,4,
2,2,6,
2,2,8,
2,4,0,
2,4,2,
2,4,4,
2,4,6,
2,4,8,
2,6,0,
2,6,2,
2,6,4,
2,6,6,
2,6,8,
2,8,0,
2,8,2,
2,8,4,
2,8,6,
2,8,8,
4,0,0,
4,0,2,
4,0,4,
4,0,6,
4,0,8,
4,2,0,
4,2,2,
4,2,4,
4,2,6,
4,2,8,
4,4,0,
4,4,2,
4,4,4,
4,4,6,
4,4,8,
4,6,0,
4,6,2,
4,6,4,
4,6,6,
4,6,8,
4,8,0,
4,8,2,
4,8,4,
4,8,6,
4,8,8,
6,0,0,
6,0,2,
6,0,4,
6,0,6,
6,0,8,
6,2,0,
6,2,2,
6,2,4,
6,2,6,
6,2,8,
6,4,0,
6,4,2,
6,4,4,
6,4,6,
6,4,8,
6,6,0,
6,6,2,
6,6,4,
6,6,6,
6,6,8,
6,8,0,
6,8,2,
6,8,4,
6,8,6,
6,8,8,
8,0,0,
8,0,2,
8,0,4,
8,0,6,
8,0,8,
8,2,0,
8,2,2,
8,2,4,
8,2,6,
8,2,8,
8,4,0,
8,4,2,
8,4,4,
8,4,6,
8,4,8,
8,6,0,
8,6,2,
8,6,4,
8,6,6,
8,6,8,
8,8,0,
8,8,2,
8,8,4,
8,8,6,
8,8,8,

これには開始点 (省略したい場合は 1 でループを開始) が含まれており、渡した立方体には 5 で割り切れるナイス サイドがあるため、「簡単」です。ダブルリストを返すように簡単に変更できます。

D次元のケースに挑戦してみます..

于 2013-05-30T00:16:26.593 に答える