ポイントリラックス

ひとことで

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

ゲームでの使いどころ

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

しくみ

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

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

• 点が混んでいる所では、領域が点の外側に偏るので、重心は外側にあり、点は外へ動きます。
• 大きなすき間の隣の点は、領域がすき間の方へ広がっているので、すき間へ引っぱられます。

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

実装のポイント

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

つまずきやすい点

• 計算が重い：点の数 × 画素数の計算になるので、点が多いと重くなります。近くの点だけを調べる工夫や、GPU での計算が必要です。
• 規則的になりすぎる：くり返しすぎると、点が蜂の巣状にきれいに並び、人工的に見えます。
• 最初の配置の影響：点が一か所に固まった状態から始めると、広がりきるまでに多くの回数が必要です。

デモで試すこと

1. でたらめに置いた点の、色分けした領域がなわばり（ボロノイ領域）で、赤い線がなわばりの重心への移動です。
2. くり返すたびに、数値の「いちばん近い 2 点の距離」が大きくなり、「なわばりの大きさのばらつき」が小さくなることを確かめてください。
3. 「最初の並び」を「かたまり」にすると、一か所に固まった点が、少しずつ全体に広がっていく様子が見えます。
4. 「重心へ動かす割合」を小さくすると、ゆっくりと並びが整っていきます。