서클 패킹

Circle packing

원들이 서로 겹치지 않는 한도까지 계속 자라나며 빈 공간을 빼곡히 채우는 알고리즘.

다른 이름: Circle packing algorithm
···
js
const c = document.createElement('canvas');
document.body.appendChild(c);
c.style.width = '100%'; c.style.height = '100%';
const ctx = c.getContext('2d');
const cs = getComputedStyle(document.documentElement);
const palette = [cs.getPropertyValue('--accent').trim(), cs.getPropertyValue('--accent-2').trim(), cs.getPropertyValue('--accent-3').trim()].map(x => x || '#5b5bf7');
let w, h;
function resize() {
  const dpr = Math.min(devicePixelRatio || 1, 2);
  w = innerWidth; h = innerHeight;
  c.width = w * dpr; c.height = h * dpr;
  ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
}
addEventListener('resize', resize);
resize();

const MAX = 240;
const circles = [];
function tryAdd() {
  if (circles.length >= MAX) return;
  for (let i = 0; i < 10; i++) {
    const x = Math.random() * w, y = Math.random() * h;
    let ok = true;
    for (const cir of circles) if (Math.hypot(x - cir.x, y - cir.y) < cir.r + 3) { ok = false; break; }
    if (ok) { circles.push({ x, y, r: 1.5, col: palette[circles.length % palette.length] }); return; }
  }
}
function step() {
  for (const cir of circles) {
    let can = cir.x - cir.r > 0 && cir.x + cir.r < w && cir.y - cir.r > 0 && cir.y + cir.r < h;
    if (can) for (const o of circles) { if (o === cir) continue; if (Math.hypot(cir.x - o.x, cir.y - o.y) < cir.r + o.r + 0.6) { can = false; break; } }
    if (can) cir.r += 0.18;
  }
  tryAdd();
}
function draw() {
  ctx.fillStyle = '#0d0d12'; ctx.fillRect(0, 0, w, h);
  for (const cir of circles) {
    ctx.beginPath(); ctx.arc(cir.x, cir.y, cir.r, 0, 7);
    ctx.fillStyle = cir.col; ctx.globalAlpha = 0.85; ctx.fill();
    ctx.globalAlpha = 1; ctx.strokeStyle = '#0d0d12'; ctx.lineWidth = 1.5; ctx.stroke();
  }
}
for (let i = 0; i < 160; i++) step(); // 미리 패킹을 진행해서 처음부터 빼곡하게 보이도록
draw();
(function loop() { step(); draw(); requestAnimationFrame(loop); })();

과정은 단순합니다. 무작위 위치에 아주 작은 원을 하나 심고, 다른 원이나 화면 경계에 닿을 때까지 반지름을 조금씩 키웁니다. 더 자랄 수 없으면 성장을 멈추고, 그 사이 계속 새로운 작은 원을 빈 곳에 심어 넣습니다. 이 과정을 반복하면 큰 원들 사이의 좁은 틈까지 작은 원들이 스며들어 채우는, 데이터 시각화의 "버블 차트"와 닮은 빽빽한 모자이크가 만들어집니다.

원 사이의 겹침 검사가 원 개수의 제곱에 비례해 느려지기 때문에(모든 쌍을 비교), 실무에서는 공간을 격자로 나눠 가까운 원만 검사하는 최적화를 씁니다. 이 데모는 개수를 제한해서 최적화 없이도 실시간으로 도는 정도로 유지했습니다.

포스터의 배경 텍스처, 데이터의 비율을 원 크기로 표현하는 버블 차트, 유기적인 로고 배경에 씁니다. 원마다 색을 다르게 주면 그 자체로 장식적인 패턴이 됩니다.

언제 쓰나

포스터·배경의 장식적 텍스처, 비율을 원 크기로 보여주는 버블 차트에. 원 개수가 많아지면 공간 분할로 겹침 검사를 최적화하세요.