Source code of plot #061 back to plot

import {kdTree} from "../thirdparty/kdTree.js";

export class Vec2 {

  constructor(x = 0, y = 0) {
    this.x = x;
    this.y = y;
  }

  set(x, y) {
    this.x = x;
    this.y = y;
    return this;
  }

  equals(other) {
    return this.x == other.x && this.y == other.y;
  }

  clone() {
    return new Vec2(this.x, this.y);
  }

  setFrom(other) {
    this.x = other.x;
    this.y = other.y;
    return this;
  }

  cross(other) {
    return cross2(this, other);
  }

  dot(other) {
    return dot2(this, other);
  }

  add(other) {
    this.x += other.x;
    this.y += other.y;
    return this;
  }

  addMul(other, r) {
    this.x += other.x * r;
    this.y += other.y * r;
    return this;
  }

  sub(other) {
    this.x -= other.x;
    this.y -= other.y;
    return this;
  }

  rot(rad) {
    const [x, y] = [this.x, this.y];
    this.x = x * Math.cos(rad) - y * Math.sin(rad);
    this.y = x * Math.sin(rad) + y * Math.cos(rad);
    return this;
  }

  angle() {
    return Math.atan2(this.y, this.x);
  }

  length() {
    return Math.sqrt(this.x ** 2 + this.y ** 2);
  }

  mul(scalar) {
    this.x *= scalar;
    this.y *= scalar;
    return this;
  }

  normalize() {
    const len = this.length();
    this.mul(1 / len);
    return this;
  }
}

export function dist2(a, b) {
  return Math.sqrt((a.x-b.x) ** 2 + (a.y-b.y) ** 2);
}

export function add2(a, b) {
  const vec = a.clone();
  vec.add(b);
  return vec;
}

export function sub2(a, b) {
  const vec = a.clone();
  vec.sub(b);
  return vec;
}

export function cross2(a, b) {
  return a.x * b.y - a.y * b.x;
}

export function dot2(a, b) {
  return a.x * b.x + a.y * b.y;
}

// UNTESTED
// export function isInsideTriangle2(a, b, c, pt) {
//   // https://stackoverflow.com/a/20861130
//   const s = (a.x - c.x) * (pt.y - c.y) - (a.y - c.y) * (pt.x - c.x);
//   const t = (b.x - a.x) * (pt.y - a.y) - (b.y - a.y) * (pt.x - a.x);
//   if ((s < 0) != (t < 0) && s != 0 && t != 0)
//     return false;
//   const d = (c.x - b.x) * (pt.y - b.y) - (c.y - b.y) * (pt.x - b.x);
//   return d == 0 || (d < 0) == (s + t <= 0);
// }

export function bounds2(pts, xtra = 0) {
  const bounds = {
    top: Number.MAX_VALUE,
    bottom: Number.MIN_VALUE,
    left: Number.MAX_VALUE,
    right: Number.MIN_VALUE,
  };
  for (const pt of pts) {
    bounds.top = Math.min(bounds.top, pt.y - xtra);
    bounds.bottom = Math.max(bounds.bottom, pt.y + xtra);
    bounds.left = Math.min(bounds.left, pt.x - xtra);
    bounds.right = Math.max(bounds.right, pt.x + xtra);
  }
  bounds.width = bounds.right - bounds.left;
  bounds.height = bounds.bottom - bounds.top;
  return bounds;
}

// Merges segments (point pairs) so each line section is covered only once
// Joins coniguous and overlapping segments
export function mergeSegments(segs, epsilon = 0.005) {

  // http://www.sunshine2k.de/coding/javascript/lineintersection2d/LineIntersect2D.html
  // https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/563240#563240

  const res = [];
  while (segs.length > 0) {
    // Gather coincident segments
    const csegs = [segs.pop()];
    for (let i = 0; i < segs.length; /*NOP*/) {
      const s = segs[i];
      if (areCoincident(csegs[0], s, epsilon)) {
        csegs.push(s);
        segs.splice(i, 1);
      }
      else ++i;
    }
    const mergedSegs = mergCoincidentSegs(csegs);
    res.push(...mergedSegs);
  }
  return res;
}

// Given an array of provent coincident segments, joins those that overlap or are contiguous
function mergCoincidentSegs(segs) {
  if (segs.length < 2) return segs;
  const res = [];
  while (segs.length > 0) {
    const base = segs.pop();
    let couldMerge = false;
    for (let i = 0; i < segs.length; /*NOP*/) {
      const merged = mergeIfOverlapping(base, segs[i]);
      if (merged != null) {
        couldMerge = true;
        segs[i] = merged;
        break;
      }
      else ++i;
    }
    if (!couldMerge) res.push(base);
  }
  return res;
}

const _moA = new Vec2(0, 0);
const _moB = new Vec2(0, 0);
const _moU = new Vec2(0, 0);

// Returns a merged segment if segments overlap / are contiguous, or null if they don't
function mergeIfOverlapping([a0, a1], [b0, b1]) {
  _moA.setFrom(a1);
  _moA.sub(a0);
  _moB.setFrom(b1);
  _moB.sub(b0);
  _moU.setFrom(b0);
  _moU.sub(a0);
  const aDot = _moA.dot(_moA);
  const t0 = _moU.dot(_moA) / aDot;
  const t1 = t0 + _moB.dot(_moA) / aDot;
  // b is entirely inside a
  if (t0 >= 0 && t0 <= 1 && t1 >= 0 && t1 <= 1) return [a0, a1];
  // b contains all of a
  else if (t0 <= 0 && t1 >= 1 || t0 >= 1 && t1 <= 0) return [b0, b1];
  // b0 inside a
  else if (t0 >= 0 && t0 <= 1) {
    if (t1 < 0) return [b1, a1];
    else return [a0, b1];
  }
  // b1 inside a
  else if (t1 >= 0 && t1 <= 1) {
    if (t0 < 0) return [b0, a1];
    else return [a0, b0];
  }
  return null;

  function near(t, val) {
    return Math.abs(t - val) < 1e-5;
  }
}

const _acA = new Vec2(0, 0);
const _acB = new Vec2(0, 0);
const _acU = new Vec2(0, 0);

// Checks if two line segments are coincident (on the same line)
export function areCoincident([a0, a1], [b0, b1], epsilon) {

  _acA.setFrom(a1);
  _acA.sub(a0);
  _acA.normalize();
  _acB.setFrom(b1);
  _acB.sub(b0);
  _acB.normalize();

  // cross2(a, b) not "zero": not parallel; hence, not coincident either
  const cpAB = cross2(_acA, _acB);
  if (Math.abs(cpAB) > epsilon) return false;

  _acU.setFrom(b0);
  _acU.sub(a0);
  _acU.normalize();
  // cross2(a, u) not zero: real parallel, i.e., not coincident
  const cpAU = cross2(_acA, _acU);
  if (Math.abs(cpAU) > epsilon) return false;

  return true;
}

// dbg();

// DBG
function dbg() {
  let a, b, c, d, e, f, g, h, i, j, k, l;
  a = [
    new Vec2(1, 1),
    new Vec2(5, 1),
  ];
  b = [
    new Vec2(0, 1),
    new Vec2(1, 1),
  ];
  const m = mergeIfOverlapping(a, b);
  // console.log(m);

  // [244.24, 228.58] - [243.96, 227.18]
  // [244.24, 228.58] - [211.28, 235.08]
  // [241.34, 213.96] - [244.24, 228.58]
  a = [new Vec2(244.24, 228.58), new Vec2(243.96, 227.18)];
  b = [new Vec2(244.24, 228.58), new Vec2(211.28, 235.08)];
  c = [new Vec2(241.34, 213.96), new Vec2(244.24, 228.58)];
  const ms = mergeSegments([a, b, c]);
  console.log(ms);
}

// DBG
function logPts(pts) {
  let str = "";
  for (let j = 0; j < pts.length; ++j) {
    const pt = pts[j];
    if (str != "") str += " - ";
    str += `[${pt.x}, ${pt.y}]`;
  }
  console.log(str);
}

// Recursively joins all paths whose ends meet
export function joinPaths(paths, allowedGap = 0.5) {
  const kdt = new kdTree([], (a, b) => Math.sqrt((a.x-b.x)**2 + (a.y-b.y)**2), ["x", "y"]);
  for (const p of paths) {
    const a = new Vec2(p.pts[0].x, p.pts[0].y);
    const b = new Vec2(p.pts[p.pts.length - 1].x, p.pts[p.pts.length - 1].y);
    a.path = b.path = p;
    a.otherEnd = b;
    b.otherEnd = a;
    kdt.insert(a);
    kdt.insert(b);
  }
  const res = [];
  const pos = new Vec2(0, 0);
  while (true) {
    // Get point that's nearest to where we last finished
    const nearest = kdt.nearest(pos, 1, Number.MAX_VALUE);
    if (nearest.length == 0) break;
    const x = nearest[0][0];
    let pts = [...x.path.pts];
    kdt.remove(x);
    kdt.remove(x.otherEnd);
    // Grow forward, and backward
    while (true) {
      const lenBefore = pts.length;
      grow(pts, false);
      grow(pts, true);
      if (pts.length == lenBefore) break;
    }
    res.push(pts);
    pos.setFrom(pts[pts.length-1]);
  }
  return res;

  function grow(pts, isFwd) {
    const end = pts[isFwd ? pts.length - 1 : 0];
    const nearest = kdt.nearest(end, 1, allowedGap);
    if (nearest.length == 0) return;
    const nextX = nearest[0][0];
    const dist = nearest[0][1];
    kdt.remove(nextX);
    kdt.remove(nextX.otherEnd);
    const nextPts = nextX.path.pts;
    let reverse = false;
    if (dist == 0) {
      reverse = nextPts[nextPts.length-1].equals(end);
    }
    else {
      const distFirst = dist2(end, nextPts[0]);
      const distLast = dist2(end, nextPts[nextPts.length-1]);
      if (distLast < distFirst)
        reverse = true;
    }
    const append = isFwd
      ? pt => pts.push(pt)
      : pt => pts.unshift(pt);
    if (!reverse) for (let i = 1; i < nextPts.length; ++i) append(nextPts[i]);
    else for (let i = nextPts.length - 2; i >= 0; --i) append(nextPts[i]);
  }
}

// Optimizes order of paths to reduce pen-up travel. Reverses paths where it helps.
export function optimizePathOrder(paths) {
  const kdt = new kdTree([], (a, b) => Math.sqrt((a.x-b.x)**2 + (a.y-b.y)**2), ["x", "y"]);
  for (const pts of paths) {
    const a = new Vec2(pts[0].x, pts[0].y);
    const b = new Vec2(pts[pts.length - 1].x, pts[pts.length - 1].y);
    a.pts = b.pts = pts;
    a.otherEnd = b;
    b.otherEnd = a;
    kdt.insert(a);
    kdt.insert(b);
  }
  const res = [];
  const pos = new Vec2(0, 0);
  while (true) {
    // Get point that's nearest to where we last finished
    const nearest = kdt.nearest(pos, 1, Number.MAX_VALUE);
    if (nearest.length == 0) break;
    const x = nearest[0][0];
    let pts = [...x.pts];
    kdt.remove(x);
    kdt.remove(x.otherEnd);
    // Reverse if needed
    const distFirst = dist2(pos, pts[0]);
    const distLast = dist2(pos, pts[pts.length-1]);
    if (distLast < distFirst) pts.reverse();
    res.push(pts);
    pos.setFrom(pts[pts.length-1]);
  }
  return res;
}


export class Vec3 {

  constructor(x = 0, y = 0, z = 0) {
    this.x = x;
    this.y = y;
    this.z = z;
  }

  set(x, y, z) {
    this.x = x;
    this.y = y;
    this.z = z;
    return this;
  }

  clone() {
    return new Vec3(this.x, this.y, this.z);
  }

  setFrom(other) {
    this.x = other.x;
    this.y = other.y;
    this.z = other.z;
    return this;
  }

  add(other) {
    this.x += other.x;
    this.y += other.y;
    this.z += other.z;
    return this;
  }

  addMul(other, r) {
    this.x += other.x * r;
    this.y += other.y * r;
    this.z += other.z * r;
    return this;
  }

  sub(other) {
    this.x -= other.x;
    this.y -= other.y;
    this.z -= other.z;
    return this;
  }

  length() {
    return Math.sqrt(this.x ** 2 + this.y ** 2 + this.z ** 2);
  }

  normalize() {
    const len = this.length();
    this.mul(1 / len);
    return this;
  }

  mul(scalar) {
    this.x *= scalar;
    this.y *= scalar;
    this.z *= scalar;
    return this;
  }

  dot(v) {
    return this.x * v.x + this.y * v.y + this.z * v.z;
  }

  cross(v) {
    const ax = this.x, ay = this.y, az = this.z;
    const bx = v.x, by = v.y, bz = v.z;
    this.x = ay * bz - az * by;
    this.y = az * bx - ax * bz;
    this.z = ax * by - ay * bx;
    return this;
  }

  rotx(angle) {
    const sin = Math.sin(angle);
    const cos = Math.cos(angle);
    this.y = cos * this.y - sin * this.z;
    this.z = sin * this.y + cos * this.z;
    return this;
  }

  roty(angle) {
    const sin = Math.sin(angle);
    const cos = Math.cos(angle);
    this.x = this.x * cos + this.z * sin;
    this.z = this.x * (-sin) + this.z * cos;
    return this;
  }

  rotZ(vector, angle) {
    const sin = Math.sin(angle);
    const cos = Math.cos(angle);
    this.x = this.x * cos - this.y * sin;
    this.y = this.x * sin + this.y * cos;
    return this;
  }
}

export function cross3(a, b) {
  return a.clone().cross(b);
}

export function sub3(a, b) {
  return a.clone().sub(b);
}

export function dist3(a, b) {
  return Math.sqrt((b.x-a.x)**2 + (b.y-a.y)**2 + (b.z-a.z)**2);
}