The Click Problem

User clicks at (347, 219). Which object did they click?

With 10 objects, loop through all of them. With 10,000 objects, that loop takes too long.

The Naive Approach

First attempt: check every object, every click.

function findClickedObject(mousePos, objects) {
  for (const obj of objects) {
    if (isPointInside(mousePos, obj)) {
      return obj;
    }
  }
  return null;
}

Performance: O(n). Fine for small canvases. Unusable for complex designs.

Problem: We tested every object even when the click was nowhere near most of them.

Bounding Box Optimization

Second attempt: quick rejection with bounding boxes.

function findClickedObject(mousePos, objects) {
  for (const obj of objects) {
    if (!isPointInBounds(mousePos, obj.bounds)) {
      continue;  // Skip expensive test
    }
    if (isPointInside(mousePos, obj)) {
      return obj;
    }
  }
  return null;
}

Better. Bounding box check is fast (4 comparisons). But we still iterate every object.

Enter the Quad-Tree

A quad-tree divides space into quadrants. Each quadrant divides further until reaching a size limit or object count threshold.

var cfg = {
  "id": "qt1",
  "type": "quadtree-demo",
  "bindings": {
    "objectCount": "quadtree.objectCount",
    "depth": "quadtree.depth"
  },
  "width": 500,
  "height": 300
}

Objects: {{quadtree.objectCount}}, Max depth: {{quadtree.depth}}

Click to query. Watch which cells get checked.

Building the Quad-Tree

class QuadTree {
  constructor(bounds, maxObjects = 4, maxDepth = 8) {
    this.bounds = bounds;
    this.maxObjects = maxObjects;
    this.maxDepth = maxDepth;
    this.objects = [];
    this.children = null;
    this.depth = 0;
  }

  insert(obj) {
    if (this.children) {
      const index = this.getChildIndex(obj.bounds);
      if (index !== -1) {
        this.children[index].insert(obj);
        return;
      }
    }

    this.objects.push(obj);

    if (this.objects.length > this.maxObjects &&
        this.depth < this.maxDepth) {
      this.subdivide();
    }
  }
}

Objects that span multiple quadrants stay at the parent level. Objects fully contained in a quadrant descend to that child.

Querying

function query(point) {
  const results = [];

  // Check objects at this level
  for (const obj of this.objects) {
    if (isPointInBounds(point, obj.bounds)) {
      results.push(obj);
    }
  }

  // Recurse into relevant child
  if (this.children) {
    const index = this.getChildIndex({
      x: point.x, y: point.y,
      width: 0, height: 0
    });
    if (index !== -1) {
      results.push(...this.children[index].query(point));
    }
  }

  return results;
}

Performance: O(log n) average case. We only check objects in quadrants the point actually touches.

Point-in-Polygon: The Real Test

The quad-tree gives us candidates. Now we need to test each one precisely.

For polygons, use ray casting:

function isPointInPolygon(point, vertices) {
  let inside = false;
  const n = vertices.length;

  for (let i = 0, j = n - 1; i < n; j = i++) {
    const vi = vertices[i];
    const vj = vertices[j];

    if ((vi.y > point.y) !== (vj.y > point.y) &&
        point.x < (vj.x - vi.x) * (point.y - vi.y) /
                  (vj.y - vi.y) + vi.x) {
      inside = !inside;
    }
  }

  return inside;
}

Cast a ray from the point. Count edge crossings. Odd = inside, even = outside.

Bezier Curves: Approximate and Test

Curved segments complicate things. You can't ray-cast against a bezier directly.

Solution: Flatten curves to line segments for hit testing.

function flattenBezier(p0, p1, p2, p3, tolerance = 1) {
  const points = [p0];

  function subdivide(t0, t1, depth) {
    const mid = (t0 + t1) / 2;
    const pMid = evaluateBezier(mid, p0, p1, p2, p3);
    const pLine = lerp(
      evaluateBezier(t0, p0, p1, p2, p3),
      evaluateBezier(t1, p0, p1, p2, p3),
      0.5
    );

    if (distance(pMid, pLine) > tolerance || depth < 2) {
      subdivide(t0, mid, depth + 1);
      points.push(pMid);
      subdivide(mid, t1, depth + 1);
    }
  }

  subdivide(0, 1, 0);
  points.push(p3);
  return points;
}

The tolerance parameter controls accuracy. Lower = more segments = slower but more precise.

Transform-Aware Hit Testing

Objects have transforms. The quad-tree stores world-space bounds. But point-in-polygon needs local coordinates.

function hitTestObject(worldPoint, obj) {
  // Convert to object's local space
  const localPoint = transformPoint(
    invert(obj.worldMatrix),
    worldPoint
  );

  // Test against local geometry
  return isPointInPolygon(localPoint, obj.localVertices);
}

The inverse matrix converts screen coordinates to object coordinates. Now the polygon test works regardless of rotation or scale.

Z-Order: Front to Back

Multiple objects can overlap. Which one gets the click?

Test in reverse z-order (front to back). First hit wins.

function findTopObject(point, objects) {
  // Assume objects sorted back-to-front
  for (let i = objects.length - 1; i >= 0; i--) {
    if (hitTestObject(point, objects[i])) {
      return objects[i];
    }
  }
  return null;
}

Stroke Hit Testing

Filled shapes: test if point is inside. Stroked shapes: test if point is within stroke width of the path.

function isPointNearPath(point, path, strokeWidth) {
  const threshold = strokeWidth / 2 + 2; // +2 for touch tolerance

  for (const segment of path.segments) {
    const dist = pointToSegmentDistance(point, segment);
    if (dist < threshold) return true;
  }

  return false;
}

The extra pixels make selection feel responsive. Users don't click with pixel precision.

Performance Summary

Approach	100 objects	10,000 objects
Naive loop	0.1ms	10ms
Bounding boxes	0.05ms	5ms
Quad-tree	0.02ms	0.05ms

The quad-tree scales. The naive approach doesn't.

Summary

• Quad-trees partition space for O(log n) queries
• Bounding boxes provide quick rejection
• Ray casting tests point-in-polygon
• Bezier flattening handles curves
• Inverse transforms convert to local space
• Z-order determines which overlapping object wins

Hit testing is invisible when it works. When it's slow, users notice immediately—every mouse move triggers a hover test.

Fast hit testing is the difference between a fluid editor and a laggy one.

Next: Editor Modes →