【ITニュース解説】Randomly selecting points inside a triangle

システム開発の現場では、ゲームのキャラクターの配置やシミュレーションにおける粒子の散布など、特定の幾何学的図形である三角形の内部にランダムな点を生成するタスクが時折発生する。四角形のようにX座標とY座標を独立に選ぶだけで良い図形とは異なり、三角形の場合は少し工夫が必要だ。この記事では、三角形の内部にランダムな点を生成する複数の方法と、それぞれの方法が持つ特徴について解説する。

まず一つ目の方法は、三角形の三つの頂点のうち一つを基準点とし、そこから他の二つの頂点へ向かうベクトルを用いて点の位置を決定する、という直感的なアプローチだ。例えば、三角形の頂点をA、B、Cとする。ここで、0から1の間の二つの乱数 s と t を生成し、点Pの位置を A + s * (B - A) + t * (C - A) という式で計算する。この式は、基準点AからB方向へ s の割合、C方向へ t の割合だけ進んだ点を示す。しかし、この計算式が表現する領域は三角形ではなく、実際には頂点A、B、Cを含む平行四辺形になってしまう。そのため、この平行四辺形のうち、三角形の外側になる部分、具体的には s + t の値が1よりも大きくなる領域の点を修正する必要がある。記事で紹介されている方法では、s + t > 1 の場合に s を 1 - s に、t を 1 - t に置き換える、という修正を行う。この修正によって、外側にはみ出した点が三角形の内側に移動するように見える。しかし、この方法で生成された点は、三角形の内部に均一には分布しないという問題がある。特に、基準点として選んだAの近くに点が集中しやすくなる傾向が見られる。これは、乱数 s と t の組み合わせによって表現される平行四辺形の面積のうち、s + t <= 1 の領域と s + t > 1 の領域で点の生成密度に数学的な偏りが生じてしまうためである。

次に、この一つ目の方法における点の偏りを解消し、より均一な分布を得るために考案された改良版のアプローチがある。この方法も、0から1の間の二つの乱数 u と v を使用し、点Pを A + u * (B - A) + v * (C - A) という基本式で計算する点は同じだ。しかし、一つ目の方法とは異なる修正を加えることで均一性を実現する。具体的には、u + v の値が1よりも大きい場合に、u を 1 - u に、v を 1 - v に変換する。この変換は、見かけ上は一つ目の方法と似ているかもしれないが、実際には乱数uとvが初期に選ばれた段階で u + v > 1 であった点を、三角形の内側の適切な位置に効率的に「再配置」する効果がある。これにより、元の平行四辺形のうち、三角形の外側にはみ出す部分に生成されるはずだった点を、三角形の内側に均等に割り振ることができ、最終的に三角形の内部全体に点が均一に分布するようになる。この方法は、比較的簡単に実装でき、均一な結果が得られるため、実用的な選択肢となるだろう。

そして、これまでに紹介した二つの方法よりもさらにシンプルで、かつ確実に均一な分布を実現する優れたアプローチが存在する。この方法は、三角形の重心座標系という考え方を利用している。重心座標系では、三角形の内部の任意の点は、三つの頂点A、B、Cをそれぞれ重み付けした平均として表現できる。具体的には、点Pは aA + bB + cC という形で表され、ここで a、b、c はそれぞれ0から1の間の係数であり、かつ a + b + c = 1 という厳密な条件を満たす。この a、b、c の値が、三角形の内部のどこに点が位置するかを決定する重みを表している。この条件を満たすランダムな a、b、c の組み合わせを生成するには、0から1の間の三つの乱数 u、v、w を用意する。次に、これらの乱数の合計 S = u + v + w を計算し、それぞれの乱数を合計 S で割って正規化する。つまり、a = u / S、b = v / S、c = w / S とする。このようにすることで、常に a + b + c = 1 という条件が満たされ、かつ a、b、c はランダムに分布する。この方法で生成された点Pは、三角形の内部全体に完全に均一に分布する。このアプローチは、数学的な背景がしっかりしており、実装も直感的で理解しやすいため、三角形内に均一なランダム点を生成する場合には最も推奨される方法と言える。

このように、三角形の内部にランダムな点を生成する方法は複数存在するが、それぞれに特性がある。最初の方法では、直感的なアプローチにもかかわらず、特定の頂点近くに点が偏ってしまうという問題があった。改良版の方法では、適切な座標変換を加えることで均一な分布を実現できるが、そのロジックはやや巧妙である。そして、最もシンプルで確実なのは、重心座標系の考え方を利用し、三つの乱数を正規化して重みとして使う方法である。この方法は、常に三角形の内部に完全に均一な点を生成できるため、システムエンジニアが将来的にこのような課題に直面した場合、特に複雑な幾何学的計算を伴わない場面では、この重心座標系に基づくアプローチが最も効果的かつ信頼性の高い選択肢となるだろう。それぞれの方法の特性を理解しておくことは、状況に応じて最適なアルゴリズムを選択するために重要だ。