Point Relaxation

This explanation is currently available in Japanese.

ひとことで

ばらばらに置いた点を、各点の「なわばり」（ボロノイ領域）の重心へ動かすことをくり返して、均等な間隔に並べ直す方法です（ロイドの緩和法）。混んだ所の点は外へ、すき間の近くの点はすき間へ引っぱられるので、数回で「規則的すぎず、でたらめでもない」ほどよい並びになります。

マップの区画：ボロノイ領域で国や地域、畑の区画を作るとき、先に緩和しておくと、大きさのそろった自然な区画になる（Amit Patel の「ポリゴンマップ生成」で有名）。
木・村・資源の配置：近すぎず、すき間も少ない配置にする。
ナビゲーションや地形のメッシュ：三角形分割の頂点を緩和して、細長い三角形を減らす。
点描・模様：画像の明るさに合わせた点の分布（重み付きの緩和）で、点描風の表現や、群衆の配置を作る。

点 $\mathbf{p}_i$ のボロノイ領域 $V_i$ は、「ほかのどの点より $\mathbf{p}_i$ に近い場所」の集まりです。緩和の 1 回は、

\mathbf{p}_i \leftarrow \mathbf{p}_i + \alpha\,\big(\mathbf{c}(V_i) - \mathbf{p}_i\big), \qquad \mathbf{c}(V_i) = \frac{1}{|V_i|}\int_{V_i} \mathbf{x}\,d\mathbf{x}

です。 $\mathbf{c}(V_i)$ は領域の重心、 $\alpha$ は動かす割合（ふつうは 1）です。

くり返すと、どの領域も点を中心とした大きさのそろった多角形（重心ボロノイ分割）に近づきます。完全に収束すると蜂の巣のような規則的な並びになるので、ゲームでは 2〜5 回で止めて、ほどよいばらつきを残すのが一般的です。

重心の求め方：ボロノイ領域の多角形を正確に作って面積と重心を計算する方法と、画面を細かい格子に分けて「どの点に一番近いか」を数える方法があります。後者は簡単で、GPU でも計算できます（ジャンプフラッドと相性がよい）。
境界の扱い：外周の点の領域は、マップの枠で切り取ってから重心を求めます。そうしないと、外周の点がどんどん外へ逃げていきます。
重み付きの緩和：重心を「密度で重みを付けた平均」にすると、密度の高い所に点が集まる配置になります（画像の明るさに合わせた点描など）。
回数で調整：1〜2 回ならでたらめさが少し残り、10 回以上なら格子に近い並びになります。目的の見た目で回数を決めます。