長方形のサーフェスを N 個の点でボロノイ分割したいとしましょう。ボロノイ分割により、N 個の点に対応する N 個の領域が生成されます。各領域について、その面積を計算し、それを表面全体の総面積で割ります。これらの数値を a1、...、aN と呼びます。それらの合計は 1 に等しくなります。
ここで、N 個の数値 b1、...、bN のプリセット リストがあり、それらの合計が 1 に等しいとします。
a1==b1、a2==b2、...、aN==bN のように、ボロノイ分割の N 点の座標の選択肢 (任意の) を見つけるにはどうすればよいでしょうか?
編集：
これについて少し考えてみると、Voronoi 分割は最適な解決策ではないかもしれません。N 領域が適切なサイズになるように、サーフェスをランダムに不規則に分割することが重要です。ボロノイは論理的な選択のように思えましたが、間違っているかもしれません。
私はいくつかの遺伝的アルゴリズムに行きます。
基本的なプロセスは次のとおりです。
1) 長方形に属するランダムな点を 100 セット作成します。
2) 各セットについて、ボロノイ図と面積を計算します
3) 各セットについて、事前に設定したウェイトと比較してどれだけ優れているかを評価します (スコアと呼びます)。
4) ポイントのセットをスコアで並べ替える
5) 50 個の最悪のセットをダンプする
6) 残りの 50 セットから 50 セットを mixin ポイントで作成し、ランダムなものをいくつか追加します。
7) 条件を満たすまでステップ 2 にジャンプします (しきい値を超えるスコア、発生回数、費やした時間など...)。
あなたは（うまくいけば）「ある程度適切な」結果になるでしょう。
探しているものが必ずしもボロノイ分割である必要はなく、べき乗図である可能性がある場合は、次の記事で説明されている優れたアルゴリズムがあります。
F. Aurenhammer、F. Hoffmann、および B. Aronov、「ミンコフスキー タイプの定理および最小二乗クラスタリング」、 Algorithmica、20 : 61-76 (1998)。
問題の彼らのバージョンは次のとおりです。多角形 P 内の N 個の点 (p_i) と、P の面積を合計する非負の実数 (a_i) のセットが与えられた場合、重み (w_i) を見つけます。 Power セル Pow_w(p_i) と P の交点は正確に a_i です。この論文のセクション 5 では、この問題が凸最適化問題として記述できることを証明しています。このアプローチを実装するには、次のものが必要です。
「二次最適トランスポート」という名前で、まさにこれを行うコードがWebページにいくつかあります。ただし、このコードはあまりきれいではなく、十分に文書化されているわけでもないため、独自のバージョンのアルゴリズムを実装する方が速いかもしれません。また、このトピックに関する私の SGP2011 論文も参照できます。これは同じページで入手でき、Aurenhammer、Hoffman、および Aronov のアルゴリズムの実装に関する簡単な説明が記載されています。
四角形が x = 0 で左端、x = 1 で右端、y = 0 で水平二等分線と軸が揃えられている座標を想定します。B(0) = 0 および B(i) = b1 + ... + とします。双方向。((B(i-1) + B(i))/2, 0) に点を置きます。それは正しくありません。x 座標を xi として、bi = (x(i+1) - x(i-1)) / 2 とし、x(0) を 0 に、x(n+1) を 1 に置き換えます。これは三重対角であり、簡単な解決策があるはずですが、おそらくそのような退屈なボロノイ図は必要ありません。それは垂直方向の分割の束になります。
よりランダムに見える図については、おそらく物理学に触発されたものがあります。点をランダムにドロップし、ボロノイ図を計算し、各セルの面積を計算し、太りすぎのセルを隣接する点に魅力的にし、セルを反発的に減量し、それぞれの小さなデルタを計算しますポイント、平衡に達するまで繰り返します。
最小スパニング ツリーを計算し、最長のエッジを削除すると、ボロノイ テッセレーションを計算できます。mst のサブツリーの各中心は、ボロノイ図の点になります。したがって、ボロノイ図は最小全域木のサブセットです。