shigureni.dev

隙間を円で埋める

3つの円が互いに接していると、その隙間にぴったり収まる4つ目の円が一意に決まる。新しくできた隙間にもまた円が入る。これを再帰でくり返すと、隙間が円で埋め尽くされていく。アポロニウスのギャスケットになる。

接する4円の半径のあいだには代数の関係があり、隙間の円を試行錯誤で「探す」のでなく「計算で出す」ことができる。

接し合う4つの円の曲率 k（半径の逆数 1/r、外接円は符号をマイナスに取る）には、デカルトの円定理

(k₁ + k₂ + k₃ + k₄)² = 2(k₁² + k₂² + k₃² + k₄²)

が成り立つ。k₄ について解くと2次式になり、根が2つ — 隙間に入る小さい円と、3円を外から包む円。中心は曲率を複素数の係数とみなした同じ形の式で出る。だから既存の3円から次の円の半径も中心も即座に求まり、再帰で隙間を埋め続けられる。曲率が整数から始まると、生成される円の曲率もぜんぶ整数になることがある（アポロニウスの整数ギャスケット）。

外円の中に2つの円を左右に並べて互いに接させ、その隙間に入る円をデカルトの円定理で解くと、4つ目が一つ決まる。曲率に中心を掛けた値を複素数として同じ式に通すと、半径だけでなく中心も出る。下は左右の分け方を揺らして、隙間の円が追従するところ。

// 曲率に中心を掛けた値を複素数として扱う。その平方根
const csqrt = (re, im) => {
  const m = Math.hypot(re, im)
  const real = Math.sqrt(Math.max(0, (m + re) / 2))
  const imag = Math.sqrt(Math.max(0, (m - re) / 2))
  return [real, im < 0 ? -imag : imag]
}

// デカルトの円定理を解いて、3円の隙間に入る小さい円を返す
const innerCircle = (a, b, cc) => {
  const k = a.k + b.k + cc.k + 2 * Math.sqrt(Math.max(0, a.k * b.k + b.k * cc.k + cc.k * a.k))
  const ax = a.k * a.x
  const ay = a.k * a.y
  const bx = b.k * b.x
  const by = b.k * b.y
  const dx = cc.k * cc.x
  const dy = cc.k * cc.y
  const productRe = ax * bx - ay * by + (bx * dx - by * dy) + (dx * ax - dy * ay)
  const productIm = ax * by + ay * bx + (bx * dy + by * dx) + (dx * ay + dy * ax)
  const root = csqrt(productRe, productIm)
  return {
    x: (ax + bx + dx + 2 * root[0]) / k,
    y: (ay + by + dy + 2 * root[1]) / k,
    r: Math.abs(1 / k),
    k,
  }
}

const drawCircle = (c, x, y, r, shade) => {
  c.strokeStyle = colors.tint(shade)
  c.beginPath()
  c.arc(x, y, r, 0, Math.PI * 2)
  c.stroke()
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cx = w / 2
  const cy = h / 2
  const outerR = Math.min(w, h) * 0.44
  let t = 0

return () => {
    t += 0.01

// 外円の内側を左右に分ける比率を揺らす
    const split = 0.5 + Math.sin(t) * 0.16
    const leftR = outerR * split
    const rightR = outerR - leftR

// 外接円は曲率の符号をマイナスに取る
    const outer = { x: cx, y: cy, r: outerR, k: -1 / outerR }
    const left = { x: cx - (outerR - leftR), y: cy, r: leftR, k: 1 / leftR }
    const right = { x: cx + (outerR - rightR), y: cy, r: rightR, k: 1 / rightR }
    const inner = innerCircle(outer, left, right)

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
    c.lineWidth = 2

drawCircle(c, outer.x, outer.y, outer.r, 40)
    drawCircle(c, left.x, left.y, left.r, 70)
    drawCircle(c, right.x, right.y, right.r, 70)
    drawCircle(c, inner.x, inner.y, inner.r, 20)
  }
}

左右の円が太ると上の隙間が痩せ、入る円も小さくなる。innerCircle が返すのは半径と中心の両方で、3円の位置から一意に決まるので、揺らしても隙間に張りついたまま動く。

4つ目を入れると、隙間は3つに分かれる（外円と左の円と新しい円、など）。その各隙間にまた円が入る。同じ計算を再帰でくり返せば全部の隙間が埋まる。新しい円を入れたら、それと隣り合う2円とで作る3つの組へ潜る。曲率が小さくなりすぎたら止める。下は外円と左右2円から始めて、隙間を再帰で埋めたもの。回転をかけて全体を見せている。

const csqrt = (re, im) => {
  const m = Math.hypot(re, im)
  const real = Math.sqrt(Math.max(0, (m + re) / 2))
  const imag = Math.sqrt(Math.max(0, (m - re) / 2))
  return [real, im < 0 ? -imag : imag]
}

// 3円の隙間に入る小さい円（デカルトの円定理）
const innerCircle = (a, b, cc) => {
  const k = a.k + b.k + cc.k + 2 * Math.sqrt(Math.max(0, a.k * b.k + b.k * cc.k + cc.k * a.k))
  const ax = a.k * a.x
  const ay = a.k * a.y
  const bx = b.k * b.x
  const by = b.k * b.y
  const dx = cc.k * cc.x
  const dy = cc.k * cc.y
  const productRe = ax * bx - ay * by + (bx * dx - by * dy) + (dx * ax - dy * ay)
  const productIm = ax * by + ay * bx + (bx * dy + by * dx) + (dx * ay + dy * ax)
  const root = csqrt(productRe, productIm)
  return {
    x: (ax + bx + dx + 2 * root[0]) / k,
    y: (ay + by + dy + 2 * root[1]) / k,
    r: Math.abs(1 / k),
    k,
  }
}

// 隣り合う3円の一つを入れ替えて、別の隙間の円を出す
const swapCircle = (a, b, cc, prev) => {
  const k = 2 * (a.k + b.k + cc.k) - prev.k
  if (Math.abs(k) < 1e-9) return null
  const x = (2 * (a.k * a.x + b.k * b.x + cc.k * cc.x) - prev.k * prev.x) / k
  const y = (2 * (a.k * a.y + b.k * b.y + cc.k * cc.y) - prev.k * prev.y) / k
  return { x, y, r: Math.abs(1 / k), k }
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cx = w / 2
  const cy = h / 2
  const outerR = Math.min(w, h) * 0.44
  const leftR = outerR * 0.52
  const rightR = outerR - leftR
  const minR = outerR * 0.012

const outer = { x: cx, y: cy, r: outerR, k: -1 / outerR }
  const left = { x: cx - (outerR - leftR), y: cy, r: leftR, k: 1 / leftR }
  const right = { x: cx + (outerR - rightR), y: cy, r: rightR, k: 1 / rightR }
  const circles = [outer, left, right]

// 隙間の円を入れて、新しくできた3つの隙間へ潜る
  const fill = (a, b, cc, d, depth) => {
    if (depth > 8 || circles.length > 500) return
    if (!d || !Number.isFinite(d.x) || d.r < minR || d.r > outerR) return
    circles.push(d)
    fill(a, b, d, swapCircle(a, b, d, cc), depth + 1)
    fill(a, cc, d, swapCircle(a, cc, d, b), depth + 1)
    fill(b, cc, d, swapCircle(b, cc, d, a), depth + 1)
  }

fill(outer, left, right, innerCircle(outer, left, right), 0)

let t = 0

return () => {
    t += 0.005

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
    c.lineWidth = 1.5

const rot = Math.sin(t) * 0.5
    const co = Math.cos(rot)
    const si = Math.sin(rot)

for (const circle of circles) {
      if (circle.r < minR) continue
      const dx = circle.x - cx
      const dy = circle.y - cy
      const x = cx + (dx * co - dy * si)
      const y = cy + (dx * si + dy * co)
      const shade = Math.min(220, 8 + (outerR / (circle.r + outerR * 0.04)) * 30)
      c.strokeStyle = colors.tint(shade | 0)
      c.beginPath()
      c.arc(x, y, circle.r, 0, Math.PI * 2)
      c.stroke()
    }
  }
}

3つの円から始めて、隙間という隙間が円で埋まる。minR を上げると浅い所で打ち切られて大きな隙間が残り、下げると小さな円が深くまで入る。swapCircle の側は平方根を使わず引き算だけで次の円が出る。隣り合う3円を共有したまま4つ目だけ入れ替える関係になっているので、定理を解き直さなくても済む。