Resources Numerical accuracy Calculation policy

Wide polylines, text masks and ellipses as drawn and plotted

Builds the outlines that a polyline with width, a text background mask and an ellipse become when the drawing is put on screen or on a plotted page.

How the precision is kept

All arithmetic is 64-bit. Straight wide segments get exact offset corners at half the width on each side. Arc segments with width are followed in steps of at most 10 degrees and an ellipse is drawn through 96 points joined by straight lines, so those outlines are polygons whose accuracy is set by the step, not by the number type.

Calculations under this policy

6 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.

walk.js CadCraft 0.8.2 64-bit 6 calculations Reviewed

Tests bin/test-cadcraft.mjs

Band of a wide polyline segment

64-bit

The filled outline of one polyline segment that has a start and end width.

h(t) = (w₀ + (w₁ − w₀)·t) ÷ 2; left = p + n·h; right = p − n·h; arc: k = max(2, ⌈sweep ÷ 10°⌉) steps

On a straight segment the four corners are the end points moved by half the width along the unit normal, in one 64-bit expression each. On an arc the points are taken at k equal steps of at most 10 degrees, so the band is a polygon inside and outside the true curved band. A repeated vertex (length not above 1e-12, absolute) is skipped.

  • walk.js
  • lines 266 to 309
  • CadCraft 0.8.2
export function polyBands(e) {
  const pts = e.pts || [];
  const g = Number.isFinite(e.w) && e.w > 0 ? e.w : 0;
  if (!g && !pts.some((p) => p.sw > 0 || p.ew > 0)) return null;
  const n = pts.length, segs = e.closed ? n : n - 1;
  const loops = [], plain = [];
  const ends = [];   // per wide segment drawn: its index and both ends { x, y, tx, ty (travel direction), h (half width) }
  for (let i = 0; i < segs; i++) {
    const a = pts[i], q = pts[(i + 1) % n];
    const ws = Number.isFinite(a.sw) ? a.sw : g, we = Number.isFinite(a.ew) ? a.ew : g;
    const one = prims({ type: 'poly', closed: false, pts: [{ x: a.x, y: a.y, b: a.b || 0 }, { x: q.x, y: q.y }] }, null);
    if (!(ws > 0 || we > 0)) { plain.push(...one); continue; }
    const p = one[0];
    if (!p) continue;
    // points along the segment with their unit normals (left side)
    const along = [];
    if (p.k === 'L') {
      const L = Math.hypot(p.x2 - p.x1, p.y2 - p.y1);
      if (!(L > 1e-12)) continue;   // a repeated vertex: no band (and no corner) there
      const nx = -(p.y2 - p.y1) / L, ny = (p.x2 - p.x1) / L;
      along.push([p.x1, p.y1, nx, ny, 0], [p.x2, p.y2, nx, ny, 1]);
    } else {
      // an A primitive runs counter-clockwise from a0 to a1; the polyline may run either way
      let sweep = (p.a1 - p.a0 + TAU) % TAU || TAU;
      const ccw = (a.b || 0) > 0;
      const k = Math.max(2, Math.ceil(sweep / (Math.PI / 18)));
      for (let j = 0; j <= k; j++) {
        const t = j / k, ang = ccw ? p.a0 + sweep * t : p.a1 - sweep * t;
        const cx = Math.cos(ang), cy = Math.sin(ang);
        along.push([p.cx + p.r * cx, p.cy + p.r * cy, ccw ? -cx : cx, ccw ? -cy : cy, t]);
      }
    }
    const left = [], right = [];
    for (const [x, y, nx, ny, t] of along) {
      const h = (ws + (we - ws) * t) / 2;
      left.push(x + nx * h, y + ny * h);
      right.unshift(x - nx * h, y - ny * h);
    }
    const ring = [...left, ...right];
    ring.push(ring[0], ring[1]);
    loops.push(ring);
    // the travel direction at each end is the left normal turned a quarter clockwise
    const f = along[0], l = along[along.length - 1];
    ends.push({ i, start: { x: f[0], y: f[1], tx: f[3], ty: -f[2], h: ws / 2 }, end: { x: l[0], y: l[1], tx: l[3], ty: -l[2], h: we / 2 } });

Corner between two wide segments

64-bit

The wedge that fills the outside gap where one wide segment meets the next.

cross = tₐ × t_b; s = ((P₂ − P₁) × t_b) ÷ cross; X = P₁ + s·tₐ; used when s ≥ 0 and |X − corner| ≤ 10 × max(hₐ, h_b)

The miter point is the intersection of the two outer edges, divided by the cross product of the two unit directions. The division is done only when |cross| > 1e-9; a sharper miter than 10 half widths is cut straight across instead. The test that the two segments share an end is scaled to the coordinates and the half width.

  • walk.js
  • lines 313 to 332
  • CadCraft 0.8.2
for (let k = 0; k < ends.length; k++) {
  const A = ends[k], B = ends[k + 1] || (e.closed && ends.length > 1 ? ends[0] : null);
  if (!B || B === A || !(A.end.h > 0) || !(B.start.h > 0)) continue;
  const a = A.end, b = B.start;
  // the next wide segment starts where this one ends (repeated vertices between them are skipped above)
  if (Math.hypot(a.x - b.x, a.y - b.y) > 1e-9 * Math.max(1, Math.abs(a.x), Math.abs(a.y), a.h)) continue;
  const cross = a.tx * b.ty - a.ty * b.tx, dot = a.tx * b.tx + a.ty * b.ty;
  if (Math.abs(cross) < 1e-9 && dot > 0) continue;   // straight on
  const side = cross > 0 ? -1 : 1;   // a left turn opens the gap on the right
  const P1 = { x: a.x - side * a.ty * a.h, y: a.y + side * a.tx * a.h }, P2 = { x: b.x - side * b.ty * b.h, y: b.y + side * b.tx * b.h };
  let X = null;
  if (Math.abs(cross) > 1e-9) {   // P1 + s·ta = P2 + u·tb
    const s = ((P2.x - P1.x) * b.ty - (P2.y - P1.y) * b.tx) / cross;
    const c = { x: P1.x + s * a.tx, y: P1.y + s * a.ty };
    if (s >= 0 && Math.hypot(c.x - a.x, c.y - a.y) <= 10 * Math.max(a.h, b.h)) X = c;
  }
  const wedge = X ? [a.x, a.y, P1.x, P1.y, X.x, X.y, P2.x, P2.y] : [a.x, a.y, P1.x, P1.y, P2.x, P2.y];
  wedge.push(wedge[0], wedge[1]);
  loops.push(wedge);
}

Text background mask

64-bit

The rectangle painted behind a text: its box grown by a margin and turned with the text.

m = max(0, scale − 1) × height; corner = (x, y) + R(rot) · (x₀ − m, y₀ − m) …

The box comes from textLayout in geom.js; the margin and the rotation are plain 64-bit expressions with one sine and one cosine. No tolerance is used.

  • walk.js
  • lines 199 to 212
  • CadCraft 0.8.2
/**
 * A text's background mask (WL.8) as a ring [x, y, …]: the text's box — its wrap width when it has one — grown by
 * (scale − 1) × the text height on every side, as the other program's "border offset factor" (1.5 = half a height).
 */
export function maskLoop(e, scale = 1.5) {
  const lay = textLayout(e), b = lay.box, m = Math.max(0, (Number.isFinite(scale) ? scale : 1.5) - 1) * e.h;
  let x0 = b.x, x1 = b.x + b.w;
  if (e.ww > 0 && e.ww > b.w) {   // the paragraph's own width, placed as its alignment places it
    if (e.ha === 'center') { const c = (x0 + x1) / 2; x0 = c - e.ww / 2; x1 = c + e.ww / 2; } else if (e.ha === 'right') x0 = x1 - e.ww; else x1 = x0 + e.ww;
  }
  const c = Math.cos(e.rot || 0), s = Math.sin(e.rot || 0), P = (x, y) => [e.x + x * c - y * s, e.y + x * s + y * c];
  const pts = [P(x0 - m, b.y - m), P(x1 + m, b.y - m), P(x1 + m, b.y + b.h + m), P(x0 - m, b.y + b.h + m)];
  return [...pts.flat(), ...pts[0]];
}

Ring direction

64-bit

Turns a ring clockwise so that overlapping rings add up when filled.

a = Σ (xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ); a > 0 → reverse the points

Only the sign of the shoelace sum is used. The sum is taken about the coordinate origin, so for a thin ring far from the origin the sign rests on a difference of large products.

  • walk.js
  • lines 336 to 344
  • CadCraft 0.8.2
/** A ring [x, y, …] turned clockwise (negative area), so rings filled together add up instead of cancelling. */
export function clockwise(l) {
  let a = 0;
  for (let i = 0; i + 3 < l.length; i += 2) a += l[i] * l[i + 3] - l[i + 2] * l[i + 1];
  if (a <= 0) return l;
  const out = [];
  for (let i = l.length - 2; i >= 0; i -= 2) out.push(l[i], l[i + 1]);
  return out;
}

Ellipse as line pieces

64-bit

The line pieces an ellipse is drawn and plotted with.

The ellipse is asked for 96 points (ellipsePoints in geom.js) and neighbors are joined with straight lines, so the drawn ellipse is made of straight pieces. The stored ellipse itself is not changed.

  • walk.js
  • lines 152 to 156
  • CadCraft 0.8.2
case 'ellipse': {
  const pts = ellipsePoints(e, 96);
  const ps = [];
  for (let i = 0; i + 1 < pts.length; i++) ps.push({ k: 'L', x1: pts[i].x, y1: pts[i].y, x2: pts[i + 1].x, y2: pts[i + 1].y });
  strokeOf(e, ps, color, lw, mm, ctx, o);

Linetype scale of an object

64-bit

The factor that sizes the dashes of an object's linetype.

scale = LTSCALE × object scale × plot style table scale (non-ISO linetypes only)

A product of up to three 64-bit factors; a missing or non-positive LTSCALE or object scale counts as 1. The dashes are cut in the object's own coordinates before the transform is applied.

  • walk.js
  • lines 78 to 86
  • CadCraft 0.8.2
const strokeOf = (e, ps, color, lw, mm, ctx, o) => {
  // a plot style table's pen may name another linetype for this colour (penLt, 0.7 DC.14) and scale the dashes of non-ISO ones (ltTable)
  const ltName = (penLt && penLt(color)) || resolveLt(doc, e, ctx.lt, ctx.layer);
  const pat = pattern(ltName);
  const sc = ltscale * (e.lts > 0 ? e.lts : 1) * (pat && ltTable !== 1 && !isIsoLinetype(ltName) ? ltTable : 1);
  // a polyline without linetype generation (lgen false, PLINEGEN off in the file) starts its pattern again at each vertex
  const d = !pat ? ps : e.type === 'poly' && e.lgen === false && ps.length > 1 ? ps.flatMap((q) => dashPrims([q], pat, sc)) : dashPrims(ps, pat, sc);
  out.stroke(color, mm ? d.flatMap((q) => txPrim(q, mm)) : d, lw, o);
};

In detail

Method
Left and right offsets along the unit normal; mitered corners from the intersection of the two outer edges; shoelace sum for ring direction.
Number types
64-bit numbers; rings are plain arrays [x, y, x, y, …].
Tolerances
A segment shorter than 1e-12 (absolute) gets no band. Two wide segments count as joined when their ends are within 1e-9 × max(1, |x|, |y|, half width). Directions with a cross product below 1e-9 count as straight on. A miter is used only within 10 × the larger half width of the corner.
Checked by
bin/test-cadcraft.mjs calls polyBands on a 2-wide straight segment and checks that the band runs from y = −1 to y = 1.
Limits
A wide arc is a polygon with a vertex every 10 degrees or less; an ellipse is drawn through 96 points.

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.

Every policy that takes this approach