C++で円の内部に一様ランダムな点を生成する方法

問題概要

円の半径と中心のx・y座標が与えられたとき、円の内部から一様（均等）にランダムな点を1つ生成する関数 randPoint() を実装します。実装にあたっては、以下の点に注意する必要があります。

• 入力値および出力値はすべて浮動小数点数として扱います。
• 半径と中心のx・y座標は、クラスのコンストラクタに渡されます。
• 円周上の点も「円の中にある」ものとみなします。
• randPoint() は、ランダムな点のx座標とy座標をこの順で返します。

例えば、入力が [10, 5, -7.5]（半径10、中心 (5, -7.5)）の場合、randPoint() を呼び出すたびに、[11.15792, -8.54781]、[2.49851, -16.27854]、[11.16325, -12.45479] のような異なる点が生成されます。

アルゴリズムの考え方

この問題を解くには、以下の手順に従います。

• まず、0以上1以下の一様乱数を返すメソッド uniform() を定義します。内部では rand() の戻り値を最大値 RAND_MAX で割ることで実現します。
• コンストラクタを通じて、半径と中心座標を初期化します。
• randPoint() は次のように動作します。
  • theta = 2 × π × uniform() として角度を決める。
  • r := uniform() の平方根 として中心からの距離を決める。
  • (center_x + r × radius × cos(theta), center_y + r × radius × sin(theta)) のペアを返す。

なぜ r に平方根を取るのか？

一様乱数をそのまま半径 r として使うと、中心付近に点が偏って集中し、面積に対して均等な分布になりません。円の面積は半径の2乗に比例するため、r = sqrt(uniform()) とすることで、面積ベースの一様な分布が得られます。これは極座標系でランダムサンプリングを行う際の定番テクニックです。

実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    const double PI = 3.14159265358979732384626433832795;
    double m_radius, m_x_center, m_y_center;
    double uniform() {
        return (double)rand() / RAND_MAX;
    }
    Solution(double radius, double x_center, double y_center) {
        srand(time(NULL));
        m_radius = radius; m_x_center = x_center; m_y_center = y_center;
    }
    vector<double> randPoint() {
        double theta = 2 * 3.14159265358979323846264 * uniform();
        double r = sqrt(uniform());
        return vector<double>{
            m_x_center + r * m_radius * cos(theta),
            m_y_center + r * m_radius * sin(theta)
        };
    }
};
main(){
    Solution ob(10, 5, 7);
    print_vector(ob.randPoint());
    print_vector(ob.randPoint());
    print_vector(ob.randPoint());
}

入力

コンストラクタに 10, 5, 7 を渡す
randPoint() を3回呼び出す

出力

[1.5441, 9.14912]
[-1.00029, 13.9072]
[10.2384, 6.49618]

まとめ

極座標変換を利用し、角度 θ を一様乱数から、距離 r を一様乱数の平方根から求めることで、円の内部に一様に分布するランダムな点を効率的に生成できます。各呼び出しの計算量は O(1) と非常に軽量で、三角関数と確率の知識を組み合わせた実践的なアルゴリズムです。