A dot-to-dot looks like the simplest printable there is. Then you try to generate one and find three separate problems:
- Which points become dots? Too few on the T. rex's jaw and it turns into a potato. Too many on its claws and the rest of the outline gets none.
- How do you offer 20, 50 or 100 dots of the same picture without hand-placing every version?
- Where does each number go? A number that sits nearer to dot 18 than to dot 17 will send a six-year-old the wrong way.
I built the dot to dot printables on Toggle9 with 17 pictures: 10 dinosaurs, a Pteranodon and 6 Christmas pictures. You pick a picture, a count (20, 30, 50, 75 or 100 dots) and how to count (1s, 2s, 5s, 10s, or the alphabet in capitals or small letters). Here's the same T. rex at three counts, made by the code in this post:
The work is split in two. A Python build step turns each drawing into a ranked list of outline points, once. The browser then picks the dots and places the numbers each time you change a setting. The code below is trimmed from the real files, but the logic is unchanged.
Step 1: find the outline
The source is a line drawing: black lines on white. The dots should follow the outer outline. Everything inside it (the eye, the mouth, the arm) stays as a printed line, so the finished picture still looks like a T. rex.
Finding the outer outline of a line drawing is harder than it sounds, because a line drawing has gaps where lines nearly meet. A flood fill from the edge of the image would leak through the gap under the jaw and into the body. So the build step first thickens the lines a little to close the gaps, floods from the border, and then shrinks the result back:
def silhouette(a, close=4):
g = grow(a, close) # thicken lines by 4 px: small gaps close
lab, sizes = components(~g) # label the empty regions
border = set(np.unique(np.concatenate([lab[0], lab[-1], lab[:, 0], lab[:, -1]]))) - {0}
sil = ~np.isin(lab, list(border)) # everything not reachable from the edge
sil = shrink(sil, close) # back to the ink's real outer edge
lab2, sz2 = components(sil); sz2[0] = 0
return lab2 == sz2.argmax() # keep the biggest piece
Step 2: trace it
Now there's a solid shape. A Moore-neighbour trace walks round its edge: from the current edge pixel, look at the 8 neighbours clockwise, starting just after the one you came from, and step to the first one that's inside the shape. Stop when you're back at the start.
D = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
cur, back = start, 6 # start at the top-left pixel; west of it is outside
out = [cur]
while True:
for k in range(1, 9):
j = (back + k) % 8
y, x = cur[0] + D[j][0], cur[1] + D[j][1]
if inside(y, x):
oy, ox = cur[0] + D[(j - 1) % 8][0], cur[1] + D[(j - 1) % 8][1]
back = D.index((oy - y, ox - x)) # remember the last outside pixel we looked at
cur = (y, x); break
if cur == start: break
out.append(cur)
The trace is resampled every 3 pixels and lightly smoothed, so the outline doesn't have a pixel staircase. Then there's one detail that's easy to miss. The trace runs along the outer edge of a 9-pixel line, so every point gets moved inward by half a line width. Otherwise the dots float just outside the drawing.
Step 3: rank every point by how much it matters
This is the step that makes "any count from 20 to 100" possible. Instead of choosing 50 dots, the build step ranks every point on the outline, using the Visvalingam–Whyatt algorithm.
For each point, take the triangle it forms with its two neighbours. A small triangle means removing the point barely changes the shape. Repeatedly remove the point with the smallest triangle, recompute its two neighbours, and record the order things were removed in. The last points to go are the ones the shape can't do without: the tip of the snout, the corner of the tail.
def importance(p):
n = len(p)
prev = [(i - 1) % n for i in range(n)]; nxt = [(i + 1) % n for i in range(n)]
area = lambda i: abs((p[prev[i]][0] - p[i][0]) * (p[nxt[i]][1] - p[i][1])
- (p[nxt[i]][0] - p[i][0]) * (p[prev[i]][1] - p[i][1])) / 2
alive = [True] * n; cur = [area(i) for i in range(n)]
h = [(cur[i], i) for i in range(n)]; heapq.heapify(h)
order = np.zeros(n, int); r = 0; last = 0.0
while h and r < n - 3:
a, i = heapq.heappop(h)
if not alive[i] or a != cur[i]: continue # stale heap entry
last = max(last, a) # a point can't be worth less than the one removed before it
alive[i] = False; order[i] = r; r += 1
pi, ni = prev[i], nxt[i]; nxt[pi] = ni; prev[ni] = pi
for j in (pi, ni):
cur[j] = max(area(j), last); heapq.heappush(h, (cur[j], j))
...
The last = max(...) line is a common fix for Visvalingam–Whyatt. Without it, removing a point can make a neighbour's triangle smaller than the one just removed, and the ranking stops matching what you see.
The build keeps the 300 highest-ranked points per picture, in order round the outline, and writes them to a JSON file with each point's rank. The inner lines go in the same file as an SVG path.
Step 4: pick the dots in the browser
At run time, picking 50 dots could be as simple as "the 50 highest-ranked points". That nearly works. The problem is detail: a claw or a row of spines has lots of sharp corners, so it ranks highly and soaks up the dots. Ten dots on one claw and a straight run of back with none.
So the picker takes points in rank order but skips any point too close to one it already has. It starts with a minimum gap of the outline's length ÷ (n × 1.6), and relaxes the gap by 15% until n points fit:
export function pick(pts, n) { // pts: [x, y, rank]
const N = pts.length; if (n >= N) return pts.map((_, i) => i);
let L = 0;
for (let i = 0; i < N; i++) { const a = pts[i], b = pts[(i + 1) % N]; L += Math.hypot(b[0] - a[0], b[1] - a[1]); }
const order = pts.map((_, i) => i).sort((a, b) => pts[a][2] - pts[b][2]);
let dmin = L / (n * 1.6);
for (;;) {
const got = [];
for (const i of order) {
const p = pts[i];
if (got.every(j => Math.hypot(pts[j][0] - p[0], pts[j][1] - p[1]) >= dmin)) got.push(i);
if (got.length === n) return got.sort((a, b) => a - b); // back in outline order
}
dmin *= 0.85;
}
}
Sorting the result by index puts the dots back in order round the outline, so dot 1 to dot n traces the shape.
Step 5: place the numbers
This took the most work, and it's the part people notice. Each number needs a spot that's:
- next to its own dot, on the outside of the shape where possible,
- not on top of another number or another dot,
- not across a line the child will draw between two dots,
- not on the drawing's inner lines,
- and clearly nearer its own dot than any other.
The placer tries 12 angles around the outward direction at 3 distances, and scores each spot. Lower is better:
| Problem | Cost |
|---|---|
| Overlaps a number already placed | 1,000 |
| Touches another dot | 500 |
| Closer to another dot than to its own | 200 |
| Crosses a line between two dots | 80 |
| Nearly as close to another dot (within 1.35×) | 60 |
| On one of the drawing's inner lines | 30 |
| Turned away from straight out, or pushed further out | a little, growing with the angle and distance |
Crowded dots are placed first, while there's still room around them. The 60-point rule is the one I added after watching the output: a number can be technically closest to its own dot and still look like it belongs to the next one. To check it was worth having, I ran today's code with and without that rule at 50 dots across all 17 pictures. Without it, 24 of 850 numbers are unclear. With it, 2.
Step 6: test every combination
There are 17 pictures, 5 counts and 6 ways of counting, and phones show the numbers up to 2× bigger than print. That's too many combinations to check by eye, so the tests check all of them:
test('the numbers never sit on another number or another dot, printed or at the phone sizes', () => {
for (const k of KEYS) for (const n of DOTS) for (const f of (n <= 30 ? [1, 2] : n <= 50 ? [1, 1.3] : [1])) {
const Lo = layout(A[k], '1', n, Math.min(190 / A[k].w, 230 / A[k].h) / f);
// ...every pair of number boxes must not overlap, and no number box may cover another dot
}
});
Another test checks that every picture at every count has the right number of dots, in outline order, and that no two dots are closer than 2.5 dot radii. One Christmas picture failed that at first: the first candy cane was so tall and thin that 100 dots crowded together on it. I redrew it, and it passed.
What I'd do differently
- Start from silhouettes, not detailed art. I first tried feeding in the site's detailed coloring-page art. The cute Spinosaurus's outline leaked into its body, and the baby dinosaur lost its egg. Clean, simple line drawings work far better.
- Write the "can a child read this?" test first. Overlap tests pass long before the output is good enough for a child to use. The "which dot does this number belong to?" check is the one that matters most.
- Keep the slow work at build time. Tracing and ranking run once per drawing in Python. The browser only sorts 300 points and scores a few thousand candidate spots, so changing the count needs no server at all.
You can try it at Toggle9's dot to dot printables. It prints free with no sign-up, with an answer page if you want one.
Have you built anything that puts labels on a drawing or map? I'd like to hear what scoring you ended up with. Label placement turned out to be the most interesting part of this.
Top comments (1)
That 60-point rule is the part I would steal. Cutting unclear numbers from 24 of 850 down to 2 is a clean way to show the placer actually works.