Compares two revisions of a sheet by their drawn lines: which lines were taken out or put in, how much, where, and whether the drawing inside a task's region changed.
How the precision is kept
The comparison is a sampled, tolerance-based test, not an exact one. Each sheet's paths are cut into straight segments, each segment is sampled every 2 points, and a sample counts as unchanged when a segment of the other sheet lies within 1.5 points. The arithmetic is 64-bit, but the path coordinates come from pdf.js 6.3.289 as a Float32Array, so they are 32-bit values before the page transform is applied. Reported amounts are rounded to whole points of line.
Open item. Use one test for a very long segment in both index() and unmatched(), so a long sloped line near the 4000-cell limit cannot be left out of both the grid and the one-by-one list.
Calculations under this policy
16 calculations in 4 source files. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
Every drawn path of a page as straight segments in page coordinates.
curve point = Bézier at t = j ÷ 8, j = 1…8; p′ = CTM × p
The path numbers are read from the array pdf.js supplies with each constructPath operator, which pdf.js 6.3.289 creates as a Float32Array, so each coordinate has 32-bit precision before the 64-bit transform. Cubic and quadratic curves become 8 chords each. Segments whose two transformed ends are exactly equal are dropped, and reading stops at 400,000 segments.
vecdiff.js
lines 21 to 60
MarkupCraft 0.8.1
export function pageSegments(opList, OPS, { max = 400000 } = {}) {
const out = [];
let ctm = [1, 0, 0, 1, 0, 0];
const stack = [];
const fn = opList.fnArray, args = opList.argsArray;
for (let i = 0; i < fn.length && out.length < max; i++) {
const op = fn[i], a = args[i];
if (op === OPS.save) stack.push(ctm);
else if (op === OPS.restore) ctm = stack.pop() || ctm;
else if (op === OPS.transform) ctm = mul(ctm, a);
else if (op === OPS.paintFormXObjectBegin) { stack.push(ctm); if (Array.isArray(a?.[0]) || a?.[0]?.length === 6) ctm = mul(ctm, Array.from(a[0])); }
else if (op === OPS.paintFormXObjectEnd) ctm = stack.pop() || ctm;
else if (op === OPS.constructPath) {
const data = a?.[1]?.[0];
if (!data) continue;
let x = 0, y = 0, sx = 0, sy = 0;
const seg = (x1, y1, x2, y2) => { const p = ap(ctm, x1, y1), q = ap(ctm, x2, y2); if (p[0] !== q[0] || p[1] !== q[1]) out.push([p[0], p[1], q[0], q[1]]); };
for (let k = 0; k < data.length;) {
const c = data[k];
if (c === DRAW.moveTo) { x = sx = data[k + 1]; y = sy = data[k + 2]; k += 3; }
else if (c === DRAW.lineTo) { seg(x, y, data[k + 1], data[k + 2]); x = data[k + 1]; y = data[k + 2]; k += 3; }
else if (c === DRAW.curveTo || c === DRAW.quadTo) {
const cubic = c === DRAW.curveTo;
const pts = cubic ? [data[k + 1], data[k + 2], data[k + 3], data[k + 4], data[k + 5], data[k + 6]] : [data[k + 1], data[k + 2], data[k + 3], data[k + 4]];
const ex = pts[pts.length - 2], ey = pts[pts.length - 1];
let px = x, py = y;
for (let j = 1; j <= 8; j++) {
const t = j / 8, u = 1 - t;
const nx = cubic ? u * u * u * x + 3 * u * u * t * pts[0] + 3 * u * t * t * pts[2] + t * t * t * ex : u * u * x + 2 * u * t * pts[0] + t * t * ex;
const ny = cubic ? u * u * u * y + 3 * u * u * t * pts[1] + 3 * u * t * t * pts[3] + t * t * t * ey : u * u * y + 2 * u * t * pts[1] + t * t * ey;
seg(px, py, nx, ny); px = nx; py = ny;
}
x = ex; y = ey; k += cubic ? 7 : 5;
} else if (c === DRAW.close) { seg(x, y, sx, sy); x = sx; y = sy; k += 1; }
else break; // an unknown code: stop reading this path rather than misread it
}
}
}
return out;
}
Distance from a point to a segment
64-bit
How far a sample point is from one segment of the other sheet.
t = clamp((p − a)·d ÷ |d|², 0, 1); distance = hypot(p − (a + t·d))
One division, guarded for a zero-length segment, and one Math.hypot. The parameter is clamped to the segment's ends.
vecdiff.js
lines 73 to 79
MarkupCraft 0.8.1
function distSeg(px, py, s) {
const dx = s[2] - s[0], dy = s[3] - s[1];
const L = dx * dx + dy * dy;
let t = L ? ((px - s[0]) * dx + (py - s[1]) * dy) / L : 0;
t = Math.max(0, Math.min(1, t));
return Math.hypot(px - (s[0] + t * dx), py - (s[1] + t * dy));
}
Grid of segments
64-bit
Files each segment under the grid cells its bounding box covers, to find nearby segments quickly.
cells = (⌊x_max ÷ cell⌋ − ⌊x_min ÷ cell⌋ + 1) × (same in y); more than 4000 → not in the grid
A segment whose box covers more than 4000 cells is left out here, to be checked one by one in unmatched(). That function selects such segments with a different expression, (|Δx| ÷ cell + 1) × (|Δy| ÷ cell + 1) > 4000, without the floor. The two counts can fall on opposite sides of 4000 for the same segment, and a segment left out of both is never matched.
vecdiff.js
lines 62 to 72
MarkupCraft 0.8.1
/** A grid of segments for "is there a segment within tol of this point?" */
function index(segs, cell) {
const g = new Map();
segs.forEach((s, i) => {
const x0 = Math.floor(Math.min(s[0], s[2]) / cell), x1 = Math.floor(Math.max(s[0], s[2]) / cell);
const y0 = Math.floor(Math.min(s[1], s[3]) / cell), y1 = Math.floor(Math.max(s[1], s[3]) / cell);
if ((x1 - x0 + 1) * (y1 - y0 + 1) > 4000) return; // a huge segment (a sheet border): checked by brute force below
for (let gx = x0; gx <= x1; gx++) for (let gy = y0; gy <= y1; gy++) { const k = gx + ',' + gy; (g.get(k) || g.set(k, []).get(k)).push(i); }
});
return g;
}
Parts of a sheet with no match
64-bit
The pieces of one sheet's segments that have no segment of the other sheet within the tolerance.
n = max(1, ⌈length ÷ step⌉) samples; miss when no segment within tol
Each segment is tested at n + 1 evenly spaced points. A run of missed samples becomes one output piece from its first to its last sample, so piece ends are quantized to the sampling step; a single missed sample between two matches is dropped unless the segment has only one interval. The cell size is max(4 × tol, 8) and the search covers the 3 × 3 cells round the sample.
vecdiff.js
lines 88 to 115
MarkupCraft 0.8.1
/** The pieces of `segs` (sampled every `step`) with no segment of `other` within tol. */
function unmatched(segs, other, tol, step) {
const cell = Math.max(tol * 4, 8);
const grid = index(other, cell);
const big = other.map((s, i) => [s, i]).filter(([s]) => (Math.abs(s[2] - s[0]) / cell + 1) * (Math.abs(s[3] - s[1]) / cell + 1) > 4000).map(([, i]) => i);
const out = [];
let kept = 0;
for (const s of segs) {
const len = Math.hypot(s[2] - s[0], s[3] - s[1]);
const n = Math.max(1, Math.ceil(len / step));
let runFrom = -1;
for (let j = 0; j <= n; j++) {
const t = j / n, x = s[0] + (s[2] - s[0]) * t, y = s[1] + (s[3] - s[1]) * t;
const miss = !near(x, y, other, grid, cell, tol, big);
if (miss && runFrom < 0) runFrom = j;
if ((!miss || j === n) && runFrom >= 0) {
const end = miss ? j : j - 1;
if (end > runFrom || n === 1) {
const t0 = runFrom / n, t1 = Math.max(end, runFrom) / n;
out.push([s[0] + (s[2] - s[0]) * t0, s[1] + (s[3] - s[1]) * t0, s[0] + (s[2] - s[0]) * (t1 === t0 ? Math.min(1, t0 + 1 / n) : t1), s[1] + (s[3] - s[1]) * (t1 === t0 ? Math.min(1, t0 + 1 / n) : t1)]);
}
runFrom = -1;
}
if (!miss) kept++;
}
}
return { out, kept };
}
Removed and added lines
64-bit
The lines of the old sheet that are not on the new one, and the other way round.
The old segments are first carried through the compare alignment T in 64-bit, then unmatched() runs in both directions with the same tolerance (1.5 points by default) and step (2 points).
vecdiff.js
lines 117 to 122
MarkupCraft 0.8.1
export function diffSegments(oldSegs, newSegs, { tol = 1.5, T = null, step = 2 } = {}) {
const olds = T ? oldSegs.map((s) => [...ap(T, s[0], s[1]), ...ap(T, s[2], s[3])]) : oldSegs;
const r = unmatched(olds, newSegs, tol, step);
const a = unmatched(newSegs, olds, tol, step);
return { removed: r.out, added: a.out, kept: r.kept + a.kept };
}
Boxes round groups of changes
64-bit
Groups changed segments that are close together into boxes, for clouding and for the list of changes.
merge boxes closer than gap; keep groups with Σ length ≥ minLen
Bounding boxes are merged with min and max only, so a box's numbers are segment coordinates, unchanged. Merging repeats until a pass makes no merge. The gap (18 points by default) and the minimum length (6 points) are absolute.
vecdiff.js
lines 124 to 155
MarkupCraft 0.8.1
export function clusters(segs, { gap = 18, minLen = 6 } = {}) {
const boxes = segs.map((s) => ({ b: [Math.min(s[0], s[2]), Math.min(s[1], s[3]), Math.max(s[0], s[2]), Math.max(s[1], s[3])], n: Math.hypot(s[2] - s[0], s[3] - s[1]) }));
// merge boxes closer than `gap` until nothing changes (grid-accelerated)
let changed = true;
let list = boxes;
while (changed) {
changed = false;
const cell = gap * 4;
const grid = new Map();
const out = [];
for (const bx of list) {
let host = null;
const cx0 = Math.floor((bx.b[0] - gap) / cell), cx1 = Math.floor((bx.b[2] + gap) / cell), cy0 = Math.floor((bx.b[1] - gap) / cell), cy1 = Math.floor((bx.b[3] + gap) / cell);
search: for (let gx = cx0; gx <= cx1; gx++) for (let gy = cy0; gy <= cy1; gy++) {
for (const o of grid.get(gx + ',' + gy) || []) {
if (o.dead) continue;
if (bx.b[0] - gap <= o.b[2] && o.b[0] - gap <= bx.b[2] && bx.b[1] - gap <= o.b[3] && o.b[1] - gap <= bx.b[3]) { host = o; break search; }
}
}
if (host) {
host.b = [Math.min(host.b[0], bx.b[0]), Math.min(host.b[1], bx.b[1]), Math.max(host.b[2], bx.b[2]), Math.max(host.b[3], bx.b[3])];
host.n += bx.n;
changed = true;
} else {
out.push(bx);
for (let gx = Math.floor(bx.b[0] / cell); gx <= Math.floor(bx.b[2] / cell); gx++) for (let gy = Math.floor(bx.b[1] / cell); gy <= Math.floor(bx.b[3] / cell); gy++) { const k = gx + ',' + gy; (grid.get(k) || grid.set(k, []).get(k)).push(bx); }
}
}
list = out;
}
return list.filter((x) => x.n >= minLen).map((x) => x.b);
}
The size of a changed area as text: inches on the sheet and, on a calibrated sheet, the real size.
in = round(pt ÷ 72, 1 decimal); real = pt × mmPerPt, in m to 1 decimal from 1000 mm, else whole mm
64-bit arithmetic, then rounded for the text; the real size is worded as "about". The box it describes is a cluster box of sampled changes, so the size is an estimate by construction.
changes.js
lines 34 to 40
MarkupCraft 0.8.1
/** A size in the sheet's own units: inches on paper, and the real length when the sheet is calibrated (mm per point). */
export function sizeWords(wPt, hPt, mmPerPt = 0) {
const paper = r1(wPt / 72) + ' × ' + r1(hPt / 72) + ' in on the sheet';
if (!(mmPerPt > 0)) return paper;
const m = (v) => (v * mmPerPt >= 1000 ? r1(v * mmPerPt / 1000) + ' m' : Math.round(v * mmPerPt) + ' mm');
return 'about ' + m(wPt) + ' × ' + m(hPt) + ' (' + paper + ')';
}
Where on the sheet
64-bit
Names the part of the sheet a point is in, on a 3 × 3 grid (upper left, center, lower right and so on).
column = ⌊(x − x₀) ÷ w × 3⌋; row = ⌊(y₁ − y) ÷ h × 3⌋, each clamped to 0…2
Two 64-bit quotients, floored and clamped to 0…2. A sheet with no width or height gives the center.
changes.js
lines 25 to 32
MarkupCraft 0.8.1
/** Where a point is on a sheet, in words (a 3 × 3 grid; y is up in PDF space). */
export function whereOn(view, x, y) {
const w = view[2] - view[0], h = view[3] - view[1];
if (!(w > 0 && h > 0)) return 'centre';
const col = Math.min(2, Math.max(0, Math.floor(((x - view[0]) / w) * 3)));
const row = Math.min(2, Math.max(0, Math.floor(((view[3] - y) / h) * 3))); // 0 = top
return SIZE_WORDS[row * 3 + col];
}
Amount of change in an area
64-bit
How many points of line were removed and added inside one changed area, and whether it counts as added, removed or modified.
removed = Σ hypot over removed pieces in the box; modified when both ≥ 6 pt
A piece belongs to a box when its midpoint is inside the box grown by 1 point. The sums are 64-bit and are rounded to whole points in the result; the box is rounded to 0.1 point.
The parts of a sheet's segments that lie inside a task's region.
Liang–Barsky: r = q ÷ p per box side; keep when t₁ − t₀ > 1e-9
The division is skipped when p is exactly 0 (a segment parallel to that side). The 1e-9 is in the segment's own parameter, so it is relative to the segment's length. Clipped ends are computed as a + d × t.
tasks.js
lines 100 to 116
MarkupCraft 0.8.1
/** The parts of the segments inside the box (Liang–Barsky clip), so a line crossing the region counts for its part inside it. */
export function clipSegments(segs, box, margin = 0) {
const [x0, y0, x1, y1] = [box[0] - margin, box[1] - margin, box[2] + margin, box[3] + margin];
const out = [];
for (const [ax, ay, bx, by] of segs) {
const dx = bx - ax, dy = by - ay;
let t0 = 0, t1 = 1, ok = true;
for (const [p, q] of [[-dx, ax - x0], [dx, x1 - ax], [-dy, ay - y0], [dy, y1 - ay]]) {
if (p === 0) { if (q < 0) { ok = false; break; } continue; }
const r = q / p;
if (p < 0) { if (r > t1) { ok = false; break; } if (r > t0) t0 = r; }
else { if (r < t0) { ok = false; break; } if (r < t1) t1 = r; }
}
if (ok && t1 - t0 > 1e-9) out.push([ax + dx * t0, ay + dy * t0, ax + dx * t1, ay + dy * t1]);
}
return out;
}
Region snapshot
64-bit
What a task's region link stores when it is made: the sheet's lines inside the region.
keep the 300 longest clipped segments; each coordinate rounded to 0.1 pt
The stored coordinates are rounded with Math.round(v × 10) ÷ 10 (cleanSegs), and segments beyond the 300 longest are not kept. The later comparison takes a new snapshot with the same clip, cap and rounding; its default tolerance of 1.5 points is fifteen times the rounding step.
tasks.js
lines 119 to 128
MarkupCraft 0.8.1
/** What a region link keeps when it is made: the sheet's lines inside the markup's rectangle (grown a little), thinned to the limit. */
export function regionSnapshot(allSegs, rect, { margin = 6 } = {}) {
const box = [Math.min(rect[0], rect[2]), Math.min(rect[1], rect[3]), Math.max(rect[0], rect[2]), Math.max(rect[1], rect[3])];
let segs = clipSegments(allSegs, box, margin);
if (segs.length > LIMITS.segs) {
// keep the longest lines: they carry the shape of the drawing; short ones are hatching and text strokes
segs = segs.map((s, i) => [Math.hypot(s[2] - s[0], s[3] - s[1]), i]).sort((a, b) => b[0] - a[0] || a[1] - b[1]).slice(0, LIMITS.segs).map(([, i]) => segs[i]);
}
return { rect: box, segs: cleanSegs(segs) };
}
Has the region changed
64-bit
Decides whether the drawing inside a task's region changed between the snapshot and the new revision.
changed when removed + added ≥ 4 pt and (removed + added) ÷ stored length ≥ 0.02
Lengths are 64-bit sums of Math.hypot over the unmatched pieces. The reported amounts are rounded to whole points and the kept share to 2 decimals. The stored length is taken as at least 1 point to guard the division.
tasks.js
lines 130 to 146
MarkupCraft 0.8.1
/**
* Has the drawing inside a region link changed? `newSegs` = the new revision's lines for the whole sheet (pageSegments).
* → { changed, removed, added (points of line), keptShare, summary }. Compared with the same clip and the same cap as the
* snapshot, so an untouched sheet reads as unchanged. Under `minChange` points (and 2 % of the lines) it is not a change.
*/
export function compareRegion(link, newSegs, { tol = 1.5, minChange = 4, margin = 6 } = {}) {
if (!link || link.kind !== 'region') throw new Error('Not a region link.');
const now = regionSnapshot(newSegs, link.rect, { margin }).segs;
const before = link.segs;
const d = diffSegments(before, now, { tol, step: 2 });
const removed = length(d.removed), added = length(d.added), total = Math.max(length(before), 1);
const changed = (removed + added >= minChange) && (removed + added) / total >= 0.02;
const words = [];
if (removed >= minChange) words.push(Math.round(removed) + ' points of line taken out');
if (added >= minChange) words.push(Math.round(added) + ' points of line put in');
return { changed, removed: Math.round(removed), added: Math.round(added), keptShare: Math.round((1 - Math.min(1, (removed) / total)) * 100) / 100, summary: changed ? 'The drawing in the marked area changed: ' + words.join(', ') + '.' : 'The drawing in the marked area is the same.' };
}
Has a model element changed
64-bit
Compares the stored state of a linked model element with its state now, number by number.
same when |x − y| ≤ tol
An absolute tolerance: the one passed in, else the link's own, which cleanLink sets to 0.01 when none is given. It is applied to every numeric field alike, whatever its unit or size.
tasks.js
lines 148 to 174
MarkupCraft 0.8.1
/**
* Has the model element changed? `now` = its state now (cleanElementState shape), or null when it is gone.
* → { changed, gone, diffs: [{ key, from, to }], summary }. Numbers differ only past `tol`; volatile keys are ignored.
*/
export function compareElement(link, now, { tol } = {}) {
if (!link || link.kind !== 'element') throw new Error('Not an element link.');
if (now === null || now === undefined) return { changed: true, gone: true, diffs: [], summary: 'The element is no longer in the model.' };
const a = link.state || {}, b = cleanElementState(now);
// A link made from the page has no state yet (the person cannot read the other app): the first report is the baseline, not a change.
if (!Object.keys(a).length) return { changed: false, gone: false, baseline: true, state: b, diffs: [], summary: 'The element\'s state was recorded; the task closes when it changes.' };
const t = fin(tol) ? tol : link.tol;
const same = (x, y) => {
if (typeof x === 'number' && typeof y === 'number') return Math.abs(x - y) <= t;
if (Array.isArray(x) && Array.isArray(y)) return x.length === y.length && x.every((v, i) => Math.abs(v - y[i]) <= t);
return x === y;
};
const diffs = [];
for (const k of new Set([...Object.keys(a), ...Object.keys(b)])) {
if (VOLATILE.test(k)) continue;
if (!(k in a)) diffs.push({ key: k, from: undefined, to: b[k] });
else if (!(k in b)) diffs.push({ key: k, from: a[k], to: undefined });
else if (!same(a[k], b[k])) diffs.push({ key: k, from: a[k], to: b[k] });
}
const show = (v) => (v === undefined ? 'nothing' : Array.isArray(v) ? '[' + v.join(', ') + ']' : typeof v === 'string' ? '"' + v + '"' : String(v));
const shown = diffs.slice(0, 4).map((d) => d.key + ' ' + show(d.from) + ' → ' + show(d.to));
return { changed: diffs.length > 0, gone: false, diffs, summary: diffs.length ? 'The element changed: ' + shown.join('; ') + (diffs.length > 4 ? ' and ' + (diffs.length - 4) + ' more.' : '.') : 'The element is the same.' };
}
The amount of removed and added line shown after comparing two sheets by their lines.
amount = round(Σ hypot(Δx, Δy)) in points
Runs diffSegments with a tolerance of 1.5 points, a step of 2 points and the current alignment. The sum is 64-bit and is rounded to a whole number of points for the status line.
Adds a cloud rectangle markup round each group of changes on every changed sheet.
cloud box = cluster box grown by 8 pt on each side
The cluster boxes come from clusters() with a gap of 18 points and a minimum of 6 points of line. The 8 point margin is absolute. The stored box therefore traces the sampled change pieces, not exact geometry.
markupcraft.js
lines 4024 to 4039
MarkupCraft 0.8.1
async function cloudSet() {
const changed = setResult.filter((r) => r.len >= 6);
if (!changed.length) return;
const who = await askAuthor();
let n = 0;
store.change(t('undo.setcmp.cloud'), (tx) => { for (const r of changed) {
const sh = sheetByKey(r.newKey);
for (const b of clusters([...r.d.removed, ...r.d.added], { gap: 18, minLen: 6 })) {
tx.add(makeMarkup({ sheet: r.newKey, type: 'cloudrect', rot: sh?.page.rotate || 0, rect: [b[0] - 8, b[1] - 8, b[2] + 8, b[3] + 8], author: who, style: styleFor('cloudrect'), comment: t('compare.cloud.comment', { old: sheetByKey(r.oldKey)?.page.title || '' }) }));
n++;
}
} });
setUi.status.textContent = t('setcmp.clouded', { n, sheets: t('find.sheets', { n: changed.length }) });
status(setUi.status.textContent);
refreshAll();
}
In detail
Method
Paths from the pdf.js operator list, curves cut into 8 chords, page transforms applied. A uniform grid of cells (4 × tolerance, at least 8 points) finds nearby segments; very long segments are checked one by one. Changed pieces are grouped into boxes by merging bounding boxes closer than a gap. Region links clip segments with Liang–Barsky.
Number types
64-bit numbers for the arithmetic. Path data arrives as Float32Array from pdf.js. Region snapshots are stored rounded to 0.1 point.
Tolerances
Match distance 1.5 points; sampling step 2 points; all absolute, in PDF points. Clusters: gap 18 points, at least 6 points of changed line. A sheet counts as changed from 6 points of changed line. A region counts as changed from 4 points and 2% of its stored line length. Clip: pieces shorter than 1e-9 of the segment are dropped. Element numbers differ only beyond the link's tolerance, 0.01 by default.
Limits
A change shorter than the sampling step can be missed, and piece ends fall on sample positions. Text drawn as glyphs is not compared. At most 400,000 segments are read from a page. The grid and the one-by-one list decide what is a very long segment with two different formulas.
Approach: 64-bit, stated limit
The arithmetic is 64-bit, but the method or the data sets the accuracy: a solver tolerance, a mesh, a step size, a datum shift, a table. The limit is stated where the result is shown.