PHASE 8Intermediate ~23 min· topic 3 of 7

Topic 8.3

Finding the Nearest Point

In one line

A pointer is never exactly on a data point. A bisector finds the nearest day on sorted data in a few steps, a Delaunay triangulation finds the nearest dot of a scatter plot, and unsorted data gives a wrong answer with no error.

Think of it like this

Finding house number 87 on a long street where the numbers go up in order. You do not walk past every door. You open the door in the middle, see 150, so you know 87 is in the first half, and halve again. With 300 houses, nine looks at most are enough. If the numbers were scrambled, the same method would take you to a wrong house and nothing would warn you.

Words you'll meet

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

bisector: A D3 helper for binary search in an array sorted by an accessor.
binary search: Finding a value in sorted data by repeatedly halving the range.
sorted: Arranged so each item is not smaller than the one before. Binary search needs this.
Delaunay triangulation: A way to connect points into triangles so that nearest-point searches are fast. d3.Delaunay builds it.

Step by step

01Turn x into a date, then into a row

x.invert(px) turns the pointer's x (in chart units, Topic 8.1) into a date. bisect.center(rows, date) turns the date into an index. The row is rows[index]. These three steps are the middle of every tooltip in this phase.

pointer to rowwhole filejs

const [px] = d3.pointer(event);
const date = x.invert(px);
const d = rows[d3.bisector((r) => r.date).center(rows, date)];

02Check the edges, the tie and the gap

The first example prints what left and center do at noon, before the first day and after the last day. Then it removes ten days and asks for a day in the hole: the answer is a day five days away, until a distance limit says "no data here".

03Break the order

The second example glues the year's two halves together in the wrong order, and shuffles it. For the pointer on 10 March the bisector says 30 June and 19 January with no complaint. Sorting fixes it.

04Switch to a 2D search for scatter plots

The third example uses d3.Delaunay on temperature against rides, compares pixel space with raw data units, and adds a distance limit.

Switch to a 2D search for scatter plotsdiagram

Rendering diagram…

Try it yourself

1
Move the tie
In the first example, change "2025-01-05T12:00Z" to "2025-01-05T11:59Z". center now answers 2025-01-05: the tie rule only matters at exactly noon.
2
Widen the gap limit
Change 1.5 to 8. On 15 January, 5 days from the next row, the example now prints a date instead of no data here: a limit that is too big hides the hole again.

Code & diagrams

Bisector: ties, edges, gaps and empty data New tab

Console

(nothing was printed)

Expected console output

rows: 59 | first: 2025-01-01 | last: 2025-02-28
2025-01-05T11:00Z | left -> 2025-01-06 | center -> 2025-01-05
2025-01-05T13:00Z | left -> 2025-01-06 | center -> 2025-01-06
2025-01-05T12:00Z | left -> 2025-01-06 | center -> 2025-01-06
before the first day: left -> 0 | center -> 0
after the last day:   left -> 59 (rows.length is 59) | center -> 58
15 Jan has no row, nearest is 2025-01-20
with a limit of 1.5 days: no data here | 2025-01-08
empty array: left 0 center 0 -> rows[0] is undefined

Unsorted data: the silent wrong answer New tab

No error and no warning anywhere: the wrong list looks exactly like the right one until you compare it with the truth.

Console

(nothing was printed)

Expected console output

sorted          bisector says 2025-03-10 | truth is 2025-03-10
halves swapped  bisector says 2025-06-30 | truth is 2025-03-10
shuffled        bisector says 2025-01-19 | truth is 2025-03-10
sorted? true false false
wrong answers for the swapped list: 182 of 365
after sorting -> 2025-03-10

A scatter plot: Delaunay, pixel space and a distance limit New tab

Console

(nothing was printed)

Expected console output

pointer (300, 100) is 16.4 C and 2880 rides
nearest in pixels:     2025-04-09 (16.7 C, 2709 rides) | 14 px away
nearest in data units: 2025-04-23 (16.9 C, 2883 rides) | 17 px away
empty corner (5, 5): find says row 359 -> 197 px away | with a 30 px limit: -1
on the cloud (300, 100) with a 30 px limit: 98
empty list: NaN | one point: 0
two identical points, asking at each of the three: 0, 0, 2
quadtree.find with a radius: 2025-04-09 | in an empty corner: 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

Use left instead of center

In the first example, add console.log(fmt(rows[left(rows, at("2025-04-01"))].date)); as the first line after the console.log("rows:" …) line, a pointer after the last day.

terminal

$ Console

── what you'll see ──

Uncaught TypeError: Cannot read properties of undefined (reading 'date')

Myth vs fact

Myth

A bisector finds the nearest value in any array.

Fact

Only in an array already sorted by the accessor. On unsorted data it returns an index and no error.

Myth

The nearest day is always the right answer to show.

Fact

Over a hole in the data the nearest day can be days away. Add a distance limit and say "no data here".

Pro corner

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

▸
bisector.center is left plus one comparison (d3-array bisector.js): it takes the insertion index i and answers i - 1 only when the previous row is strictly closer, so an exact tie goes to i, the later day. That is why noon went to 6 January in the first example.
▸
Hovering 60 times a second on 365 days costs about nine comparisons per event. A linear find over 365 rows would still be fast; the bisector matters at 100,000 points (about 17 comparisons), and the Delaunay index at tens of thousands of dots.
▸
A Delaunay index is built once per scale: after a zoom or a resize the pixel positions change, so rebuild it (or build it in data space and convert the pointer, accepting the distortion shown in the third example).

Remember this

1
The problem this solves: the pointer is at x = 312 pixels. Which day is that? And which data row is closest? You must turn a position into a row, quickly enough to do it on every pointermove, which can fire 60 times a second.
2
**d3.bisector is the street method.** d3.bisector((d) => d.date) makes a binary search over an array sorted by that accessor. .left(rows, date) and .right(rows, date) return an insertion index (where the date would fit); .center(rows, date) returns the index of the closest row, which is what you want under a pointer. On 365 rows it takes about nine comparisons instead of 365.
3
The edges and the ties. Before the first day center returns 0, after the last day the last index. left returns rows.length after the last row, and rows[rows.length] is undefined, the usual cause of "cannot read properties of undefined" on the right edge. A pointer exactly halfway between two days goes to the later day. An empty array gives 0 and rows[0] is undefined: check for empty data before you draw.
4
Gaps. If ten days are missing, a pointer over the gap snaps to a day five days away, and the tooltip looks as if that day belongs to the pointer. Compare the distance and show "no data here" when it is above a limit. The first example does this with a limit of 1.5 days.
5
Unsorted data is the silent wrong answer. Binary search assumes the order and never checks it. With two halves of the year glued together the wrong way round, center still returns an index, with no error and no warning, and the tooltip shows the wrong day (the second example: 182 of 365 answers wrong). Typical causes: two files concatenated, dates stored as text and sorted as text, rows from a Map. Sort once after loading, and check sortedness while developing.
6
Scatter plots have no order. Dots at (temperature, rides) cannot be binary-searched along one axis. d3.Delaunay.from(points).find(x, y) builds a triangulation once and then finds the nearest point in a few steps; d3.quadtree().find(x, y, radius) does the same with a maximum distance. Build the index in pixel space (after the scales), so a pixel counts the same left-right and up-down. find always answers, even 197 pixels away, so add your own limit: 30 pixels, 44 for touch. Two edge cases are printed in the third example: on an empty list find answers NaN (not -1), so check the length first, and when two points are identical it answers the first of them.

Explain it without notes

Why does bisector.center give the day under the pointer, but bisector.left can crash on the right edge?

What happens if you call a bisector on unsorted data, and why is that worse than an error?

Why build the Delaunay index in pixel space?

Practice

Write nearestDay(rows, date, maxDays) that returns the nearest row or null, and handles an empty array.

Write isSortedBy(rows, accessor) and use it to throw a clear error Rows must be sorted by date before building a chart.

Trade-offs

↔
A bisector is the fastest and simplest for ordered x, but only for one axis and only on sorted data. Delaunay and quadtree work in 2D but must be rebuilt when scales change.

Done when you can

I can find the data row under the pointer with x.invert and bisector.center.
I can say what left, right and center return at the edges and at a tie.
I can show why unsorted data gives a wrong answer with no error, and sort or check to prevent it.
I can find the nearest dot of a scatter plot with Delaunay in pixel space, and add a distance limit.

Command Palette

Words you'll meet

Step by step

01Turn x into a date, then into a row

02Check the edges, the tie and the gap

03Break the order

04Switch to a 2D search for scatter plots

Try it yourself

Move the tie

Widen the gap limit

Code & diagrams

Break it on purpose

Use left instead of center

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can