第8章：細い縁を調べる前に大きな箱を探す

まずは5歳児にもわかるゲームから

この章で覚える真実は一つだけです。Hit Testing は幾何クエリシステムであって、いくつかの if 文ではありません。

20個のおもちゃを4個の靴箱に分けて入れます。目を閉じ、綿棒で「一番上にある細い青いひも」を探してください。方法は二つあります。すべてのおもちゃを取り出して一つずつ触るか、綿棒がどの靴箱に落ちたかを先に見て、その箱のおもちゃだけを調べ、最後に綿棒とひもの距離を測ります。

先に予想してみてください。青いひもが髪の毛ほど細いとします。子どもがおもちゃの街を10倍に拡大したとき、綿棒がどれくらい近ければ命中でしょうか。許容距離も10倍にすればクリックしやすくなるでしょうか、それとも同じ操作感でしょうか。長方形を45°回転したとき、回転前の大きな箱に触れただけで、本当に長方形へ触れたと断定できるでしょうか。

これが二段階クエリです。第1段階では余分な候補を少し残してもかまいませんが、本当の対象を漏らしてはいけません。第2段階で初めて、塗り、線、ハンドル、コネクター、変換後の本当の幾何を検査します。結果は true/false だけではありません。どれの、どの部位に命中し、どれくらい離れ、ワールド点とローカル点がどこかをツールへ伝えます。

おもちゃを Canvas に置き換える

この比喩には限界があります。本物の靴箱には体積がありますが、2D の AABB は軸に沿った範囲にすぎません。AABB の交差は必要条件であって十分条件ではありません。負の Scale はローカル方向を反転させますが、幅や高さを負の距離にしてよいわけではありません。数学上の幅ゼロの線に面積はなくても、UI は画面上の許容距離によってクリック可能にできます。浮動小数点数も無限精度の定規ではないため、境界判定には epsilon が必要です。

まず誤った直感を捨てる

• 「x <= px <= x + width で十分だ。」 回転、親変換、負の Scale、線分、Bézier が直ちに破綻させます。
• 「ctx.isPointInPath() を直接呼ぶのが一番正確だ。」 命中ルールが Renderer、Context State、ブラウザ環境に固定されます。Node テスト、空間インデックス、SVG/GPU Renderer で再利用できません。
• 「AABB に命中すれば本当に命中している。」 回転した長方形の AABB の角には大きな空白があります。
• 「線のクリックには固定 5 world units を使う。」 Zoom 0.1 では 0.5 px でほぼクリックできず、Zoom 10 では 50 px となって遠くからでも命中します。
• 「最初の候補を返せばよい。」 Spatial Index は Z-Order を保証しません。ページの重なりルールで比較する必要があります。
• 「Bounds を一度キャッシュしたら変えない。」 Shape、親 Transform、Stroke、Geometry が変わると、古い箱によって対象が消えたり幽霊のように命中したりします。

Production backpack

前提となる契約

第4章は可逆な worldToScreen/screenToWorld と、有限かつ正の Camera Scale を提供します。第5章の Shape には Stable ID、親子関係、Z-Order、Local Transform、Geometry Provider があります。第7章からは正規化済み World Point だけが渡されます。GeometryKernel は Canvas API、React、DOM を import しません。

正式な知識

二次元ベクトルは v=(x,y) です。Dot Product a·b=ax·bx+ay·by は射影と角度判定に使えます。二次元 Cross Product のスカラー値 a×b=ax·by-ay·bx の符号は、左右の向き、線分の交差、多角形の巻き方向を示します。距離は差ベクトルの長さです。点から線分までの距離は、点から無限直線までの距離ではありません。まず t=clamp(((p-a)·(b-a))/|b-a|²,0,1) を求め、次に a+t(b-a) を使います。線分の長さがゼロに近いときは点として扱います。

線分交差では、通常の交差、共線の重なり、端点接触を処理します。プロダクトとして、一点を返すのか、区間を返すのか、boolean だけを返すのかも決める必要があります。Polygon Contains には偶奇規則または nonzero Winding を使えます。穴や自己交差多角形には明示的な塗り規則が必要です。二次・三次 Bézier の Narrow Phase には、解析的な最近点、再帰分割、誤差上限付き flattening を使えます。すべての曲線を固定10分割し、精度が同じだと見なしてはいけません。

AABB は {minX,minY,maxX,maxY} で、インデックスと粗い絞り込みに適します。OBB は中心、2本の単位軸、半サイズを持ち、回転対象へより密着しますが交差計算のコストが高くなります。一般的な実装ではローカル幾何の各角を World Matrix で変換し、結果の最小値と最大値から保守的な transformed AABB を作ります。入れ子の Group は定めた行列乗算順で合成します。負の Scale のあとは min/max を並べ直します。逆変換できない行列は診断可能な miss を返すだけにし、NaN を拡散させてはいけません。

Fill の命中は面の内側規則を使います。Stroke の命中は、中心線を「この Shape の変換後の実際の半ストローク幅 + toleranceWorld」だけ膨張させたものに相当し、line cap、join、miter も考慮します。ローカル空間の strokeWidth やローカル距離をワールド許容距離へ直接足してはいけません。均一な Camera なら toleranceWorld = toleranceScreen / abs(cameraScale) です。非均一 View Transform では画面の許容ベクトルを逆行列で変換するか、Screen Space で正確に比較します。Resize/Rotate Handle は通常、画面上で 8〜12 CSS px を保ち、ワールドと一緒に拡縮しません。

Broad Phase のインターフェースが保証するのは「交差する可能性がある全オブジェクト」だけです。実装は線形走査から始め、あとで R-tree、quadtree、BVH に置き換えられます。各 Shape の Geometry Provider は Narrow Phase の containsPoint、distanceToPoint、intersectsRectangle、nearestPoint、outline、snapPoints に答えます。クエリ結果を overlay handle、選択オブジェクトの規則、Z-Order、距離、Stable ID で決定的に並べます。インデックスの返却順が変わってもリプレイ結果は安定します。

根拠と互換性（確認日：2026-08-29）

GeometryKernel は通常の数値構造だけを使い、Node で実行できます。MDN DOMMatrix と DOMMatrixReadOnly.inverse() はブラウザアダプタの参考になります。MDN は逆行列を得られない場合に成分が NaN になり得ると説明しているため、境界で有限性を検証します。Canvas の isPointInPath() と isPointInStroke() は差分テストに使えますが、ドメインの真実ではありません。Renderer を交換しても Kernel のテストはそのまま通るべきです。

この章で積み上げる実装

開始地点： Select Tool がすべての Shape を走査し、回転していない長方形の if で判定します。完了地点： 独立した GeometryKernel が安定したクエリを提供します。線形 Broad Phase を空間インデックスに置き換えても、Narrow Phase と結果の意味は変わりません。

次のファイルとインターフェースを追加します。

• src/engine/geometry/vector.ts：ベクトル、dot、cross、epsilon。
• src/engine/geometry/bounds.ts：AABB、変換、交差。
• src/engine/geometry/providers.ts：Geometry Provider レジストリ。
• src/engine/geometry/GeometryKernel.ts：Broad/Narrow クエリと決定的ソート。
• src/engine/geometry/__tests__/properties.test.ts：回転、負の Scale、退化形状、許容距離の性質。
• tests/browser/hit-tolerance.spec.ts：異なる Zoom で同じ画面距離を検証。

以下の完全な TypeScript カーネルは長方形と折れ線のクエリを実装します。Ellipse/Bézier はあとで Provider を追加するだけで、Tool は変更しません。コードに隠れやすい契約を先に明記します。この教材カーネルの strokeWidthWorld は、Shape Transform では拡縮しないワールド空間の幅です。Entry.bounds はストロークの半分を含む transformed world AABB です。プロダクトが「Shape の拡縮と一緒に Stroke も拡縮する」を選ぶなら、Provider は変換後の本当の outline を先に求め、ワールド許容距離とローカル距離を足してはいけません。例の Camera は回転、平行移動、均一 Zoom だけを含みます。非均一 View Transform では Screen Space で比較します。

export type Vec = Readonly<{ x: number; y: number }>;
export type Aabb = Readonly<{ minX: number; minY: number; maxX: number; maxY: number }>;
export type Mat = Readonly<{ a: number; b: number; c: number; d: number; e: number; f: number }>;
export type Geometry =
  | Readonly<{
      kind: 'rect';
      width: number;
      height: number;
      filled: boolean;
      strokeWidthWorld: number;
    }>
  | Readonly<{
      kind: 'polyline';
      points: readonly Vec[];
      closed: boolean;
      strokeWidthWorld: number;
    }>;
export type Entry = Readonly<{
  id: string;
  z: number;
  world: Mat;
  bounds: Aabb;
  geometry: Geometry;
}>;
export type HitResult = Readonly<{
  id: string;
  part: 'fill' | 'stroke';
  distanceWorld: number;
  worldPoint: Vec;
  localPoint: Vec;
  z: number;
}>;

const EPS = 1e-9;
const dot = (a: Vec, b: Vec) => a.x * b.x + a.y * b.y;
const sub = (a: Vec, b: Vec): Vec => ({ x: a.x - b.x, y: a.y - b.y });
const add = (a: Vec, b: Vec): Vec => ({ x: a.x + b.x, y: a.y + b.y });
const mul = (a: Vec, n: number): Vec => ({ x: a.x * n, y: a.y * n });
const length = (v: Vec) => Math.hypot(v.x, v.y);
export const cross = (a: Vec, b: Vec) => a.x * b.y - a.y * b.x;

export function nearestOnSegment(p: Vec, a: Vec, b: Vec): Vec {
  const ab = sub(b, a);
  const denominator = dot(ab, ab);
  if (denominator <= EPS) return a;
  const t = Math.max(0, Math.min(1, dot(sub(p, a), ab) / denominator));
  return add(a, mul(ab, t));
}

export function invert(m: Mat): Mat | null {
  const det = m.a * m.d - m.b * m.c;
  if (!Number.isFinite(det) || Math.abs(det) <= EPS) return null;
  return {
    a: m.d / det,
    b: -m.b / det,
    c: -m.c / det,
    d: m.a / det,
    e: (m.c * m.f - m.d * m.e) / det,
    f: (m.b * m.e - m.a * m.f) / det,
  };
}

export const transform = (m: Mat, p: Vec): Vec => ({
  x: m.a * p.x + m.c * p.y + m.e,
  y: m.b * p.x + m.d * p.y + m.f,
});

export const expand = (b: Aabb, by: number): Aabb => ({
  minX: b.minX - by,
  minY: b.minY - by,
  maxX: b.maxX + by,
  maxY: b.maxY + by,
});
export const containsAabb = (b: Aabb, p: Vec) =>
  p.x >= b.minX && p.x <= b.maxX && p.y >= b.minY && p.y <= b.maxY;

function pointInPolygon(point: Vec, points: readonly Vec[]): boolean {
  let winding = 0;
  for (let i = 0; i < points.length; i++) {
    const a = points[i],
      b = points[(i + 1) % points.length];
    const side = cross(sub(b, a), sub(point, a));
    if (a.y <= point.y && b.y > point.y && side > EPS) winding++;
    if (a.y > point.y && b.y <= point.y && side < -EPS) winding--;
  }
  return winding !== 0;
}

function narrow(entry: Entry, worldPoint: Vec, toleranceWorld: number): HitResult | null {
  const inverse = invert(entry.world);
  if (!inverse) return null;
  const p = transform(inverse, worldPoint);
  const g = entry.geometry;
  const points: readonly Vec[] =
    g.kind === 'rect'
      ? [
          { x: 0, y: 0 },
          { x: g.width, y: 0 },
          { x: g.width, y: g.height },
          { x: 0, y: g.height },
        ]
      : g.points;
  const worldPoints = points.map((point) => transform(entry.world, point));

  let minimumWorld = Number.POSITIVE_INFINITY;
  const edgeCount = g.kind === 'rect' || g.closed ? points.length : Math.max(0, points.length - 1);
  for (let i = 0; i < edgeCount; i++) {
    const nearest = nearestOnSegment(
      worldPoint,
      worldPoints[i],
      worldPoints[(i + 1) % worldPoints.length],
    );
    minimumWorld = Math.min(minimumWorld, length(sub(worldPoint, nearest)));
  }
  const filled = g.kind === 'rect' ? g.filled : g.closed;
  const inFill = filled && points.length >= 3 && pointInPolygon(p, points);
  const strokeHit = minimumWorld <= g.strokeWidthWorld / 2 + toleranceWorld;
  if (!inFill && !strokeHit) return null;
  return {
    id: entry.id,
    part: inFill ? 'fill' : 'stroke',
    distanceWorld: inFill ? 0 : minimumWorld,
    worldPoint,
    localPoint: p,
    z: entry.z,
  };
}

export interface SpatialQuery {
  atPoint(point: Vec, radiusWorld: number): readonly Entry[];
}

export class GeometryKernel {
  constructor(private readonly index: SpatialQuery) {}

  hitTest(worldPoint: Vec, toleranceScreen: number, cameraScale: number): HitResult | null {
    if (!(cameraScale > EPS) || !Number.isFinite(cameraScale)) return null;
    const toleranceWorld = toleranceScreen / cameraScale;
    const candidates = this.index
      .atPoint(worldPoint, toleranceWorld)
      .filter((entry) => containsAabb(expand(entry.bounds, toleranceWorld), worldPoint))
      .sort((a, b) => b.z - a.z || a.id.localeCompare(b.id));
    for (const entry of candidates) {
      const result = narrow(entry, worldPoint, toleranceWorld);
      if (result) return result;
    }
    return null;
  }
}

Provider の完全な公開契約には次の能力も含まれます。Selection、Snapping、Spatial Index は Renderer ではなく、この契約に依存します。

export interface ShapeGeometryProvider<S> {
  bounds(shape: S): Aabb;
  containsPoint(shape: S, localPoint: Vec): boolean;
  distanceToPoint(shape: S, localPoint: Vec): number;
  intersectsRectangle(shape: S, localRectangle: Aabb): boolean;
  transformedBounds(shape: S, world: Mat): Aabb;
  nearestPoint(shape: S, localPoint: Vec): Vec;
  selectionOutline(shape: S): readonly Vec[];
  snapPoints(shape: S): readonly Vec[];
}

Property test は、見栄えのよい3座標だけでなく「不変条件」に注目します。

import { describe, expect, it } from 'vitest';
import fc from 'fast-check';
import { GeometryKernel, nearestOnSegment } from '../GeometryKernel';

describe('GeometryKernel', () => {
  it('線分上の最近点は常に線分パラメータの範囲内にある', () => {
    fc.assert(
      fc.property(
        fc.double({ min: -1e4, max: 1e4, noNaN: true }),
        fc.double({ min: -1e4, max: 1e4, noNaN: true }),
        (x, y) => {
          const q = nearestOnSegment({ x, y }, { x: 0, y: 0 }, { x: 10, y: 0 });
          expect(q.x).toBeGreaterThanOrEqual(0);
          expect(q.x).toBeLessThanOrEqual(10);
          expect(q.y).toBe(0);
        },
      ),
    );
  });

  it('画面上の許容距離は Zoom が違っても同じである', () => {
    const line = {
      id: 'line',
      z: 1,
      world: { a: 1, b: 0, c: 0, d: 1, e: 0, f: 0 },
      bounds: { minX: 0, minY: 0, maxX: 100, maxY: 0 },
      geometry: {
        kind: 'polyline' as const,
        points: [
          { x: 0, y: 0 },
          { x: 100, y: 0 },
        ],
        closed: false,
        strokeWidthWorld: 0,
      },
    };
    const kernel = new GeometryKernel({ atPoint: () => [line] });
    expect(kernel.hitTest({ x: 20, y: 4 }, 5, 1)?.id).toBe('line');
    expect(kernel.hitTest({ x: 20, y: 0.4 }, 5, 10)?.id).toBe('line');
    expect(kernel.hitTest({ x: 20, y: 0.6 }, 5, 10)).toBeNull();
  });

  it('Shape の Scale はワールド許容距離をローカル許容距離に変えない', () => {
    const scaledLine = {
      id: 'scaled',
      z: 1,
      world: { a: 10, b: 0, c: 0, d: 10, e: 0, f: 0 },
      bounds: { minX: 0, minY: 0, maxX: 100, maxY: 0 },
      geometry: {
        kind: 'polyline' as const,
        points: [
          { x: 0, y: 0 },
          { x: 10, y: 0 },
        ],
        closed: false,
        strokeWidthWorld: 0,
      },
    };
    const kernel = new GeometryKernel({ atPoint: () => [scaledLine] });
    expect(kernel.hitTest({ x: 50, y: 4 }, 5, 1)?.distanceWorld).toBe(4);
    expect(kernel.hitTest({ x: 50, y: 6 }, 5, 1)).toBeNull();
  });
});

pnpm vitest run src/engine/geometry を実行し、DOM 環境なしですべての property run が通ることを確認します。pnpm playwright test tests/browser/hit-tolerance.spec.ts を実行し、Zoom 25%、100%、400% のすべてで線から 4 px の点は命中し、6 px の点は命中しないことを確認します。候補数も記録し、第15章で空間インデックスを交換するときに同じ assertion を使います。

靴箱へ戻りましょう。インデックスが教えるのは「綿棒がこの箱に落ちたかもしれない」ことだけです。Provider が本当のおもちゃの輪郭に触れ、Z-Order が一番上のおもちゃを先に取り出します。絵筆を GPU Renderer に替えても、箱、定規、結果メモは変わりません。

わざと壊してみる

証拠をもって合格する

• Vector、dot、cross、点と線分の距離、線交差、Polygon/Winding、Bézier 方針がそれぞれ独立して定義されている。
• AABB は Broad Phase だけに使い、必要な Narrow Phase には OBB または本当の幾何を使う。
• Transformed Bounds が回転、入れ子、負の Scale、浮動小数点 epsilon を扱う。
• Fill、Stroke Expansion、Handle Geometry が明示的に異なる規則を使う。
• HitResult が ID、part、距離、local/world 点、Z 情報を含む。
• Bounds/Contains/Distance/Intersects/Nearest/Outline/SnapPoints が Canvas Context に依存しない。
• Renderer を削除してもすべての Geometry テストを実行できる。

5歳児に説明する

「ベクトル」「AABB」「ヒットテスト」「空間インデックス」という言葉を使わずに答えてください。

1. なぜ先に靴箱を探すのに、箱を見つけただけではおもちゃを見つけたと言えないのでしょうか。
2. おもちゃの街を拡大しても、なぜ目に見える綿棒の先は同じ太さであるべきでしょうか。
3. 二つのおもちゃが重なったとき、毎回同じものを取るにはどうしますか。
4. 新しい問題です。ひもが小さな一点に縮んだら、定規は「数ではないもの」を出さずにどう測ればよいでしょうか。