shigureni.dev

近くだけ見る

物を詰めるとき、いちばん素朴な問いは「いま置こうとしている点は、すでに置いた点と近すぎないか」。全部の既存点と比べると、点が N 個あれば N 回。点が増えるたびに重くなる。

盤面を粗いマス（セル）に切って、点を「自分が入るマス」に登録しておくと、この比較が縮む。新しい点の近さを調べたいときは、そのマスとまわりの数マスだけ覗けばいい。遠くのマスは見るまでもなく遠い。

空間ハッシュ（spatial hash）。盤面をマス幅 cell の格子に切り、各点を落ちたマスに登録しておくデータ構造。マス幅を判定したい最短距離 r より少し狭く取ると、距離 r 以内に来る点は必ず自分のマスか隣接 8 マスのどれかに入る。だから全点との総当たり（O(N)）が、近傍 3×3 マスの中だけを見る一定回数の問い合わせに落ちる。

盤面をマスに割って、点を撒く。cell がマスの幅で、cols × rows 枚に切れる。点はまだどのマスとも結びついていない。

格子の上に点が散らばる。各点を自分の入るマスに登録すると、近さの比較がそのマスのまわりだけで済む。座標をマス幅で割って切り捨てると、その点が何列目・何行目のマスにいるかが出る。buckets はマスの数だけの配列で、各マスに「そこへ落ちた点」のリストを溜める。

const buckets = Array.from({ length: cols * rows }, () => [])

for (const p of pts) {
  const cx = Math.floor(p.x / cell)
  const cy = Math.floor(p.y / cell)
  buckets[cy * cols + cx].push(p)
}

登録が済むと、ある点のまわりを見るのは近傍 3×3 マスを覗くだけになる。中心のマスから上下左右に ±1 ずらした 9 枚。盤面の外へはみ出すマスは飛ばす。下は中心を真ん中に固定して、その 3×3 と、そこに登録された点だけを濃く塗ったもの。枠の外の点には触っていない。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cell = 48
  const cols = Math.ceil(w / cell)
  const rows = Math.ceil(h / cell)

const buckets = Array.from({ length: cols * rows }, () => [])
  const pts = Array.from({ length: 80 }, () => ({
    x: Math.random() * w,
    y: Math.random() * h,
  }))
  for (const p of pts) {
    const cx = Math.floor(p.x / cell)
    const cy = Math.floor(p.y / cell)
    buckets[cy * cols + cx].push(p)
  }

const cx = Math.floor(cols / 2)
  const cy = Math.floor(rows / 2)

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

c.fillStyle = colors.tintAlpha(118, 0.18)
  for (let oy = -1; oy <= 1; oy++) {
    for (let ox = -1; ox <= 1; ox++) {
      const nx = cx + ox
      const ny = cy + oy
      if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue
      c.fillRect(nx * cell, ny * cell, cell, cell)
    }
  }

c.fillStyle = colors.tint(78)
  for (const p of pts) c.fillRect(p.x - 1, p.y - 1, 2, 2)

c.fillStyle = colors.tint(28)
  for (let oy = -1; oy <= 1; oy++) {
    for (let ox = -1; ox <= 1; ox++) {
      const nx = cx + ox
      const ny = cy + oy
      if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue
      for (const p of buckets[ny * cols + nx]) {
        c.fillRect(p.x - 2, p.y - 2, 4, 4)
      }
    }
  }

return () => {}
}

問い合わせ点を動かすと、見ているマスもいっしょに動く。下は問い合わせ点（中央の四角）を漂わせて、そのマスを中心にした 3×3 と、その中の点だけを毎フレーム塗り直す。調べているのは常に枠で囲った一角だけで、点が 80 個あっても全体は走査していない。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cell = 48
  const cols = Math.ceil(w / cell)
  const rows = Math.ceil(h / cell)

let qx = w / 2
  let qy = h / 2
  let ax = (Math.random() - 0.5) * 2.4
  let ay = (Math.random() - 0.5) * 2.4

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

return () => {
    qx += ax
    qy += ay
    if (qx < 10 || qx > w - 10) ax = -ax
    if (qy < 10 || qy > h - 10) ay = -ay

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

const cx = Math.floor(qx / cell)
    const cy = Math.floor(qy / cell)

c.fillStyle = colors.tintAlpha(118, 0.18)
    for (let oy = -1; oy <= 1; oy++) {
      for (let ox = -1; ox <= 1; ox++) {
        const nx = cx + ox
        const ny = cy + oy
        if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue
        c.fillRect(nx * cell, ny * cell, cell, cell)
      }
    }

c.fillStyle = colors.tint(78)
    for (const p of pts) c.fillRect(p.x - 1, p.y - 1, 2, 2)

c.fillStyle = colors.tint(28)
    for (let oy = -1; oy <= 1; oy++) {
      for (let ox = -1; ox <= 1; ox++) {
        const nx = cx + ox
        const ny = cy + oy
        if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue
        for (const p of buckets[ny * cols + nx]) {
          c.fillRect(p.x - 2, p.y - 2, 4, 4)
        }
      }
    }
    c.fillRect(qx - 3, qy - 3, 6, 6)
  }
}

問い合わせ点が盤面を漂っても、濃く塗られるのはそのときの 3×3 マスとその中の点だけで、残りは薄いまま動かない。点の数が増えても、近さを調べる相手は枠で囲った 9 マスの中身に限られる。