A頂点、B、およびを持つ任意の三角形があるとしますC。この論文 (セクション 4.2)では、次の頂点の凸結合によって、P三角形内から一様にランダムな点 を生成できると述べています。ABC
P = (1 - sqrt(r1)) * A + (sqrt(r1) * (1 - r2)) * B + (sqrt(r1) * r2) * C
ここで、r1とr2は から一様に引き出され[0, 1]、sqrtは平方根関数です。
サンプリングされたポイントが三角形内に均一に分布していることをどのように正当化しますABCか?
編集
mathoverflow の質問に対するコメントで指摘されているように、 Graphical Gems ではこのアルゴリズムについて説明しています。
単位正方形から三角形へのマップ P(r1,r2) があります。r1 と r2 を一様に選択すると、単位正方形内のランダムな点が得られます。三角形内の画像は、写像 P のヤコビ行列式に従って分布し、これは定数であることがわかります。したがって、画像の分布も均一です。
実際には、これを確認するには、共線でないポイント A、B、C の 1 つのトリプルについて確認するだけで済みます。アフィン線形マップには一定のヤコビアンがあるため、これらのいずれかを適用して、分布に影響を与えることなく、任意のトリプルをこの標準位置に移動できます。
最後に、「理由」について一言: BC 側に平行な線分によって塗りつぶされた三角形を考えてみましょう。P の式では、変数 r1 はポイントが存在するセグメントを選択し、r2 はセグメントに沿った場所を決定します。均一性のために、特定のセグメント上のすべてのポイントを均等に処理する必要があります (したがって、r2 では線形)。ただし、r1 の場合、一部のセグメントは他のセグメントよりも短いため、均一な分布を実現するには、長いセグメントを優先する必要があります。式の sqrt(r1) がこれを説明します。