2

1次元の値の範囲(つまり、連続した整数)をk個のセクションにランダムに分割する方法が必要です。疑似ランダムジェネレータを使用して分割点を選択するだけで、技術的には作業が完了します。ただし、範囲が非常に小さい(逆に非常に大きい)可能性があります。私は、ハードコードされた範囲制限に頼ることなく、この問題を一般的に解決する方法を探していました。

この記事を見つけました。これは、2D地形の生成に関係しています。しかし、それは同じ問題に直面し、解決策を提示します。著者がロイドリラクゼーションについて言及しているポリゴンセクションを見ることができます。その全体がボロノイ図から派生し、2D範囲で機能します。さらに、ロイド緩和が必要とするボロノイ図を作成するためのアルゴリズムを見ると、次のように始まります。

*(z)を変換*(z)=(zx、zy + d(z))とします。ここで、d(z)はzで最小の放物線です。

当然、1dには放物線はありません。

私の1d範囲の場合に同じ結果を達成する方法は私にはわかりません。それとも、問題に対して別の/より良いアプローチがありますか?

4

1 に答える 1

7

私は彼のコードの詳細には触れませんでしたが、彼が2Dでボロノイ図を使って行ったこと、次にポリゴンの中心を新しい点として選択し、ボロノイ図を作り直すことで、このアイデアが得られました。

1. Randomly select your points
2. Compute midways between your points
    -> The two midways on the two sides of each point, is like
       its Voronoi polygon in the Voronoi diagram
    -> So let's call the range between these two "midways" a Voronoi range!
3. Replace each point by the center of its Voronoi range
4. If you want the values to be less random, loop back to step 2
5. The ranges you are looking for are the Voronoi ranges of the last results.

例を挙げてみましょう。簡単にするために、連続範囲で作業していると仮定しましょう。

したがって、範囲[0、80]から始めて、それを15の範囲に分割します。

ソートされた後の15個の乱数が(Cプログラムによって生成された)としましょう:)

1 5 12 17 19 21 26 31 38 47 52 54 56 67 71

中点は次のとおりです。

1   5   12   17   19   21   26   31   38   47   52   54   56   67   71
  ^   ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^
  |   |    |    |    |    |    |    |    |    |    |    |    |    |
  3  8.5 14.5  18   20  23.5 28.5 34.5 42.5 49.5  51   55  61.5  69

したがって、範囲は次のようになります。

[0, 3], [3, 8.5], [8.5, 14.5], [14.5, 18], [18, 20], 
[20, 23.5], [23.5, 28.5], [28.5, 34.5], [34.5, 42.5], [42.5, 49.5],
[49.5, 51], [51, 55], [55, 61.5], [61.5, 69], [69, 80]

これを視覚化したい場合は、次のようになります(テキストで表示できるのが最善です)。

+..+.....+.....+..+.+...+....+.....+.......+......++...+......+......+.........+

ここで、.0から80までの番号を+表示し、ボロノイ範囲のエッジを表示します。

それでは、ステップ3を適用しましょう。

1   5   12   17   19   21   26   31   38   47   52   54   56   67   71
  ^   ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^
  |   |    |    |    |    |    |    |    |    |    |    |    |    |
0 3  8.5 14.5  18   20  23.5 28.5 34.5 42.5 49.5  51   55  61.5  69 80
 ^  ^   ^     ^   ^    ^    ^    ^    ^    ^    ^    ^    ^     ^  ^
 |  |   |     |   |    |    |    |    |    |    |    |    |     |  |
1.5 | 11.5  16.25 19 21.75 26  31.5 38.5  46  50.25 53  58.25 65.25|
   5.75                                                          74.5

それでは、ボロノイ範囲が新しいポイントでどのように見えるかを見てみましょう。

1.5  5.75 11.5  16.25  19  21.75 26  31.5 38.5  46  50.25 53  58.25 65.25 74.5
   ^     ^    ^       ^   ^     ^   ^    ^    ^    ^     ^    ^    ^     ^
   |     |    |       |   |     |   |    |    |    |     |    |    |     |
 3.625 8.625 13.875 17.625|  23.875 |   35  42.25 48.125 | 55.625 61.75 69.875
                        20.375    28.75               51.625

今、あなたの範囲は(それは醜く見え始めていますが、私に耐えます)

[0, 3.625], [3.625, 8.625], [8.625, 13.875],
[13.875, 17.625], [17.625, 20.375], [20.375, 23.875],
[23.875, 28.75], [28.75, 35], [35, 42.25],
[42.25, 48.125], [48.125, 51.625], [51.625, 55.625],
[55.625, 61.75], [61.75, 69.875], [69.875, 80]

それでは、このポイントの分布がどのように見えるかを見てみましょう。

+...+....+....+...+..+..+....+.....+.......+....+...+...+.....+.......+........+

次に、2つの分布を比較してみましょう。

First one 
  |
  V
+..+.....+.....+..+.+...+....+.....+.......+......++...+......+......+.........+
+...+....+....+...+..+..+....+.....+.......+....+...+...+.....+.......+........+
  ^
  |
Second one

見栄えが良くなりませんか?これは、2Dボロノイポリゴンを1D範囲に適用して見つけた記事で彼が行ったこととまったく同じです。

(計算エラーの可能性があるので失礼します)

于 2011-10-19T20:53:39.983 に答える