TOP
Tutorials
Processing / Tutorials
Quadtreeによる空間分割を使った探査スピードアップの方法 for Processing

Processing / Tutorials

Date:2025-04-21

Quadtreeによる空間分割を使った探査スピードアップの方法 for Processing

大量のデータを効率よく扱いたいとき、空間を分割して整理する「空間分割データ構造」が役立ちます。その中でも特に有名なのが QuadTree（クワッドツリー）です。今回QuadTreeを使用した探査のスピードアップ方法を詳しくまとめます。

前回、最も簡単なグリッド法による空間分割として、空間分割アルゴリズムを使ったスピードアップの方法 for Processing をまとめました。今回は、それよりもさらに効率的に分割する QuadTreeによる空間分割によるスピードアップ方法になります。

この記事では、QuadTreeの基本概念、仕組みと構造、主な用途についてまとめ、Processingを使用した実装について詳しくまとめています。

1. QuadTree（クワッドツリー）とは？

QuadTreeとは、2次元空間を再帰的に4分割して管理するツリー構造のことです。主に「空間内のオブジェクトの探査を高速化」する目的で使われます。

「Quad」は「4つ」を意味し、各ノードが最大で4つの子ノードを持つことが名前の由来です。

1-1. なぜQuadTreeが必要なのか？

空間内に無数のオブジェクトが存在するとき、それらすべてを毎回１つずつ調べるのは非常に非効率です。必要なオブジェクトを必要な範囲のみ調べることで効率的な探査を行い、実行負荷を大きく減らすことができます。たとえば、「画面上のある半径内にいるオブジェクトだけ調べたい」といった場面では、クワッドツリーのような効率的な探査構造が威力を発揮します。

1-2. QuadTreeの仕組み

ノードの構成
QuadTreeは通常、以下のような情報を各ノードに持ちます。

空間領域（矩形の範囲）
領域内に存在するオブジェクトのリスト
子ノード（NE、NW、SE、SW の4つ）
空間内の最大格納数（上限を超えると分割）

分割のルール
あるノードがオブジェクト数の上限（capacity）を超えると、そのノードは 4つの子ノードに分割 され、オブジェクトは該当する子ノードへ振り分けられます。これを再帰的に分割していくことで空間全体をツリー状に管理できるようになります。

QuadTreeの用途
QuadTreeは、ゲーム開発による衝突判定や、画像処理によるエッジ検出、地理情報システム上のレイヤー管理などさまざまな分野で使われており、大量のデータを判定するのに役立ちます。

２. Processingによる実装

ここからは、QuadTreeを先ほどのQuadTreeの仕組みの考えに沿って、Processingにて実装します。この方法は、その他の環境・言語でも同様に実装できます。

完全なサンプルコードが必要な場合は下記 Patreon にてダウンロードできます。
https://patreon.com/c/barbe_generative_diary

2-1. QuadTreeに必要となる各classを作成する。

QuadTreeの空間分割では、再起的に判定範囲を分割していきます。必要になるのは下記３種類のclassです。まず、ProcessingにてQuadTreeのファイルを作成し、下記３つのクラス及びコンストラクタを制作します。

Pointクラス（パーティクルの位置を明示するクラス）
Rectangleクラス（境界となる空間枠クラス。再起的に利用）
QuadTreeクラス（分割や探査を行うQuadTreeのクラス）


class Point {
  float x, y;
  Point(float px, float py) {
    x = px;
    y = py;
  }
}

class Rectangle {
  float x, y, w, h;
  Rectangle(float rx, float ry, float rw, float rh) {
    this.x = rx;
    this.y = ry;
    this.w = rw;
    this.h = rh;
  }
}

class QuadTree {
  Rectangle boundary;
  int capacity;
  ArrayListpoints;
  boolean divided;

  QuadTree(Rectangle b, int cap) {
    boundary = b;
    capacity = cap;
    points = new ArrayList();
    divided = false;
  }
}

Pointクラス
各オブジェクトの座標位置を明示するためxy座標のコンストラクタを作成します。
Rectangleクラス
空間分割における範囲です。コンストラクタでは、範囲となる矩形の中点となるxy座標 、空間となる矩形の幅 w、高さ hを作成します。
QuadTreeクラス
ポイントが空間内の容量を超えたら分割しツリー構造による管理を行います。コンストラクタでは、範囲となるRectangleクラス boundary、範囲内に入るポイントの数の上限 capacity、ポイントを格納するArrayListを作成します。また、その範囲が分割されているかどうかをbooleanによって判定します。

2-2. Rectangleクラス

Rectangleクラスでは、後ほどQuadTreeクラスで使用するための関数を２種作成します。

contains( )　ポイントが空間内にあるかどうかを判定する関数（boolean）
intersects ()　検出における範囲を判定する関数。

これら関数のコードは次項QuadTreeクラス作成と並行して制作します。

2-3. QuadTreeクラス

QuadTreeでは、大きく三つの重要な関数があります。

insert( )
各ポイントを各境界内に入れていき、容量を超えたらsubdivide( )で分割する。
subdivide( )
４つに分割する関数。
query( )
範囲内のポイントを探査する関数。

insert ( )はポイントの位置がどの範囲にあるかをif文を使って確認します。よって引数にPointを使います。QuadTreeの分割範囲は下記のように分け再帰的に分割を行なっていきます。


QuadTree northeast, northwest, southeast, southwest;
boolean insert(Point pt){
   if(!boundary.contains(pt)){
     return false;
   }
  return false;
}

まずは、空間内にポイントがあるかどうかの判定をif(!boundary.contains(pt))にて判定します。空間の中にポイントがない場合にfalseを返します。

下記、判定の際に利用する関数contains( )をRectangleクラスで作成します。


boolean contains(Point pt){
  if(pt.x >= x - w &&
     pt.x < x + w &&
     pt.y >= y - h &&
     pt.y < y + h ){
     return true;
  }else{
     return false;
  }
}

このコードでは、ポイントがRectangle範囲x,yを中点とする範囲内にあるかどうかを幅w,高さhを使って判定しています。範囲内にあればtrue,なければfalse。

次に、ポイントが範囲内にあり且つ範囲内のcapacity以内の場合はポイントをリストに追加します。capacityを超えた場合はelseにて分割します。この工程をポイントが全てリストに収まるまで、再帰的に続け分割を行なっていきます。


QuadTree northeast, northwest, southeast, southwest;
boolean insert(Point pt){
   if(!boundary.contains(pt)){
     return false;
   }
   if(this.points.size() < this.capacity){
     points.add(pt);
   }else{
    if(!this.divided){
       this.subdivide(); 
      }
    if(this.northwest.insert(pt)){
      return true;
    }else if(this.northeast.insert(pt)){
      return true;
    }else if(this.southwest.insert(pt)){
      return true;
    }else if(this.southeast.insert(pt)){
      return true;
    }
  }
  return false;
}

pointが空間範囲のcapacityを超えた時に使用するsubdivide( )関数を作成します。


void subdivide(){
  float tx = boundary.x;
  float ty = boundary.y;
  float tw = boundary.w;
  float th = boundary.h;
  Rectangle northwestbd = new Rectangle(tx - tw/2, ty - th/2 , tw/2, th/2);
  northwest = new QuadTree(northwestbd, capacity);
  Rectangle northeastbd = new Rectangle(tx + tw/2, ty - th/2 , tw/2, th/2);
  northeast = new QuadTree(northeastbd, capacity);
  Rectangle southwestbd = new Rectangle(tx - tw/2, ty + th/2 , tw/2, th/2);
  southwest = new QuadTree(southwestbd, capacity);
  Rectangle southeastbd = new Rectangle(tx + tw/2, ty + th/2 , tw/2, th/2);
  southeast = new QuadTree(southeastbd, capacity);
  divided = true;
}

上記コードは、分割する空間範囲の中点座標と幅・高さをtx, ty, tw, thで明示し、四つに分割したそれぞれの位置に新しくRectangleで範囲を作成します。また、分割したかどうかのチェックをdividedにてtrueとします。

2-4. QuadTreeによる分割の確認

QuadTreeによる分割が行われているかを視覚的に確認するため、QuadTree内に下記display()関数を準備します。


void display(){
  for(int i=0; i < points.size(); i++){
    strokeWeight(10);
    stroke(255);
    point(points.get(i).x, points.get(i).y);
  }
    
  rectMode(CENTER);
  noFill();
  stroke(255);
  strokeWeight(1);
  rect(boundary.x, boundary.y, boundary.w*2, boundary.h*2);   
  if(this.divided){
    northwest.display();
    northeast.display();
    southwest.display();
    southeast.display();
  }
}

display()内では、pointリスト内のポイント表示、加えて、分割された範囲をRectを使って表示します。RectMode(CENTER)とすることで中点からの範囲を表示させます。

下記、setupとdrawにてQuadTreeによる分割を行います。


QuadTree qt;
Rectangle bd;
Point p;
int ptnum = 100;
int qtCap = 2;

void setup() {
  size(900, 900);
  bd = new Rectangle(width/2, height/2, width/2, height/2);
  qt = new QuadTree(bd, qtCap);

  for (int i=0; i < ptnum; i++) {
    Point p = new Point(random(width), random(height));
    qt.insert(p);
  }
}

void draw() {
  background(0);
  qt.display();
}

setupにて、Rectangleの範囲を作成、それをQuadTreeの引数として渡します。その後、ポイントをランダムに作成し、QuadTreeに入れるためinsertします。

drawにてdiplay()で表示させ、分割が正しく行われているかを確認します。（上記コード例は、ポイントの数が100、範囲内の容量が2以上で分割するようになります。）

2-5. Pointを探査するためのquary()を作成

QuadTree構造が確認できたところで、探査するためのquary()関数を作成します。下記は、任意の四角内で探査します。


void query(Rectangle range, ArrayList found){
  if(!range.intersects(boundary)){
    return;
  }
}

まず、先ほど、ポイントがあるかどうかを判定するためのconstain()関数を作成したのと同様に探査範囲内にポイントがあるかどうかを調べるためのintersects()関数をRectangleクラスに作成します。

下記、判定の際に利用する関数intersects( )をRectangleクラスで作成します。


boolean intersects(Rectangle boundary){
  float boundaryR = boundary.x + boundary.w;
  float boundaryL = boundary.x - boundary.w;
  float boundaryT = boundary.y - boundary.h;
  float boundaryB = boundary.y + boundary.h;
    
  float rangeR = x + w;
  float rangeL = x - w;
  float rangeT = y - h;
  float rangeB = y + h;
    
  if (boundaryR > rangeL &&
    boundaryL < rangeR &&
    boundaryT < rangeB &&
    boundaryB > rangeT) {
    return true;
  } else {
    return false;
  }
}

このコードでは、QuadTree分割された範囲が探査範囲と重なっているかどうかを判定します。範囲があればtrue,なければfalseです。

次に、quary( )に探査範囲内で見つけたポイントリストを作成する条件式を追加します。


void query(Rectangle range, ArrayList found){
  if(!range.intersects(boundary)){
    return;
  } else {
    for(int i=0; i < points.size(); i++){
      if(range.contains(points.get(i))){
        found.add(this.points.get(i));
      }
    }
    if (divided) {
      if (range.intersects(northeast.boundary)) {
          northeast.query(range, found);
      }
      if (range.intersects(northwest.boundary)) {
          northwest.query(range, found);
      }
      if (range.intersects(southeast.boundary)) {
          southeast.query(range, found);
      }
      if (range.intersects(southwest.boundary)) {
          southwest.query(range, found);
      }
    }
  }
}

contains( )を使用し探査範囲(range)内にポイントがあればポイントリストfoundに追加します。これをQuadTree構造内で再帰的に行い、dividedがtureの分割された範囲の重なっている部分を判定、見つけたポイントをfoundリストへと追加しています。

2-6. query( )による探査の確認

指定範囲内の探査が行われているかを確認します。


void draw() {
  background(0);
  
  Rectangle range = new Rectangle(mouseX, mouseY, 100, 100);
  noFill();
  stroke(0, 255, 0);
  strokeWeight(1);
  rectMode(CENTER);
  rect(range.x, range.y, range.w * 2, range.h *2);

  ArrayList foundPoints = new ArrayList();
  qt.query(range, foundPoints);
  
  qt.display();
  for (int i=0; i < foundPoints.size(); i++) {
    stroke(255, 255, 0);
    strokeWeight(15);
    point(foundPoints.get(i).x, foundPoints.get(i).y);
  }
}

探査範囲をマウスで移動できるようmouseX,mouseYを使用し、rangeをRectangleで作成ます。また、探査範囲をrectにて描画します。

rangeにより見つけたポイントを格納するリストを準備し、QuadTreeのquery()にて空のリストを渡し探査されたポイントを追加します。確認のため、探査範囲内で見つかったポイントの色を変えfor文にて描画します。

2-7. Circleによる探査

円による探査はRectangleクラスと同様の方法で矩形を円に変えclassを作成します。以下class Circle。また、QuadTreeのqueryの探査範囲引数をCircleにします。


class Circle{
  float x, y, radius;
  Circle(float theX, float theY, float theR) {
    x = theX;
    y = theY;
    radius = theR;
  }
  
  boolean contains(Point point) {
    float distX = x - point.x;
    float distY = y - point.y;
    float distance = sqrt(pow(distX, 2) + pow(distY, 2));

    if (distance <= radius) {
      return true;
    } else {
      return false;
    }
  }
  
  boolean intersects(Rectangle boundary) {
    float closeX = x;
    float closeY = y;
    if (x < boundary.x - boundary.w) {
      closeX = boundary.x - boundary.w;
    } else if (closeX > boundary.x + boundary.w) {
      closeX = boundary.x + boundary.w;
    }

    if (y < boundary.y - boundary.h) {
      closeY = boundary.y - boundary.h;
    } else if (y > boundary.y + boundary.h) {
      closeY = boundary.y + boundary.h;
    }

    float distX = abs(x - closeX);
    float distY = abs(y - closeY);
    float distance = sqrt(pow(distX, 2) + pow(distY, 2));

    if (distance <= radius) {
      return true;
    } else {
      return false;
    }
  }
}

Circleのコンストラクタは、範囲の中点座標x,yと半径です。

constains( )では得られらポイントと範囲の中点までの距離をユークリッド距離で求め、範囲内であればtrueを返します。

intersects( ) では、円の中心から矩形に最も近い点までの距離を計算し、その距離が円の半径以下であれば、円と矩形は重なり合っていると判定します。


//void query(Rectangle range, ArrayList found){
void query(Circle range, ArrayList found){

QuadTreeクラスのqueryクラスの引数をCircleにします。

2-8. Circleによる探査確認

下記通り、draw内にて探査範囲をCircleクラスに書き換えます。


void draw() {
  background(0);
  
  //Rectangle range = new Rectangle(mouseX, mouseY, 100, 100);
  float radius = 100;
  Circle range = new Circle(mouseX, mouseY, radius);
  noFill();
  stroke(0, 255, 0);
  strokeWeight(1);
  //rectMode(CENTER);
  //rect(range.x, range.y, range.w * 2, range.h *2);
  circle(range.x, range.y, radius*2);

  ArrayList foundPoints = new ArrayList();
  qt.query(range, foundPoints);
  
  qt.display();
  for (int i=0; i < foundPoints.size(); i++) {
    stroke(255, 255, 0);
    strokeWeight(15);
    point(foundPoints.get(i).x, foundPoints.get(i).y);
  }
}

2-9. drawにて動くポイントの探査

最後に、動くパーティクルでのQuadTreeを利用した探査方法をまとめます。draw内で動くパーティクルを使用する場合、QuadTree構造で得られた各ポイントをフレームごとに更新していきます。

まず、QuadTreeクラスを更新するための関数として関数clearQuadTreeを作成します。Pointリストを作り直し、分割したか判定するdividedをfalseに戻します。


void clearQuadTree() {
  points = new ArrayList();
  divided = false;
}

今回、サンプルとして使用する動くパーティクルを作成します。下記は、単純に画面の端でバウンドするParticleクラスです。


class Particle {
  float x, y, vx, vy;
  Particle(float theX, float theY) {
    x = theX;
    y = theY;
    vx = random(-3, 3);
    vy = random(-3, 3);
  }

  void update() {
    bounce();
    x += vx;
    y += vy;
  }

  void bounce() {
    if (x > width || x < 0) {
      vx *= -1;
    }
    if (y > height || y < 0) {
      vy *= -1;
    }
  }
}

次に作成したPointクラスをParticleクラスが使用できるよう下記通り書き換えます。


class Point{
  float x,y;
  Particle userData;
  Point(float px, float py){
    x = px;
    y = py;
  }
}

setup(), draw()を下記通り書き換えます。


QuadTree qt;
Rectangle bd;
ArrayList particles;
int particleNum = 100;
int qtCap = 2;
float radius = 100;

void setup() {
  size(900, 900);
  bd = new Rectangle(width/2, height/2, width/2, height/2);
  qt = new QuadTree(bd, qtCap);

  particles = new ArrayList();
  for (int i=0; i < particleNum; i++) {
    particles.add(new Particle(random(width), random(height)));
  }
}

void draw() {
  background(0);

  qt.clearQuadTree();

  for (Particle pa : particles) {
    pa.update();
    qt.insert(new Point(pa.x, pa.y));
  }

  Circle range = new Circle(mouseX, mouseY, radius);
  noFill();
  stroke(0, 255, 0);
  strokeWeight(1);
  circle(range.x, range.y, radius*2);

  ArrayList foundPoints = new ArrayList();
  qt.query(range, foundPoints);

  qt.display();
  for (int i=0; i < foundPoints.size(); i++) {
    stroke(255, 255, 0);
    strokeWeight(15);
    point(foundPoints.get(i).x, foundPoints.get(i).y);
  }
}

このコードの流れは、setupにて複数のパーティクルを作成し、draw内でQuadTreeを更新していきます。探査範囲内rangeにて範囲内radius内に入ったポイントを探し色をつけます。

Recommended Book for Digital arts

Generative Design / Processingで切り拓く、デザインの新たな地平
-Harmut Bohnacker, Benedikt Groß, Julia Laub

2012年に出版されたGenerative Designの日本語版、プログラミングによる視覚表現の解説本。Generative Designのオリジナルライブラリを利用することで、ビギナーにも優しいプログラムコードと解説でジェネラティブデザインが楽しめます。たくさんの美しい作品例と解説により、インスピレーションやリソースとして役立つだけでなく、プログラマーでない人にとっても新しいデザイン体験を与えてくれます。

ーーーーー
► 『Generative Design / Processingで切り拓く、デザインの新たな地平』（Harmut Bohnacker, Benedikt Groß, Julia Laub）

BGD_SOUNDS on bandcamp

BGD_SOUNDSでは、bandcamp上にて、安価で利用できる膨大な著作権フリーのサウンドライブラリーを目指して日々様々な音源ライブラリーを増やしています。音源のほとんどは、192kHzの32bitの高音質にて録音。音楽制作や映像制作など用途に合わせて利用可能です。また、Sound visualization Penplot artも定期的に販売しています。

BGD_CLUB（月額サブスクリプション）も低価格から始めており、すべてのライブラリーにアクセスし自由にダウンロードすることも可能です。

Link / BGD_SOUNDS on bandcamp