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 }
));
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.