ランダム凸多角形の生成方法は？

Question

私は、ランダムな2D凸多角形を生成する方法を考案しようとしています。それは以下の特性を持たなければならない：

• 座標は整数でなければならない。
• ポリゴンは、コーナー（0,0）と（C、C）を持つ正方形の内側にある必要があります。
• 多角形が正方形の内部10個の頂点と位置を有するランダムポリゴン[0..100]×[0..100]を生成し、例えば、所与の数Nを

に近い頂点の数を有していなければなりません。

この作業を難しくしているのは、座標が整数でなければならないということです。

私が試みたアプローチは、与えられた四角形にランダムな点集合を生成し、これらの点の凸包を計算することでした。しかし、結果として得られる凸包は、Nに比べて非常に小さな頂点です。

アイデア？

Answer 1

これはまだ完全ではありませんが、いくつか考えていただけます。

Bail out if N < 3. N個の頂点を持つ単位円を生成し、ランダムに[0..90]度回転させます。

各頂点を原点から外側にランダムに押し出し、隣接する頂点のペアと原点の間に外積の符号を使用して凸性を判定します。これは速度と品質の間にトレードオフがある段階です。

頂点を設定したら、原点から最大の大きさの頂点を見つけます。ポリゴンを正規化するために、すべての頂点をその大きさで除算し、それを（C/2）だけ元に戻します。 （C/2、C/2）に変換し、整数にキャストし直します。

Answer 2

単純なアルゴリズムは次のようになります。

1. ランダムなラインでスタート（2つの頂点と2辺のポリゴン）
2. はポリゴン
3. のランダムなエッジEに乗り、このエッジ上の新しいランダム点Pを作ります
4. 点Pを通るEに対して垂直な線Lを取る。線TとEに隣接する2つの辺によって定義される線との交点を計算することによって、凸が壊れていないときのPの最大オフセットを計算する。
5. ポイントPをその範囲内でランダムにオフセットします。 2.

Answer 3

あなたの最初のアプローチが正しいから

ない場合は十分なポイントは、リピート - 凸包を計算すると、あなたはランダム、凸部とintegernessを満足させる唯一の方法です。

「より多くのポイント」を得るためにアルゴリズムを最適化する唯一の方法は、完全にランダムではなく円の周りに整理することです。あなたのポイントは、中心付近よりもあなたの四角形の「辺」近くにある可能性が高いはずです。中心では、ポリゴンが凸でなければならないので、確率は〜0でなければなりません。

単純なオプションの1つは、ポイントが表示される最小半径を設定することです（おそらくC/2またはC * 0.75）。C正方形の中心を計算し、点が近すぎる場合は、中心から最小距離になるまで移動します。

Answer 4

これは、私が知っている最も速いアルゴリズムです。それは、等しい確率で各凸多角形を生成します。出力は正確にN個の頂点を持ち、実行時間はO（N log N）であるため、大規模なポリゴンをすばやく生成することもできます。

• 0とCの間のNのランダムな整数の二つのリスト、XとYを生成する重複しないことを確認してください。
• XとYをソートし、最大値と最小値を格納します。
• 他の（最大または最小でない）要素をX1とX2とY1とY2の2つのグループにランダムに分割します。
• これらのリストの先頭と最後に、最小値と最大値の要素を挿入してください（の先頭にminX、最後にX2,maxXなど）。
• 2番目のグループ（X2[i] - X2[i + 1]）の順序を逆にして、連続する相違点（X1[i + 1] - X1[i]）を見つけます。これらをリストXVecとYVecに格納します。
• YVecをランダム化（シャッフル）し、各ペアXVec[i]およびYVec[i]を2Dベクターとして処理します。
• これらのベクトルを角度でソートし、次にそれらをエンドツーエンドに配置してポリゴンを形成します。
• 多角形を元の最小座標と最大座標に移動します。

アニメーションとJavaの実装は、Generating Random Convex Polygonsで利用できます。

このアルゴリズムは、Pavel Valtrの論文「Probability that n random points are in convex position」に基づいています。ディスクリート&計算幾何学13.1（1995）：637-643。