Command Palette

Search for a command to run...

Hectal
PHASE 12Advanced ~28 min· topic 3 of 7

Topic 12.3

Hit-Testing: Clicking Things on a Canvas

In one line

A canvas draws pixels and keeps no shapes, so it cannot tell you what was clicked. You find the mark under the pointer yourself, with the browser's shape test, a hidden colour canvas, a quadtree or a Delaunay diagram.

0/7 · 0%

Think of it like this

A paper map with a pin in every town. If a friend points and asks "which town is this?", you look at the spot and decide. The map does not answer. A page with SVG is a map where every town answers for itself. A canvas is the paper: you keep the list of towns and their places, and do the looking.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

hit-test
Finding which mark is under a given point.
Path2D
A shape you can store, draw and ask questions about.
colour picking
Drawing marks on a hidden canvas in id-colours, then reading the colour at the pointer.
anti-aliasing
Blending a shape's edge pixels with the background so edges look smooth.

Step by step

01Ask the browser

The first example draws Lumen's 25 stations with a Path2D each, and stationAt(x, y) asks isPointInPath from the last mark to the first. The centre of Quay gives Market: the circles overlap (13 pixels apart, radii 10.1 and 13.1) and Market is drawn later. A point 8 pixels further from Market gives Quay. Far away, outside the canvas and NaN all give null: NaN does not throw, it is just in no path.

02Look at the pixels

The second example draws four circles twice, the second time on a hidden canvas in colours 1 to 4 (almost black, so it looks black). pick reads one pixel, rejects it unless its alpha is 255, and turns the colour back into an index.

03Search by distance

The third example asks the same questions of a quadtree, a plain loop and Delaunay over 200,000 points: all agree. On the machine this was checked on, a lookup took about 2 to 4 milliseconds for the loop, 7 to 10 microseconds for the quadtree and 26 to 55 for Delaunay across runs (shown on the page: yours will differ). A tiny radius, an empty tree or NaN return undefined: always handle it.

04Choose by what you have

Hundreds of shapes: isPointInPath. Thousands of complex shapes: colour picking. Thousands of dots: a quadtree. A target is always wanted: Delaunay. Add a bigger reach for touch.

Try it yourself

  1. 1

    Bigger circles, bigger overlap

    In the first example, change the radius range [0, 16] to [0, 30]. Quay's radius becomes 19.0, the centre of Quay still gives Market, Quay, 8 px further from Market than its centre now gives Market too (Market's bigger circle reaches it), and Quay, 30 px away now gives Mill: bigger marks catch the pointer from further away.

  2. 2

    Test the first mark first

    In the first example, change the loop header for (let i = marks.length - 1; i >= 0; i--) { to for (let i = 0; i < marks.length; i++) {. The centre of Quay now answers Quay, although Market is drawn on top of it: the hover highlights a circle that is under another one. The order of the loop is the stacking rule.

  3. 3

    Take the dots away

    In the third example, change const N = 200000; to 20. The quadtree and the brute-force loop both say nothing within 10 pixels, because 20 points leave most of the picture empty, while Delaunay still names a point (point 0, point 18, point 5) because it has no radius. Use Delaunay only with a distance check.

Code & diagrams

isPointInPath on 25 stations New tab

Move the pointer over the stations: the hovered one turns orange and its name appears. Quay and Market overlap, so the later-drawn Market wins where they cross.

Preview

Press Run to see the page.

Console

Nothing logged yet.

Expected console output

Quay is drawn with radius 10.1 (12 docks)
the centre of Quay -> Market
Quay, 8 px further from Market than its centre -> Quay
Quay, 30 px away -> null
far from every station -> null
outside the canvas -> null
a point that is NaN -> null
every mark under the centre of Quay: Quay, Market
distance between Quay and Market: 13.0 px, radii 10.1 + 13.1
Colour picking with a hidden canvas New tab

The dashed canvas is the hidden one, shown so you can see it: its colours are ids 1 to 4, so it looks black. The alpha check in `pick` is explained in Break it.

Preview

Press Run to see the page.

Console

Nothing logged yet.

Expected console output

on Quay only: Quay
where Quay and Market overlap: Market
on Chapel: Chapel
empty space: null
outside the canvas: null
A quadtree and Delaunay over 200,000 points New tab

The timings appear on the page, not in the Console, because they change with the machine. The pointer uses a reach of 24 for touch and 6 for a mouse.

Preview

Press Run to see the page.

Console

Nothing logged yet.

Expected console output

at (100, 100) quadtree within 10 px: point 146783 | brute force: point 146783 | Delaunay nearest: point 146783 | quadtree and brute force agree: true
at (240, 120) quadtree within 10 px: point 94821 | brute force: point 94821 | Delaunay nearest: point 94821 | quadtree and brute force agree: true
at (400, 20) quadtree within 10 px: point 22090 | brute force: point 22090 | Delaunay nearest: point 22090 | quadtree and brute force agree: true
a radius of 0.01 finds: undefined
a radius of Infinity finds the nearest point anywhere: point 88865
an empty tree finds: undefined
a NaN position finds: undefined

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Trust the edge pixels

In the second example, delete the line if (a !== 255) return null;, and at the end add const seen = new Set(); for (let deg = 0; deg < 360; deg += 3) seen.add(pick(190 + 28 * Math.cos((deg * Math.PI) / 180), 50 + 28 * Math.sin((deg * Math.PI) / 180))); console.log("names found around Chapel's edge:", [...seen].join(", "));.

terminal
$ Console
── what you'll see ──
names found around Chapel's edge: , Market, Chapel

Myth vs fact

Myth

Colour picking is exact because the pixel colour is exact.

Fact

Only at pixels with full alpha. Shape edges are blended, and blended colours decode to wrong ids.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

  • ▸

    getImageData reads back from the GPU and can stall. Create the hidden canvas's context with { willReadFrequently: true }, as the example does, and read one pixel, never the whole canvas, per move. The hidden canvas must match the visible one's size and pixel ratio. Mind the pixel ratio: getImageData and isPointInPath take positions in the canvas's own pixels, not CSS pixels. Checked: after ctx.setTransform(2, 0, 0, 2, 0, 0) (what Topic 11.4's setupCanvas does on a 2x screen) a circle drawn at (50, 50) answers isPointInPath at (100, 100) and not at (50, 50). On a high-density screen multiply the pointer position by the ratio before you ask. The examples in this topic use a plain canvas, so nothing needs converting there.

Remember this

  1. 1

    The problem this solves: an SVG <circle> can have a click handler because it is an element. A canvas dot is only pixels: the browser reports that the pointer is at (212, 87) and nothing more. Hit-testing is working out which mark is at that point.

  2. 2

    Way 1: ask the browser. Keep each mark as a Path2D and call ctx.isPointInPath(path, x, y) (isPointInStroke for outlines). It is exact for any shape, but loops over all marks per pointer move: fine for hundreds, slow for tens of thousands. Test the last drawn mark first: it is on top.

  3. 3

    Way 2: colour picking. Draw every mark again on a hidden canvas, each in a unique colour that encodes its id (24 bits of RGB give 16.7 million ids). getImageData(x, y, 1, 1) there returns the colour under the pointer, which is the id: one read per move, whatever the mark count. The trap is anti-aliasing: at a shape's edge the browser blends the colour with what is behind it, and the blend decodes to a wrong id. Trust only pixels with alpha 255.

  4. 4

    Way 3: a quadtree. d3.quadtree(points, x, y) splits the plane into nested squares. tree.find(x, y, radius) returns the nearest point within the radius, or undefined, looking at a few squares instead of every point, so 200,000 points answer in microseconds. Build it once when the data changes, not on every move.

  5. 5

    Way 4: Delaunay. d3.Delaunay.from(points, x, y).find(x, y) returns the index of the nearest point anywhere: there is no radius, so some point is always the answer. Check the distance yourself if far away should mean nothing.

  6. 6

    Reach, overlap and touch. A mouse can aim at a 3-pixel dot, a finger cannot: use a reach of about 8 pixels for a mouse and 24 for touch (event.pointerType). Where marks overlap, choose a rule: topmost wins (isPointInPath, colour picking) or nearest centre wins (quadtree). Convert the pointer to canvas coordinates first, because the canvas may be shown at a different size from its pixel grid.

Explain it without notes

01

Why can you not add a click handler to one dot on a canvas?

02

Compare isPointInPath and colour picking: when would you choose each?

Practice

01

Write stationAtPoint(stations, x, y, reach) using a quadtree built inside it, returning the station or null.

02

In the second example, make the hover text say edge when the pixel is partly transparent, nothing when empty, and the name only when alpha is 255.

Trade-offs

  • ↔

    isPointInPath is exact and simple but loops over all marks. Colour picking and a quadtree are faster at scale but need more memory (a second canvas, a tree) and care. A bigger reach makes marks easier to hit and close marks harder to tell apart.

Done when you can

  • I can explain why a canvas has no click events for marks.

  • I can hit-test with isPointInPath, and know it loops over all marks.

  • I can build a colour-picking canvas and I check alpha 255.

  • I can use quadtree.find with a reach and handle undefined.