Published
Edited
Mar 18, 2020
Importers
testData = [
{ y: 423962436, x: -710998953, t: 1583084540 },
{ y: 423946736, y: -710823379, t: 1583085476 },
]
function slog(label, x) {
console.log(`${label}: ${x}`);
return x;
}
function sq(x) {
return x * x;
}
function remapPt(pt, cx, cy, lonToM, latToM) {
return {
x: lonToM * (pt.x - cx),
y: latToM * (pt.y - cy),
t: pt.t
}
}
function flatEarth(p, q) {
// Convert distances to meters using the center of the segments as the effective latitude
const cy = (p[0].y + p[1].y + q[0].y + q[1].y) / 4;
const cx = (p[0].x + p[1].x + q[0].x + q[1].x) / 4;
const latToM = 111111 / 1e7;
const lonToM = 111111 * Math.cos(cy * Math.PI / 180) / 1e7;
return [[remapPt(p[0], cx, cy, lonToM, latToM),
remapPt(p[1], cx, cy, lonToM, latToM)],
[remapPt(q[0], cx, cy, lonToM, latToM),
remapPt(q[1], cx, cy, lonToM, latToM)]]
}
flatEarth([{x: 0, y: 0, t: 0}, {x: 0, y: 1000, t: 1}],
[{x: 0, y: 0, t: 0}, {x: 1000, y: 0, t: 1}])
function pathsIntersect(p, q, d) {
// Reset time to starting from 0
const t0 = 0;
const t1 = p[1].t - p[0].t;
const dt = t1 - t0;
const x0 = p[0].x;
const y0 = p[0].y;
const a0 = q[0].x;
const b0 = q[0].y;
const dx = p[1].x - p[0].x;
const dy = p[1].y - p[0].y;
const da = q[1].x - q[0].x;
const db = q[1].y - q[0].y;
const A = (sq(dx - da) + sq(dy - db)) / sq(dt);
const B = 2 * ( (dx - da) * (x0 - a0) + (dy -db) * (y0 - b0) ) / dt;
const C = sq(x0 - a0) + sq(y0 - b0) - sq(d);
const D = sq(B) - 4 * A * C;
console.log({A, B, C, D});
if (D < 0 || A == 0) {
return false;
}
const sD = Math.sqrt(D);
const T1 = (-B + sD) / (2 * A);
const T2 = (-B - sD) / (2 * A);
console.log({T1, T2});
const lowT = Math.min(T1, T2);
const highT = Math.max(T1, T2);
if ((t0 < lowT && t1 < lowT) || (t0 > highT && t1 > highT)) {
return false;
}
return true;
}
pathsIntersect(
[{x: -42, y: -48, t: 0},
{x: 55, y: 62, t: 100}],
[{x: -27, y: -95, t: 0},
{x: 14, y: 80, t: 100}],
100
)
pathsIntersect(
[{ x: 0.5, y: 0.5, t: 0.5 },
{ x: 1.5, y: 1.5, t: 1.5 }],
[{ x: 1.5, y: 0.5, t: 0.5 },
{ x: 2.5, y: 1.5, t: 1.5 }],
0
)
pathsIntersect(
[{x: -1, y: 0, t: 0}, {x: 1, y: 0, t: 10}],
[{x: 0, y: -1, t: 0}, {x: 0, y: 1, t: 10}],
1)
pathsIntersect(
[{x: 1, y: 0, t: 0}, {x: 3, y: 0, t: 10}],
[{x: 0, y: 1, t: 0}, {x: 0, y: 3, t: 10}],
2)
pathsIntersect(
[{ x: 0.5, y: 0.5, t: 0.0 },
{ x: 0.5, y: 0.5, t: 1.0 }],
[{ x: 0.1, y: 0.0, t: 0.0 },
{ x: 1.0, y: 1.0, t: 1.0 }],
0
);
function shortestDistanceSquared(p, q) {
console.assert(p[0].t == q[0].t && p[1].t == q[1].t, "Adjust times before testing for shortest distance");
const t0 = p[0].t;
const t1 = p[1].t;
const dt = t1 - t0;
const x0 = p[0].x;
const y0 = p[0].y;
const a0 = q[0].x;
const b0 = q[0].y;
const dx = p[1].x - p[0].x;
const dy = p[1].y - p[0].y;
const da = q[1].x - q[0].x;
const db = q[1].y - q[0].y;
const denominator = (dx - da) * (dx - da) + (dy - db) * (dy - db);
let tmin = t0;
if (denominator != 0) {
tmin = t0 - dt * ((x0 - a0) * (dx - da) + (y0 - b0) * (dy - db)) / denominator;
}
console.log(tmin);
if (tmin < t0) tmin = t0;
if (tmin > t1) tmin = t1;
const xmin = x0 + tmin * dx / dt;
const ymin = y0 + tmin * dy / dt;
const amin = a0 + tmin * da / dt;
const bmin = b0 + tmin * db / dt;
return (xmin - amin) * (xmin - amin) + (ymin - bmin) * (ymin - bmin);
}
// should be 0
shortestDistanceSquared([{x: -1, y: 0, t: 0}, {x: 1, y: 0, t: 10}],
[{x: 0, y: -1, t: 0}, {x: 0, y: 1, t: 10}])
shortestDistanceSquared([{x: 1, y: 0, t: 0}, {x: 3, y: 0, t: 10}],
[{x: 0, y: 1, t: 0}, {x: 0, y: 3, t: 10}])
function modifySegment(p, t0, t1) {
const dx = p[1].x - p[0].x;
const dy = p[1].y - p[0].y;
const dt = p[1].t - p[0].t;
const q = [{}, {}];
q[0].x = p[0].x + (t0 - p[0].t) * dx / dt;
q[0].y = p[0].y + (t0 - p[0].t) * dy / dt;
q[0].t = t0;
q[1].x = p[1].x + (t1 - p[1].t) * dx / dt;
q[1].y = p[1].y + (t1 - p[1].t) * dy / dt;
q[1].t = t1;
return q;
}
modifySegment([{x: 0, y: 0, t: 0}, {x: 10, y: 10, t: 10}], 2, 8)
function overlapTime(p, q) {
console.assert(p[0].t < p[1].t && q[0].t < q[1].t);
if (p[1].t < q[0].t || q[1].t < p[0].t)
return []
const t0 = Math.max(p[0].t, q[0].t);
const t1 = Math.min(p[1].t, q[1].t);
return [modifySegment(p, t0, t1), modifySegment(q, t0, t1)];
}
overlapTime([{x: 0, y: 0, t: 0}, {x: 10, y: 10, t: 10}],
[{x: 0, y: 0, t: 8}, {x: -4, y: -4, t: 12}])
overlapTime([{x: 0, y: 0, t: 0}, {x: 10, y: 10, t: 10}],
[{x: 0, y: 0, t: 12}, {x: -4, y: -4, t: 14}])
function intersectsWithBuffer(p, q, d) {
console.log("Testing:", p, q, d);
p = [p.start, p.end];
q = [q.start, q.end];
const overlapped = overlapTime(p, q);
console.assert(pathsIntersect(p, q, Math.sqrt(sq(d.x) + sq(d.y))));
}
function assert() {
}
{
assert(intersectsWithBuffer(
{
start: { x: 0.5, y: 0.5, t: 0.5 },
end: { x: 1.5, y: 1.5, t: 1.5 },
},
{
start: { x: 0.5, y: 0.5, t: 0.5 },
end: { x: 1.5, y: 1.5, t: 1.5 },
},
{ x: 0, y: 0, t: 0 }
));
assert(!intersectsWithBuffer(
{
start: { x: 0.5, y: 0.5, t: 0.5 },
end: { x: 1.5, y: 1.5, t: 1.5 },
},
{
start: { x: 1.5, y: 0.5, t: 0.5 },
end: { x: 2.5, y: 1.5, t: 1.5 },
},
{ x: 0, y: 0, t: 0 }
));
assert(intersectsWithBuffer(
{
start: { x: 0.5, y: 0.5, t: 0.5 },
end: { x: 1.5, y: 1.5, t: 1.5 },
},
{
start: { x: 1.0, y: 0.5, t: 0.5 },
end: { x: 2.0, y: 1.5, t: 1.5 },
},
{ x: 0.5, y: 0, t: 0 }
));
assert(intersectsWithBuffer(
{
start: { x: 0.5, y: 0.5, t: 0.0 },
end: { x: 0.5, y: 0.5, t: 1.0 },
},
{
start: { x: 0.0, y: 0.0, t: 0.0 },
end: { x: 1.0, y: 1.0, t: 1.0 },
},
{ x: 0, y: 0, t: 0 }
));
assert(!intersectsWithBuffer(
{
start: { x: 0.5, y: 0.5, t: 0.0 },
end: { x: 0.5, y: 0.5, t: 1.0 },
},
{
start: { x: 0.1, y: 0.0, t: 0.0 },
end: { x: 1.0, y: 1.0, t: 1.0 },
},
{ x: 0, y: 0, t: 0 }
));
assert(intersectsWithBuffer(
{
start: { x: 0.5, y: 0.5, t: 0.0 },
end: { x: 0.5, y: 0.5, t: 1.0 },
},
{
start: { x: 0.1, y: 0.0, t: 0.0 },
end: { x: 1.0, y: 1.0, t: 1.0 },
},
{ x: 0.05, y: 0, t: 0 }
));
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
