Chapter 65

矩形分割

miku
miku
2021.11.17に更新

この章では、1つの矩形を用意して、その中を分割して2つの矩形を作り、さらにその矩形から矩形を作り…と再帰的に矩形を分割して領域を生成する方法を扱う。

基本

function setup() {
  createCanvas(windowWidth, windowHeight);
  strokeWeight(2);
  stroke(240);
  noFill();

  divide(0, 0, width, height, 5);
}

function divide(x, y, w, h, n) {
  if (n === 0) {
    rect(x, y, w, h);
    return;
  }

  if (w > h) {
    divide(x, y, w / 2, h, n - 1);
    divide(x + w / 2, y, w / 2, h, n - 1);
  } else {
    divide(x, y, w, h / 2, n - 1);
    divide(x, y + h / 2, w, h / 2, n - 1);
  }
}

divide(x, y, w, h, n)(x, y) ~ (x + w, y + h) の矩形領域を再帰的に n 回分割する。分割位置は横長の矩形なら横50%の位置から縦に、縦長の矩形なら縦50%の位置から横に分割する。n === 0 のときはこれ以上分割しないという意味になるので、渡された矩形領域を描画する。

確率で分割位置を決める

const prob = 0.5;

function setup() {
  createCanvas(windowWidth, windowHeight);
  strokeWeight(2);
  stroke(240);
  noFill();

  divide(0, 0, width, height, 5);
}

function divide(x, y, w, h, n) {
  if (n === 0) {
    rect(x, y, w, h);
    return;
  }

  if (random() < prob) {
    divide(x, y, w / 2, h, n - 1);
    divide(x + w / 2, y, w / 2, h, n - 1);
  } else {
    divide(x, y, w, h / 2, n - 1);
    divide(x, y + h / 2, w, h / 2, n - 1);
  }
}

先程は矩形の縦横長い方を分割していたが、今度は確率依存にする。

分割した片側だけ再帰する

function setup() {
  createCanvas(windowWidth, windowHeight);
  strokeWeight(2);
  stroke(240);
  noFill();

  divide(0, 0, width, height, 10);
}

function divide(x, y, w, h, n) {
  if (n === 0) {
    rect(x, y, w, h);
    return;
  }

  if (w > h) {
    rect(x, y, w / 2, h);
    divide(x + w / 2, y, w / 2, h, n - 1);
  } else {
    rect(x, y, w, h / 2);
    divide(x, y + h / 2, w, h / 2, n - 1);
  }
}

分割した2つ矩形を両方とも更に分割してしまうと矩形分割をしている感がイマイチなくなるので、分割したら片側だけ再帰を行い、もう1つの方はその場で描画してしまう作例。

幅か高さが一定サイズ以下になるまで分割する

function setup() {
  createCanvas(windowWidth, windowHeight);
  strokeWeight(2);
  stroke(240);
  noFill();

  divide(0, 0, width, height, 10);
}

function divide(x, y, w, h, size) {
  if (w <= size || h <= size) {
    rect(x, y, w, h);
    return;
  }

  if (w > h) {
    rect(x, y, w / 2, h);
    divide(x + w / 2, y, w / 2, h, size);
  } else {
    rect(x, y, w, h / 2);
    divide(x, y + h / 2, w, h / 2, size);
  }
}

ユークリッドの互除法

最大公約数を求める方法にユークリッドの互除法というものがあり、2つの自然数である (a, b) の最大公約数は (b, a % b) の最大公約数と一致することを利用した再帰的なアルゴリズムになる。

// 暫定版
function gcd(a, b) {
  if (a < b) {
    [a, b] = [b, a];
  }

  if (a % b === 0) {
    return b;
  }

  return gcd(b, a % b);
}

2つの自然数である (a, b) の最大公約数を求めるための関数 gcd(a, b) を用意する。a < b なら a >= b になるように数を交換する。最大公約数は明らかに b 以下の数になるので、ab で割り切れるなら b が最大公約数になる。割り切れない場合 gcd(b, a % b) を実行し、割り切れるまで再帰的に関数を呼び出す。

function gcd(a, b) {
  if (b === 0) {
    return a;
  }

  return gcd(b, a % b);
}

こちらは先程の暫定版を最適化した gcd() になる。渡した引数が a < b であっても、最初の再帰呼び出しである gcd(b, a % b)a, b の中身がひっくり返るので交換の判定が無くなる上に、b === 0 なら a を返すようにしているので、仮に a, b のどちらかが 0 の場合、0除算でエラーが出ることがない。

a % ba の中にある b の倍数の数を取り除く処理と同等なので、(a, b) を矩形の長辺・短辺にしたときに、矩形から b * b の矩形を作れるだけ作ると、残った矩形は (a % b, b) のサイズになる。そのサイズを新たな (a, b) として b * b の矩形を作れるだけ作る…のように繰り返すと、これはまさしくユークリッドの互除法の可視化になる。

function setup() {
  createCanvas(windowWidth, windowHeight);
  colorMode(HSB, 1);
  noStroke();

  // 最大公約数を求めるための2つの数 (a > b)
  const scale = 30;
  let a = 14 * scale;
  let b = 9 * scale;

  let dw = true; // trueなら横に分割
  let tx = 0; // 今の座標
  let ty = 0;

  while (b !== 0) {
    // aの中でbが幾つ作れるか
    const c = floor(a / b);

    // b*bの矩形を並べる
    for (let i = 0; i < c; i++) {
      fill(random(), 1, 1);
      rect(tx, ty, b, b);
      if (dw) {
        tx += b;
      } else {
        ty += b;
      }
    }

    [a, b] = [b, a % b];

    dw = !dw;
  }
}

矩形分割の作例

const minSize = 10;
let rects, turn, bgColor, fillColor;

function setup() {
  createCanvas(windowWidth, windowHeight);
  rectMode(CENTER);

  turn = -1;
  reset();
}

function reset() {
  turn++;
  if (turn % 2 === 0) {
    bgColor = "#1a1a1a";
    fillColor = "#597dce";
  } else {
    bgColor = "#597dce";
    fillColor = "#1a1a1a";
  }

  rects = [];
  const num = 10;
  const sizeW = ceil(width / num);
  const sizeH = ceil(height / num);
  for (let y = 0; y < num; y++) {
    for (let x = 0; x < num; x++) {
      const rect = Rectangle.create(x * sizeW, y * sizeH, sizeW, sizeH);
      divide(rect);
    }
  }
  const r = dist(0, 0, width / 2, height / 2);
  rects.forEach((rect) => {
    const d = dist(width / 2, height / 2, rect.x, rect.y);
    const delay = map(d, 0, r, 0, 120);
    rect.delay = delay + floor(random(-20, 20));
  });
}

function draw() {
  background(bgColor);
  noStroke();
  fill(fillColor);

  let end = true;
  rects.forEach((r) => {
    if (!r.dead) {
      Rectangle.update(r);
      rect(r.x, r.y, r.width, r.height);
      end = false;
    }
  });
  if (end) {
    reset();
  }
}

function divide(rect) {
  if (rect.width <= minSize || rect.height <= minSize) {
    rects.push(rect);
    return;
  }
  let a, b;
  const w = rect.width;
  const h = rect.height;
  const w0 = floor(rect.width / 2);
  const w1 = rect.width - w0;
  const h0 = floor(rect.height / 2);
  const h1 = rect.height - h0;
  if (rect.height < rect.width || (rect.width === rect.height && random(100) < 50)) {
    a = Rectangle.create(rect.x, rect.y, w0, h);
    b = Rectangle.create(rect.x + w0, rect.y, w1, h);
  } else {
    a = Rectangle.create(rect.x, rect.y, w, h0);
    b = Rectangle.create(rect.x, rect.y + h0, w, h1);
  }
  if (random(100) < 50) {
    const temp = a;
    a = b;
    b = temp;
  }
  rects.push(a);
  divide(b);
}

const Rectangle = {
  create(x, y, width, height, delay = 0) {
    const originalWidth = width;
    const originalHeight = height;
    const scale = 1;
    const scalev = 0.01;
    const dead = false;
    return { x, y, width, height, originalWidth, originalHeight, scale, scalev, dead, delay };
  },

  update(rect) {
    if (0 < rect.delay) {
      rect.delay--;
      return;
    }
    rect.scale -= rect.scalev;
    rect.width = rect.originalWidth * rect.scale;
    rect.height = rect.originalHeight * rect.scale;
    if (rect.scale < 0) {
      rect.scale = 0;
      rect.dead = true;
    }
  },
};

矩形分割の作例 その2

const minSize = 10;
let rects, turn, bgColor, fillColor;

function setup() {
  createCanvas(windowWidth, windowHeight);
  turn = -1;
  reset();
}

function reset() {
  turn++;
  if (turn % 2 === 0) {
    bgColor = "#1a1a1a";
    fillColor = "#597dce";
  } else {
    bgColor = "#597dce";
    fillColor = "#1a1a1a";
  }

  rects = [];
  const num = 10;
  const sizeW = ceil(width / num);
  const sizeH = ceil(height / num);
  for (let y = 0; y < num; y++) {
    for (let x = 0; x < num; x++) {
      const rect = Rectangle.create(x * sizeW, y * sizeH, sizeW, sizeH);
      divide(rect);
    }
  }
  const r = dist(0, 0, width / 2, height / 2);
  rects.forEach((rect) => {
    const d = dist(width / 2, height / 2, rect.x, rect.y);
    const delay = map(constrain(d, 0, r), 0, r, 0, 120);
    rect.delay = delay + floor(random(-20, 20));
  });
}

function draw() {
  background(bgColor);
  noStroke();
  fill(fillColor);

  let end = true;
  rects.forEach((r) => {
    if (r.scale > 0) {
      Rectangle.update(r);
      rect(r.x, r.y, r.width, r.height);
      end = false;
    }
  });
  if (end) {
    reset();
  }
}

function divide(rect) {
  if (rect.width <= minSize || rect.height <= minSize) {
    rects.push(rect);
    return;
  }

  let a, b;
  const w = rect.width;
  const h = rect.height;
  const w0 = floor(rect.width / 2);
  const w1 = rect.width - w0;
  const h0 = floor(rect.height / 2);
  const h1 = rect.height - h0;
  if (rect.height < rect.width || (rect.width === rect.height && random(100) < 50)) {
    a = Rectangle.create(rect.x, rect.y, w0, h);
    b = Rectangle.create(rect.x + w0, rect.y, w1, h);
  } else {
    a = Rectangle.create(rect.x, rect.y, w, h0);
    b = Rectangle.create(rect.x, rect.y + h0, w, h1);
  }
  if (random(100) < 50) {
    const temp = a;
    a = b;
    b = temp;
  }
  rects.push(a);
  divide(b);
}

const Rectangle = {
  create(x, y, width, height, delay = 0) {
    const scale = 1;
    const scalev = -0.02;
    return { x, y, width, height, scale, scalev, delay };
  },

  update(rect) {
    if (rect.delay > 0) {
      rect.delay--;
      return;
    }

    rect.scale += rect.scalev;
    if (rect.scale < 0) {
      rect.scale = 0;
    }
  },
};