Source code of plot #065 back to plot

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);
  }

  isNull() {
    return this.x == 0 && this.y == 0;
  }

  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();
    return this.mul(1 / len);
  }

  setLength(len) {
    return this.mul(len / this.length());
  }

  distToLine(linePt, lineAngle) {
    // Direction vector of the line
    const dx = Math.cos(lineAngle);
    const dy = Math.sin(lineAngle);

    // Vector from line point to this point
    const px = this.x - linePt.x;
    const py = this.y - linePt.y;

    // Cross product magnitude divided by line length
    // Line length is 1 because dx, dy is unit vector
    const distance = Math.abs(px * dy - py * dx);

    return distance;
  }

  fromLineSegmentIsect(linePt, lineAngle, a, b) {
    const dx = Math.cos(lineAngle), dy = Math.sin(lineAngle);
    const sx = b.x - a.x, sy = b.y - a.y;
    const denom = dx * (-sy) + dy * sx;

    // Parallel
    if (Math.abs(denom) < 1e-12) return false;

    const lx = a.x - linePt.x;
    const ly = a.y - linePt.y;

    const t = (lx * (-sy) + ly * sx) / denom; // line parameter
    const u = (dx * ly - dy * lx) / denom; // segment parameter

    // intersection not on segment
    if (u < 0 || u > 1) return false;

    this.x = linePt.x + t * dx;
    this.y = linePt.y + t * dy;
    return true;
  }
}

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;
}

export function angle2(a, b) {
  const dot = dot2(a, b);
  return Math.acos(dot / (a.length() * b.length()));
}

// Signed angle (-PI..PI), clockwise from a to b is positive.
export function signedAngle2(a, b) {
  return Math.atan2(
    a.x * b.y - a.y * b.x,
    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);
}



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();
    return this.mul(1 / len);
  }

  setLength(len) {
    return this.mul(len / this.length());
  }

  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;
  }

  applyAxisAngle(axis, angle) {
    // Stolne ThreeJS Vector3
    // Make a quaternion for this rotation
    const halfAngle = angle / 2, s = Math.sin(halfAngle);
    const q = {
      x: axis.x * s,
      y: axis.y * s,
      z: axis.z * s,
      w: Math.cos(halfAngle),
    };
    // Apply quaternion to me
    // quaternion q is assumed to have unit length
    const vx = this.x, vy = this.y, vz = this.z;
    const qx = q.x, qy = q.y, qz = q.z, qw = q.w;
    const tx = 2 * (qy * vz - qz * vy);
    const ty = 2 * (qz * vx - qx * vz);
    const tz = 2 * (qx * vy - qy * vx);
    this.x = vx + qw * tx + qy * tz - qz * ty;
    this.y = vy + qw * ty + qz * tx - qx * tz;
    this.z = vz + qw * tz + qx * ty - qy * tx;
    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);
}