Source code of plot #060 back to plot
Download full working sketch as 060.tar.gz.
Unzip, then start a local web server and load the page in a browser.
Unless otherwise noted, code published here is © Gábor L Ugray, shared under the Creative Commons
BY-NC-SA license (Attribution, Non-Commercial, Share-Alike). Files in lib/thirdparty
, and additional
libraries in the downloadable archive, are shared under their respective open-source licenses, attributed
to their authors.
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);
}