Source identity
| Field | Recorded value |
|---|---|
| Source type | GitHub source |
| Original record | Janady13/feedthejoe / src/core/field/contour.js |
| Date | Not specified in source |
| Repository | Janady13/feedthejoe |
| Revision | 0e608a2b515a959bf35d2783428766624400ca3c |
| Branch | main |
| Path or archive member | src/core/field/contour.js |
| Original SHA-256 | 835584cba6eda572302187dbfdd6dbbdb2d6672dd6c27f941583f4014e7ab978 |
| Git blob SHA | c8751501a8b74d801cf4bab8164fb7d26a0b2034 |
| Reading-copy SHA-256 | 835584cba6eda572302187dbfdd6dbbdb2d6672dd6c27f941583f4014e7ab978 |
Recovered source transcript
Download complete source text ↓164 lines · 5.9 KB
/**
* Contour extraction by marching squares.
*
* Given a scalar field and a threshold, walk every cell of the grid and emit
* the line segments where the surface crosses that level. Chain those segments
* into continuous polylines so the result can be drawn as strokes rather than
* as a scatter of disconnected ticks — the chaining is what makes the output a
* DRAWING instead of a dashed approximation of one.
*
* Pure. This is the piece that converts a measurement into a line.
*/
/** Linear crossing position between two corner values. */
function lerp(threshold, a, b) {
const d = b - a;
// A flat edge has no defined crossing; put it at the midpoint rather than
// dividing by zero and emitting a coordinate of Infinity.
return Math.abs(d) < 1e-12 ? 0.5 : (threshold - a) / d;
}
/**
* Extract contour segments at one level.
*
* @param {{data: Float32Array, width: number, height: number}} field
* @param {number} threshold
* @returns {number[][]} Segments as [x1, y1, x2, y2] in grid coordinates.
*/
export function marchingSquares(field, threshold) {
const { data, width, height } = field;
const segments = [];
const at = (x, y) => data[y * width + x];
for (let y = 0; y < height - 1; y += 1) {
for (let x = 0; x < width - 1; x += 1) {
const tl = at(x, y);
const tr = at(x + 1, y);
const br = at(x + 1, y + 1);
const bl = at(x, y + 1);
let idx = 0;
if (tl > threshold) idx |= 8;
if (tr > threshold) idx |= 4;
if (br > threshold) idx |= 2;
if (bl > threshold) idx |= 1;
if (idx === 0 || idx === 15) continue;
// Crossing points on each edge, in grid coordinates.
const top = [x + lerp(threshold, tl, tr), y];
const right = [x + 1, y + lerp(threshold, tr, br)];
const bottom = [x + lerp(threshold, bl, br), y + 1];
const left = [x, y + lerp(threshold, tl, bl)];
const push = (a, b) => segments.push([a[0], a[1], b[0], b[1]]);
switch (idx) {
case 1: case 14: push(left, bottom); break;
case 2: case 13: push(bottom, right); break;
case 3: case 12: push(left, right); break;
case 4: case 11: push(top, right); break;
case 6: case 9: push(top, bottom); break;
case 7: case 8: push(left, top); break;
// Saddles. Both diagonal corners are on the same side of the threshold,
// so the cell can be resolved two ways. Disambiguate with the average of
// the four corners — the standard fix. Choosing arbitrarily produces
// contours that cross themselves, which looks like a rendering bug.
case 5: {
const centre = (tl + tr + br + bl) / 4;
if (centre > threshold) { push(left, top); push(bottom, right); }
else { push(left, bottom); push(top, right); }
break;
}
case 10: {
const centre = (tl + tr + br + bl) / 4;
if (centre > threshold) { push(top, right); push(left, bottom); }
else { push(top, left); push(right, bottom); }
break;
}
default: break;
}
}
}
return segments;
}
/**
* Chain segments into continuous polylines.
*
* Marching squares emits segments in scan order, not in path order. Drawing
* them as-is gives a field of unconnected ticks. Joining endpoints turns them
* into the long, continuous lines that read as a contour drawn by hand.
*
* @param {number[][]} segments
* @param {number} [tol] How close two endpoints must be to count as the same.
* @returns {number[][][]} Polylines as arrays of [x, y].
*/
export function chain(segments, tol = 1e-6) {
// Spatial hash on quantised endpoints: O(n) rather than O(n^2) pairwise.
const key = (x, y) => `${Math.round(x / tol)},${Math.round(y / tol)}`;
const ends = new Map();
segments.forEach((s, i) => {
for (const k of [key(s[0], s[1]), key(s[2], s[3])]) {
if (!ends.has(k)) ends.set(k, []);
ends.get(k).push(i);
}
});
const used = new Uint8Array(segments.length);
const paths = [];
for (let i = 0; i < segments.length; i += 1) {
if (used[i]) continue;
used[i] = 1;
const s = segments[i];
const path = [[s[0], s[1]], [s[2], s[3]]];
// Extend from both ends until nothing connects.
for (const forward of [true, false]) {
for (;;) {
const tip = forward ? path[path.length - 1] : path[0];
const candidates = ends.get(key(tip[0], tip[1])) ?? [];
const next = candidates.find((j) => !used[j]);
if (next === undefined) break;
used[next] = 1;
const t = segments[next];
const head = Math.abs(t[0] - tip[0]) < tol && Math.abs(t[1] - tip[1]) < tol;
const point = head ? [t[2], t[3]] : [t[0], t[1]];
if (forward) path.push(point); else path.unshift(point);
}
}
// Two-segment stubs are marching-squares noise at the field's edge, not
// structure. Dropping them keeps the drawing clean.
if (path.length > 2) paths.push(path);
}
return paths;
}
/**
* Extract a full set of nested contours.
*
* @param {{data: Float32Array, width: number, height: number, min: number, max: number}} field
* @param {number} levels How many contour lines.
* @param {number} [floor] Fraction of the range to start at; below this the
* terrain is flat and the contours are just noise.
* @returns {Array<{level: number, t: number, paths: number[][][]}>}
*/
export function contours(field, levels, floor = 0.06) {
const out = [];
const range = field.max - field.min;
for (let i = 0; i < levels; i += 1) {
// Distribute levels with a slight bias toward the low end, where the
// interesting silhouette of the landmass lives; evenly spaced levels put
// most of the lines inside the peaks where they read as clutter.
const t = floor + (1 - floor) * ((i + 1) / (levels + 1)) ** 1.35;
const level = field.min + range * t;
const paths = chain(marchingSquares(field, level));
if (paths.length) out.push({ level, t, paths });
}
return out;
}