【科学技術計算講座ミニ】四分木と空間分割

以前、木構造と二分探索木についてお話しました。

今回は四分木とそれを使った空間分割について解説します。

四分木

二分木は１つのノードに対して２つの子ノードを持つ木構造をしていましたが、同様に子ノードを４つ持つ木構造を四分木と言います。

ルートノードから４つの子ノードに枝分かれし、さらに４つの子ノードに枝分かれしていきます。

空間分割

四分木はよく空間分割などに使われます。空間分割とは以前粒子法で説明した近傍粒子の探索の所で出てきました。そのときは、空間を一様な大きさに当分割して近傍粒子の探索を高速化しました。

空間を均等に分割すると、空間に対して分割サイズが小さい場合は多くのメモリを使うことになります。このとき、粒子の分布が偏っていた場合、粒子が不在の領域も均等に分割されるため、無駄に多くのメモリが必要になります。

そこで、四分木を空間分割に適用する方法があります。

まず空間を一つの四角で表します（上図の①）。次に四角を均等に４分割します（②）。さらに必要に応じて一部の四角を均等に４分割していきます（③の右上）。このように必要な箇所だけ細かく分割していけば、全体を均等に細かく分割するより全体の分割数が抑えられるというわけです。

これを木構造で考えると、①がルートノードです。これを４分割して４つの子ノードに分けます（②）。②のノードのうち右上のノードを分割し、さらに４つの子ノードを作ります（③）。木構造であれば、これまでと同様にノードの連結を考えてプログラミングできそうです。

では、ノードはどのタイミングで分割されるのでしょうか。今回は粒子の配置による分割を考えましょう。つまり、粒子が少ない領域は大きな分割サイズとし、粒子が密集している領域は細かい分割になるようにすると、無駄が少なくなりそうです。

それには、ノードに含まれる粒子数が、ある個数を超えると分割するようにします。

この図はノードに含まれる粒子数の制限を３個としています。まずルートノードに３個の粒子が存在しています（①）。ここに、もう１個粒子を挿入すると、制限を超えるので４分割します（②）。②の右上のノードの位置にさらに２つ粒子が追加されると、そのノードを分割します（③）。こうすることで粒子が密集している領域のノードは細かくなり、粒子が少ない場所は粗い分割のままにすることができます。

このような空間分割の仕方は流体解析などのメッシュ生成にも応用されています。物体の境界面や流れ場の急峻に変化する場所などでメッシュを細かくしたい場合、その周りだけ徐々に細かくすることでメッシュ数を抑えつつ解像度を上げることができます。当サイトのオンライン流体解析ツールCATCFDzeroでもソリッド周りの解像度を上げるため四分木による分割を行っています。

四分木による空間分割のプログラム

では四分木による空間分割のプログラムを作ってみましょう。前回の二分木はPythonでプログラミングしましたが、ここでは粒子法のときと同じようにJavaScriptを使ってプログラムを作ることにします。データ可視化用のJavaScriptライブラリp5.jsを使うことでインタラクティブにブラウザ上に図が描画できるので、空間分割のようすがよくわかると思います。

JavaScriptとp5.jsの詳細は「科学技術計算講座５－粒子法（SPH法）で流体シミュレーション」を一読してみてください。

作るもの

どのようなプログラムを作るかをはじめに説明しておきます。

まず、ブラウザ上に正方形の空間を用意し、そこに2000個の粒子をランダムに配置します。空間は四分木により分割されます。

そして、この空間にマウスカーソルを合わせると、カーソル位置のノードとそのノードに属する粒子をハイライトするようにしましょう。

次のリンクから実際の描画を開くことができるので確かめてみてください。

ここをクリックすると別ウィンドウが開きます。

キャンバス中央の粒子が集中している箇所では分割が細かく、外側の粒子が少ない場所では分割が荒くなっていることがわかります。

四角形のクラス

まず、分割ノードの四角形を表すクラスRectangleを定義します。これは前述の粒子法のプログラムに出てきたのと同じです。

class Rectangle {
  constructor(x, y, width, height) {
    this.width = width;
    this.height = height;
    this.left = x;
    this.right = x + width;
    this.bottom = y;
    this.top = y + height;
  }
}

四角の左下角の座標x、yと四角の幅width、高さheightを引数として、各プロパティを定義します。
width：幅、height：高さ、left：左端のx座標、right：右端のx座標、bottom：下端のy座標、top：上端のy座標。

粒子のクラス

粒子のクラスParticleは粒子法のときとは違い、座標x、yのみを持つ簡単なものとします。

class Particle {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

四分木のクラス

次に四分木のクラスQuadTreeを定義します。

class QuadTree {
  constructor(x, y, width, height, limit) {
    this.region = new Rectangle(x, y, width, height);
    this.sw = null;
    this.se = null;
    this.nw = null;
    this.ne = null;
    this.bucket = [];
    this.limit = limit;
  }

コンストラクターには四角形を定義するために、x、y、width、heightと、分割のための粒子の個数制限limitを引数で渡しています。

プロパティはregionに四角形のオブジェクトを定義します。そして分割後の４つのノードsw、se、nw、neを定義します。それぞれ以下の位置にあるとします。

なお最初、４つの子ノードはnullとしておきます。子ノードがnullということは、そのノードは分割されていない末端のノードであるということを意味します。

bucketはこのノードに含まれる粒子を格納するための配列です。後はlimitに制限粒子個数を入れます。

※以前、二分木のプログラムでは二分木クラスの他にノードのクラスを別途用意しましたが、今回は四分木のクラス自体がノードを表しているという構造にしています。前と同様にノードクラスを別途分けて作る方法でも可能です。

以下のページに続きます。

全体の目次