1

問題：

多角形を横切るランダムな線を生成するのに問題があります (凸面である必要はありません)。ラインは、完全にランダムなライン (ランダムな位置、ランダムな角度) と同じ分布を持つ必要があり、ポリゴンを完全に見逃しているラインは無視されます。

これまでの私の考え：

多角形内のランダムなポイントを選択し (私は既にそのアルゴリズムを持っています)、ランダムな角度を選択してもうまくいきません。完全にランダムな線は、ハンドルを突き破る可能性が高くなります。また、角度は間違いなく均一に分布しません。

同じ理由で、サーフェス内またはサーフェス上の 2 つのポイントを選択して、両方のポイントを通る線を生成したり、同様の方法で線を生成したりすることはできません。

編集: 使用できる方法が 2 つありますが、どちらにも完全に満足しているわけではありません。

  1. 多角形を含む円を見つけます。多角形を横切る線が見つかるまで、円を通るランダムな線を選びます。これは基本的に、ポリゴンにヒットする可能性が高いだけで上に書いた定義です。

  2. ポリゴンを n 方向 (例: 0°、10°、20° など) に投影します。投影のサイズは、この方向からの衝突の可能性に比例します。次に、方向を選択します (投影サイズを加重確率として使用)。最後に、角度に 360/n° ジッターを追加できます。これは分布を十分に近似するはずですが、それを行うより良い方法があるかどうか疑問に思います。

Edit2 : -deleted-
かなり多くのことを書きましたが、それについてもう少し考え、いくつかの間違いを発見した後、これが頭を悩ませていることに気付きました。アイデアは、多角形の凸包をいくつかの特定の方向に投影し、既知のものをブレンドすることによって他のすべての投影を与える関数を見つけることでした。しかし、詳細は非常に複雑で、現時点では私には多すぎることが判明しました.

4

1 に答える 1

3

図形と交差するランダムな線の概念は、厳密に定義するのが驚くほど厄介です。この種のアイデアのあいまいさのよく知られた例については、ベルトランの逆説を参照してください。平面内のランダムな線でさえ定義するのは簡単ではありません。「ランダムな点をランダムな角度で通過する線」のようなものを試すかもしれませんが、ランダムな点をどのように選択しますか？平面内のポイント全体に均一な分布はありません。

図形Fと交差するランダムな線を正確に定義する方法は次のとおりです。w （ θ）を角度θに垂直な図形Fの幅とします。

Fがポリゴンの場合、w （ θ）は区分的正弦関数で構成され、ポリゴンの凸包が頂点の対脚ペアを持っているのと同じ数のピースがあります。

ここで、確率密度関数としてp （θ）を使用して角度θを選択します。ここで、

p（θ）= w（θ）/∫w （ θ）dθ

次に、区間[0、w（θ）]で線の位置を均一に選択します。

（あなたの方法＃2は、少数のθの値をサンプリングし、区分的に一定の分布を構築することによってp （θ）を近似しようとします。しかし、それほど難しいことなく正確な結果を得ることができます。）

積分∫<em>w（θ）dθ（したがってp（θ））を計算するには、最初に多角形の凸包を見つけ、次に回転キャリパー法を使用して頂点の対蹠ペアを見つけます。隣接する対脚ペア間で、キャリパーはたとえばθ0からθ1に移動し、この範囲ではw （ θ）は次の式で与えられます。

w（θ）= dsin（θ-φ）

ここで、φは対蹠頂点間の線の角度です。dは、次の2つの図に示すように、その長さです。

ここで、 θ0からθ1の範囲で、不定積分は次のようになります。

∫w （θ）dθ=∫dsin （ θ-φ）dθ= -dcos （ θ-φ）

したがって、範囲[θ0 、θ1 ]のw（θ）の定積分は次のようになります。

d（cos（θ0 −φ） −cos（θ1 − φ））

これを対蹠点のすべてのペアで合計すると、積分全体が計算されます。

于 2013-01-22T15:30:57.423 に答える