design+data+people nerd ❦ previously partner at IDEO, co-founded Datascope
Public
Edited
Dec 2, 2023
Paused
Importers
2 stars
function getIntersectionsCheckBounds(polyline1, polyline2) {
let bbox1 = getBoundingBox(polyline1);
let bbox2 = getBoundingBox(polyline2);
let bboxIntersection = getBoundingBoxIntersection(bbox1, bbox2);
if (!bboxIntersection) {
return [];
}
let segments1 = getSegmentsTouchingBox(polyline1, bboxIntersection);
let segments2 = getSegmentsTouchingBox(polyline2, bboxIntersection);
let intersections = [];
segments1.forEach(function (one) {
segments2.forEach(function (two) {
let intersect = checkIntersection(one, two);
if (intersect) {
intersections.push(intersect);
}
});
});
return intersections;
}
function areCollinear(p1, p2, p3) {
return (
p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y) === 0
);
}
// adapted from https://stackoverflow.com/a/15812696/1431778, almost certainly way too complicated!
function collinearIntersection([a, b], [c, d], x = "x") {
if (!areCollinear(a, b, c)) {
return null;
}
let aa, bb, cc, dd;
if (a[x] < b[x]) {
aa = a;
bb = b;
} else if (a[x] === b[x]) {
return collinearIntersection([a, b], [c, d], "y");
} else {
aa = b;
bb = a;
}
if (c[x] < d[x]) {
cc = c;
dd = d;
} else {
cc = d;
dd = c;
}
if (bb[x] - cc[x] >= 0 && dd[x] - aa[x] >= 0) {
let result = [];
if (aa[x] > cc[x]) {
result.push(aa);
} else {
result.push(cc);
}
if (bb[x] > dd[x]) {
result.push(dd);
} else {
result.push(bb);
}
return {
x: (result[0].x + result[1].x) / 2,
y: (result[0].y + result[1].y) / 2
};
} else {
return null;
}
return [aa, bb, cc, dd];
}
// adapted from https://paulbourke.net/geometry/pointlineplane/
function checkIntersection([a, b], [c, d]) {
let x1 = a.x,
y1 = a.y,
x2 = b.x,
y2 = b.y,
x3 = c.x,
y3 = c.y,
x4 = d.x,
y4 = d.y;
// Check if any of the lines are of length 0
if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) {
return null;
}
const denominator = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
// Lines are parallel
if (denominator === 0) {
return collinearIntersection([a, b], [c, d]);
}
let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator;
let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator;
// is the intersection along the segments
if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {
return null;
}
// Return x and y coordinates of the intersection
return {
x: x1 + ua * (x2 - x1),
y: y1 + ua * (y2 - y1)
};
}
function getBoundingBox(polyline) {
if (polyline.length === 0) {
return null;
}
let minX = polyline[0].x;
let maxX = polyline[0].x;
let minY = polyline[0].y;
let maxY = polyline[0].y;
for (let i = 1; i < polyline.length; i++) {
minX = Math.min(minX, polyline[i].x);
maxX = Math.max(maxX, polyline[i].x);
minY = Math.min(minY, polyline[i].y);
maxY = Math.max(maxY, polyline[i].y);
}
return {
minX: minX,
maxX: maxX,
minY: minY,
maxY: maxY
};
}
function getSegmentsTouchingBox(polyline, box) {
let segments = [];
for (let i = 0; i < polyline.length - 1; i++) {
let a = polyline[i];
let b = polyline[i + 1];
if (isSegmentTouchingBox(a, b, box)) {
segments.push([a, b]);
}
}
return segments;
}
function getBoundingBoxIntersection(box1, box2) {
let intersectMinX = Math.max(box1.minX, box2.minX);
let intersectMaxX = Math.min(box1.maxX, box2.maxX);
let intersectMinY = Math.max(box1.minY, box2.minY);
let intersectMaxY = Math.min(box1.maxY, box2.maxY);
if (intersectMinX <= intersectMaxX && intersectMinY <= intersectMaxY) {
return {
minX: intersectMinX,
maxX: intersectMaxX,
minY: intersectMinY,
maxY: intersectMaxY
};
} else {
return null;
}
}
function isSegmentTouchingBox(a, b, box) {
const lineBox = getBoundingBox([a, b]);
return Boolean(getBoundingBoxIntersection(lineBox, box));
}
function* iterSegments(polyline) {
for (let i = 0; i < polyline.length - 1; i++) {
yield [polyline[i], polyline[i + 1]];
}
}
function makeIndex(polyline) {
const index = new Flatbush(polyline.length - 1);
for (let segment of iterSegments(polyline)) {
let bb = getBoundingBox(segment);
index.add(bb.minX, bb.minY, bb.maxX, bb.maxY);
}
index.finish();
return index;
}
function getIntersectionsIndex(polyline1, polyline2) {
let iterateOver, indexLine;
if (polyline1.length < polyline2.length) {
iterateOver = polyline1;
indexLine = polyline2;
} else {
iterateOver = polyline2;
indexLine = polyline1;
}
const index = makeIndex(indexLine);
let intersections = [];
for (let i = 0; i < iterateOver.length - 1; i++) {
let one = [iterateOver[i], iterateOver[i + 1]];
let bbOne = getBoundingBox(one);
index
.search(bbOne.minX, bbOne.minY, bbOne.maxX, bbOne.maxY)
.forEach(function (j) {
let two = [indexLine[j], indexLine[j + 1]];
let intersect = checkIntersection(one, two);
if (intersect) {
intersections.push(intersect);
}
});
}
return intersections;
}
kld = require("kld-intersections")
Flatbush = require("flatbush")
// simplify = require("simplify-js")
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.
