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")
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.