C++で重ならない長方形領域からランダムに点を一様に選択する方法

問題概要

軸に平行で互いに重ならない長方形のリスト rects が与えられているとします。このとき、長方形が覆う空間の中から整数座標の点をランダムかつ一様に選択して返す関数 pick を実装する必要があります。

実装にあたっては、以下の条件を満たす必要があります。

• 整数点とは、x座標・y座標がともに整数である点を指します。
• 長方形の周囲（境界線）上にある点も、長方形が覆う空間に含まれるものとします。
• i番目の長方形 rects[i] は [x1, y1, x2, y2] という形式で表されます。ここで [x1, y1] は左下隅の整数座標、[x2, y2] は右上隅の整数座標です。
• 各長方形の縦および横の長さは 2000 を超えません。
• 長方形の個数は 1 以上 100 以下です（1 <= rects.length <= 100）。
• pick は選ばれた点を整数座標の配列 [p_x, p_y] として返します。

たとえば入力が [1, 1, 5, 5] の場合、pick() を3回呼び出すと、結果は [4, 1]、[4, 1]、[3, 3] のようになります（乱数を使用するため、実行ごとに結果は異なります）。

解法のアプローチ

この問題を解く鍵となるのは「面積に比例した確率で長方形を選ぶ」ことです。これにより、全体の空間に対して点が一様に分布することになります。手順は以下の通りです。

コンストラクタでの前処理

• area と rect という2つの配列を用意します。
• rect に入力の rects をコピーし、累積面積の合計を表す変数 sum を 0 で初期化します。
• 各長方形について以下を繰り返します。
  • 左下隅 (x1, y1) と右上隅 (x2, y2) を取得します。
  • その長方形に含まれる整数点の個数 temp = |x2 − x1 + 1| × |y2 − y1 + 1| を計算します（境界線上の点も含むため +1 します）。
  • sum に temp を加算し、その値を area 配列に挿入します。これにより area には累積面積が格納されます。

pick メソッドでの点の選択

• randArea = 乱数 % sum + 1 として、1 から総面積までの範囲の乱数を生成します。
• area 配列を先頭から走査し、randArea <= area[i] となる最初のインデックス i を見つけます。これにより、面積に比例した確率で i番目の長方形が選ばれます。
• 選ばれた長方形内でのオフセットを決めます。
  • dist_x = 乱数 % |rect[i][0] − rect[i][2] + 1|
  • dist_y = 乱数 % |rect[i][1] − rect[i][3] + 1|
• (dist_x + rect[i][0], dist_y + rect[i][1]) を返します。

この手法により、大きな長方形ほど高い確率で選ばれ、結果として全空間における点の分布が一様になります。

実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector <int> area;
   vector < vector <int> > rect;
   int sum;
   Solution(vector<vector<int> >& rects) {
      rect = rects;
      sum = 0;
      for(int i =0 ; i < rects.size(); i++){
         int x1 = rects[i][0];
         int y1 = rects[i][1];
         int x2 = rects[i][2];
         int y2 = rects[i][3];
         int temp = (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1);
         sum += temp;
         area.push_back(sum);
      }
   }
   vector<int> pick() {
      int randArea = rand() % sum + 1;
      int i;
      for(i = 0; i < area.size(); i++){
         if(randArea <= area[i]) break;
      }
      int dist_x = rand() % (abs(rect[i][0] - rect[i][2] ) + 1);
      int dist_y = rand() % (abs(rect[i][1] - rect[i][3] ) + 1);
      return {dist_x + rect[i][0], dist_y + rect[i][1]};
   }
};
main(){
   vector<vector<int> > v = {{1, 1, 5, 5}};
   Solution ob(v);
   print_vector(ob.pick());
   print_vector(ob.pick());
   print_vector(ob.pick());
}

入力

["Solution", "pick", "pick", "pick"]
[[[[1, 1, 5, 5]]], [], [], []]

出力

[2, 3]
[4, 1]
[3, 5]

まとめ

本記事では、重なりを持たない複数の軸平行長方形から、整数点を一様かつランダムに選択する pick 関数の実装方法を解説しました。ポイントは次の2つです。

• 累積面積による加重選択：各長方形の面積を累積和として保持し、乱数を照合することで面積比例の確率で長方形を選べます。
• 境界線の扱い：辺の長さを計算する際に +1 することで、周囲上の点も選択対象に含めています。

計算量は、コンストラクタで O(n)、pick の呼び出しごとに O(n)（n は長方形の個数）となります。長方形の個数が最大100と小さいため、この線形探索でも十分高速に動作します。