Group OCR word boxes into text lines by vertical overlap
An expense app scans paper receipts. Its text recognizer returns one box per word, in no particular order, and the boxes on one printed line are never perfectly aligned: a crumpled receipt makes words drift up and down. Implement readReceiptLines(boxes), which rebuilds the printed lines of text from the boxes.
readReceiptLines(boxes) // => string[]
// boxes: Array<{ text: string, x: number, y: number, width: number, height: number }>
x and y are the box’s top-left corner and y grows downward. height is positive. width is not needed.
y, then by x, then by their position in the input.top to bottom, which starts as the first box’s own extent: top = y, bottom = y + height.overlap = min(bottom, box.y + box.height) - max(top, box.y).overlap >= box.height / 2 (at least half of the box’s own height), the box joins the line and the band grows to cover it: bottom = max(bottom, box.y + box.height).Because the band grows, a line can drift downward word by word, which is exactly what a tilted receipt does.
x (smallest first), ties by position in the input, and joined with a single space.[] for no boxes. Do not mutate boxes or the box objects.readReceiptLines([
{ text: 'TOTAL', x: 10, y: 200, width: 60, height: 20 },
{ text: '$12.40', x: 150, y: 204, width: 50, height: 20 },
{ text: 'Coffee', x: 10, y: 100, width: 60, height: 18 },
{ text: '$4.20', x: 150, y: 96, width: 45, height: 18 },
{ text: 'Bagel', x: 10, y: 130, width: 50, height: 18 },
{ text: '$8.20', x: 150, y: 133, width: 45, height: 18 },
]);
// => ['Coffee $4.20', 'Bagel $8.20', 'TOTAL $12.40']
Sorted by y: $4.20 (96), Coffee (100), Bagel (130), $8.20 (133), TOTAL (200), $12.40 (204). “$4.20” opens a line with band 96–114. Coffee spans 100–118 and overlaps by 14, at least half of 18, so it joins and the band becomes 96–118. Bagel (130–148) does not overlap, so it opens line 2, and so on.
// A drifting line: each word overlaps the grown band by at least half its height.
readReceiptLines([
{ text: 'due', x: 60, y: 0, width: 30, height: 10 },
{ text: 'Amount', x: 0, y: 4, width: 50, height: 10 },
{ text: 'now', x: 110, y: 9, width: 30, height: 10 },
]);
// => ['Amount due now']
// band 0–10, Amount overlaps 6 (joins, band 0–14), now overlaps 5 (joins)