Checks contour lines, gives them elevations, and builds a ground surface from them, filling in the flat triangles that contours leave on ridges, valleys and hilltops.
How the precision is kept
Contour vertices keep their 64-bit coordinates and become breaklines of the surface. Two optional steps set the accuracy of the result: line simplification to a tolerance the person chooses, and estimated points added inside flat triangles. The checks use fixed absolute tolerances.
Calculations under this policy
8 calculations in 1 source file. 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.
The one elevation a line carries: its own z, or the z all its vertices share.
Vertices count as one level when each is within 1e-9 of the first (absolute). The first vertex's z is returned unchanged; a shared level of exactly 0 is treated as no elevation.
ground-surface.js
lines 38 to 45
CivilCraft 0.8.1
export function levelOf(line) {
if (finite(line?.z)) return line.z;
const pts = line?.pts || [];
if (!pts.length || !pts.every((p) => finite(p.z))) return null;
const z = pts[0].z;
if (!pts.every((p) => Math.abs(p.z - z) < 1e-9)) return null;
return z === 0 ? null : z;
}
Elevations by picking lines in order
64-bit
Gives the k-th picked line the elevation start + k × interval.
z_k = start + k × interval
Each level is one multiplication and one addition from the whole-number count, not a running sum, so the error does not grow with the number of picks.
ground-surface.js
lines 47 to 51
CivilCraft 0.8.1
export function assignPick(lines, picks, start, interval) {
const lv = new Map();
for (const i of picks) if (!lv.has(i) && i >= 0 && i < lines.length) lv.set(i, start + lv.size * interval);
return lines.map((l, i) => (lv.has(i) ? { ...l, z: lv.get(i) } : l));
}
Where two contour segments cross
64-bit
The crossing point of two segments, or none when they are parallel or only meet at an end.
d = (q − p) × (s − r); t = (r − p) × (s − r) ÷ d; point = p + t·(q − p)
Segments are treated as parallel when |d| < 1e-14, an absolute threshold on a value with units of length squared, so two very short segments can be skipped as parallel. Crossings within 1e-9 of either end (in the segment parameter) are not reported.
ground-surface.js
lines 60 to 67
CivilCraft 0.8.1
function segCross(p, q, r, s) {
const d = (q.x - p.x) * (s.y - r.y) - (q.y - p.y) * (s.x - r.x);
if (Math.abs(d) < 1e-14) return null;
const t = ((r.x - p.x) * (s.y - r.y) - (r.y - p.y) * (s.x - r.x)) / d;
const u = ((r.x - p.x) * (q.y - p.y) - (r.y - p.y) * (q.x - p.x)) / d;
if (t <= 1e-9 || t >= 1 - 1e-9 || u <= 1e-9 || u >= 1 - 1e-9) return null; // meeting at an end is not a crossing
return { x: p.x + t * (q.x - p.x), y: p.y + t * (q.y - p.y) };
}
Contour checks
64-bit
Lists lines with no elevation, elevations off the interval, duplicate lines and lines that cross.
k = (z − base) ÷ interval; off the interval when |k − round(k)| > 1e-6
The off-interval test allows 1e-6 of an interval. Duplicates are found by rounding x and y to the tolerance (1e-6 by default) and comparing the rounded lists; the rounding is used only for the comparison. Two lines count as the same level only when their levels are exactly equal.
ground-surface.js
lines 71 to 126
CivilCraft 0.8.1
export function checkContours(lines, { interval = 0, base = 0, tol = 1e-6, maxIssues = 500 } = {}) {
const issues = [], push = (i) => { if (issues.length < maxIssues) issues.push(i); };
const levels = lines.map(levelOf);
lines.forEach((l, i) => {
if ((l.pts || []).length < 2) push({ code: 'short', a: i });
else if (levels[i] === null) push({ code: 'noz', a: i });
else if (interval > 0) {
const k = (levels[i] - base) / interval;
if (Math.abs(k - Math.round(k)) > 1e-6) push({ code: 'offgrid', a: i, z: levels[i] });
}
});
// duplicates: same vertex set (either direction)
const sig = new Map();
lines.forEach((l, i) => {
if ((l.pts || []).length < 2) return;
const r = (v) => Math.round(v / Math.max(tol, 1e-9));
const f = l.pts.map((p) => r(p.x) + ',' + r(p.y)), b = f.slice().reverse();
const key = (f.join(';') < b.join(';') ? f : b).join(';');
if (sig.has(key)) push({ code: 'duplicate', a: i, b: sig.get(key) }); else sig.set(key, i);
});
// crossings: segments hashed on a grid
const segs = [];
lines.forEach((l, i) => {
const pts = closedPts(l);
for (let k = 0; k + 1 < (pts?.length || 0); k++) segs.push({ i, k, p: pts[k], q: pts[k + 1] });
});
if (segs.length) {
let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity, len = 0;
for (const s of segs) { minX = Math.min(minX, s.p.x, s.q.x); minY = Math.min(minY, s.p.y, s.q.y); maxX = Math.max(maxX, s.p.x, s.q.x); maxY = Math.max(maxY, s.p.y, s.q.y); len += Math.hypot(s.q.x - s.p.x, s.q.y - s.p.y); }
const cell = Math.max(len / segs.length * 2, (Math.max(maxX - minX, maxY - minY) || 1) / 2000, 1e-9);
const grid = new Map();
const cells = (s, f) => {
const x0 = Math.floor((Math.min(s.p.x, s.q.x) - minX) / cell), x1 = Math.floor((Math.max(s.p.x, s.q.x) - minX) / cell);
const y0 = Math.floor((Math.min(s.p.y, s.q.y) - minY) / cell), y1 = Math.floor((Math.max(s.p.y, s.q.y) - minY) / cell);
if ((x1 - x0 + 1) * (y1 - y0 + 1) > 4096) { f('big'); return; }
for (let x = x0; x <= x1; x++) for (let y = y0; y <= y1; y++) f(x + ',' + y);
};
segs.forEach((s, n) => cells(s, (c) => { let a = grid.get(c); if (!a) grid.set(c, a = []); a.push(n); }));
const seen = new Set(), pairSeen = new Set();
for (const list of grid.values()) {
for (let a = 0; a < list.length; a++) for (let b = a + 1; b < list.length; b++) {
const A = segs[list[a]], B = segs[list[b]];
if (A.i === B.i && Math.abs(A.k - B.k) < 2) continue; // neighbours on one line
const pk = list[a] + '_' + list[b];
if (seen.has(pk)) continue; seen.add(pk);
const x = segCross(A.p, A.q, B.p, B.q);
if (!x) continue;
const lo = Math.min(A.i, B.i), hi = Math.max(A.i, B.i), key = lo + '_' + hi;
if (pairSeen.has(key)) continue; pairSeen.add(key);
const same = levels[A.i] !== null && levels[A.i] === levels[B.i];
push({ code: same && A.i !== B.i ? 'samelevel' : 'crossing', a: lo, b: hi, x: x.x, y: x.y, z: levels[lo], zb: levels[hi] });
}
}
}
return issues;
}
Line simplification
64-bit
Removes contour vertices that lie within a tolerance of the line through their neighbors.
distance = |(p − a) × (b − a)| ÷ |b − a|
Douglas–Peucker on x and y only. Kept vertices are the original objects, so their coordinates are not changed; dropped vertices move the line by up to the tolerance. When the two end points coincide the distance to that point is used instead of dividing by zero.
ground-surface.js
lines 131 to 146
CivilCraft 0.8.1
export function simplifyLine(pts, tol) {
if (!(tol > 0) || pts.length < 3) return pts.slice();
const keep = new Uint8Array(pts.length); keep[0] = keep[pts.length - 1] = 1;
const stack = [[0, pts.length - 1]];
while (stack.length) {
const [i, j] = stack.pop();
let best = -1, bd = tol;
const a = pts[i], b = pts[j], dx = b.x - a.x, dy = b.y - a.y, L = Math.hypot(dx, dy);
for (let k = i + 1; k < j; k++) {
const d = L > 0 ? Math.abs((pts[k].x - a.x) * dy - (pts[k].y - a.y) * dx) / L : Math.hypot(pts[k].x - a.x, pts[k].y - a.y);
if (d > bd) { bd = d; best = k; }
}
if (best > 0) { keep[best] = 1; stack.push([i, best], [best, j]); }
}
return pts.filter((_, k) => keep[k]);
}
Placing by two known points
64-bit
The scale, rotation and shift that take two picked points to their real positions.
k = |b₂ − a₂| ÷ |b − a|; rot = atan2(d₂) − atan2(d₁); x′ = k·(x cos rot − y sin rot) + t_x
The rotation is formed as a difference of two atan2 angles and then turned back into cos and sin, rather than taken from the dot and cross products of the two vectors, which adds a few rounding steps. The shift is solved so that the first picked point lands on its target. Returns nothing when either pair of points coincides.
ground-surface.js
lines 148 to 155
CivilCraft 0.8.1
export function placeByTwoPoints(a, b, a2, b2) {
const d1x = b.x - a.x, d1y = b.y - a.y, d2x = b2.x - a2.x, d2y = b2.y - a2.y;
const l1 = Math.hypot(d1x, d1y), l2 = Math.hypot(d2x, d2y);
if (!(l1 > 0) || !(l2 > 0)) return null;
const k = l2 / l1, rot = Math.atan2(d2y, d2x) - Math.atan2(d1y, d1x), c = Math.cos(rot) * k, s = Math.sin(rot) * k;
const tx = a2.x - (c * a.x - s * a.y), ty = a2.y - (s * a.x + c * a.y);
return { k, rot, tx, ty, apply: (p) => ({ ...p, x: c * p.x - s * p.y + tx, y: s * p.x + c * p.y + ty }) };
}
Points inside flat triangles
64-bit
An estimated elevation at the centroid of each triangle whose three corners are on one contour.
z = z₀ − (z_apex − z₀) ÷ h_n × (h ÷ 3), averaged over contour edges; limited to z₀ ± interval ÷ 2
The slope of the neighbor across a contour edge is carried on to the centroid, which is a third of the triangle's height from that edge. A triangle is flat when its corner elevations agree within 1e-9. The result is an estimate by construction, and is clamped to half an interval from the contour when an interval is given.
ground-surface.js
lines 164 to 199
CivilCraft 0.8.1
export function fixFlatTriangles(surface, { interval = 0, constrained = null } = {}) {
const { X, Y, Z, tris, ox, oy } = surface;
const nT = tris.length / 3, eps = 1e-9;
const key = (a, b) => (a < b ? a + '_' + b : b + '_' + a);
const edgeTris = new Map();
for (let t = 0; t < nT; t++) for (let e = 0; e < 3; e++) {
const k = key(tris[3 * t + e], tris[3 * t + (e + 1) % 3]);
const l = edgeTris.get(k); if (l) l.push(t); else edgeTris.set(k, [t]);
}
const con = new Set((constrained || surface.constrainedEdges || []).map(([a, b]) => key(a, b)));
const flat = (t) => Math.abs(Z[tris[3 * t]] - Z[tris[3 * t + 1]]) < eps && Math.abs(Z[tris[3 * t + 1]] - Z[tris[3 * t + 2]]) < eps;
const dist = (p, a, b) => { const dx = X[b] - X[a], dy = Y[b] - Y[a]; return Math.abs((X[p] - X[a]) * dy - (Y[p] - Y[a]) * dx) / (Math.hypot(dx, dy) || 1); };
const out = [];
for (let t = 0; t < nT; t++) {
if (!flat(t)) continue;
const v = [tris[3 * t], tris[3 * t + 1], tris[3 * t + 2]], z0 = Z[v[0]];
const area2 = Math.abs((X[v[1]] - X[v[0]]) * (Y[v[2]] - Y[v[0]]) - (X[v[2]] - X[v[0]]) * (Y[v[1]] - Y[v[0]]));
if (area2 < 1e-12) continue;
const ests = [];
for (let e = 0; e < 3; e++) {
const a = v[e], b = v[(e + 1) % 3], c = v[(e + 2) % 3], k = key(a, b);
if (!con.has(k)) continue;
const other = (edgeTris.get(k) || []).find((u) => u !== t);
if (other === undefined || flat(other)) continue;
const apex = [tris[3 * other], tris[3 * other + 1], tris[3 * other + 2]].find((q) => q !== a && q !== b);
const hn = dist(apex, a, b);
if (!(hn > 0)) continue;
ests.push(z0 - ((Z[apex] - z0) / hn) * (dist(c, a, b) / 3));
}
if (!ests.length) continue;
let z = ests.reduce((s, q) => s + q, 0) / ests.length;
if (interval > 0) z = Math.max(z0 - interval / 2, Math.min(z0 + interval / 2, z));
out.push({ x: (X[v[0]] + X[v[1]] + X[v[2]]) / 3 + ox, y: (Y[v[0]] + Y[v[1]] + Y[v[2]]) / 3 + oy, z });
}
return out;
}
Building the ground surface
64-bit
Thins the points when a spacing is given, triangulates with the breaklines, and repeats the flat-triangle fill-in up to three times.
Thinning is done by Thinner (thin.js) and triangulation by buildSurface (tin.js); this function passes points through unchanged. Each fill-in pass rebuilds the whole surface from the original points plus the added ones.
Douglas–Peucker simplification in plan; segment crossing by parametric solve on a hashed grid; flat-triangle points at the centroid with an elevation extrapolated from the neighboring triangle's slope, limited to half a contour interval.
Number types
64-bit numbers; the surface arrays X, Y, Z come from tin.js.
Tolerances
Same level: 1e-9. Off-interval test: 1e-6 of an interval. Duplicate lines: vertices rounded to 1e-6. Parallel segments: |denominator| < 1e-14. Crossing ends excluded within 1e-9 of the segment parameter. Flat triangle: vertex elevations within 1e-9; triangles with twice-area under 1e-12 skipped. All absolute.
Limits
Elevations added inside flat triangles are estimates, not survey data. Simplification moves the surface by up to the chosen tolerance in plan. Up to 3 fill-in passes.
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.