Interested in data visualisation, maps, JavasScript, and geology
Published
Edited
Jul 1, 2022
8 stars
// html`<img src="https://commons.wikimedia.org/wiki/File:Voronoi_centerlines_skeleton.gif">`
pointsOnPolygon = getPointsAlongPolyline(outerRing, numPerimeterPoints)
voronoi = {
const [xMin, xMax] = d3.extent(pointsOnPolygon.map(d => d[0]));
const [yMin, yMax] = d3.extent(pointsOnPolygon.map(d => d[1]));
// 1 px padding to prevent points on bounds from appearing inside polygon
const padding = 5
const bounds = [xMin - padding, yMin - padding, xMax + padding, yMax + padding];
return d3.Delaunay
.from(pointsOnPolygon)
.voronoi(bounds);
}
allCellPolygons = Array.from(voronoi.cellPolygons())
isInsidePolygon = (node) => d3.polygonContains(pointsOnPolygon, node) ? true : false
// adds 'inside' boolean property to each node
checkNodesInside = (cellPolygon) => cellPolygon.map((node) => {
node.inside = isInsidePolygon(node);
return node
})
function clipEdge(edge) {
const [fromNode, toNode] = edge;
// If only one of the two nodes is inside, we should clip
const outward = (fromNode.inside !== toNode.inside && !fromNode.inside);
const inward = (fromNode.inside !== toNode.inside && !toNode.inside);
const clip = (outward) ? "outward" : (inward) ? "inward" : null;
// find the intersection with feature polygon
if (clip) {
const { intersection } = findIntersectionWithFeature(fromNode, toNode);
// why sometimes no intersection tho?
if (intersection) intersection.clipped = true;
// clip one edge of polygon (ie replace outside nodes)
const newEdge = (clip === "outward") ? [intersection, toNode] : [fromNode, intersection];
// newEdge.distance = distance
return newEdge;
}
return edge;
}
function* edgeClipper(cellPolygonEdges) {
for (const edge of cellPolygonEdges) {
const [fromNode, toNode] = edge;
// If only one of the two nodes is inside, we should clip
const outward = (fromNode.inside !== toNode.inside && !fromNode.inside);
const inward = (fromNode.inside !== toNode.inside && !toNode.inside);
const clip = (outward) ? "outward" : (inward) ? "inward" : null;
// find the intersection with feature polygon
if (clip) {
const { intersection } = findIntersectionWithFeature(fromNode, toNode);
// why sometimes no intersection tho?
if (intersection) intersection.clipped = true;
// clip one edge of polygon (ie replace outside nodes)
const newEdge = (clip === "outward") ? [intersection, toNode] : [fromNode, intersection];
// newEdge.distance = distance
return newEdge;
}
}
}
clipCellPolygon = (cellPolygon) => {
// check which nodes of cellPolygon are inside feature polygon and appends boolean
const cellPolygonWithInside = checkNodesInside(cellPolygon);
// turn nodes into edges
const cellPolygonEdges = d3.pairs(cellPolygonWithInside);
const clippedCellPolygonEdges = cellPolygonEdges
.map(clipEdge)
.filter(([fromNode, toNode]) => { // discard outside edge
if (fromNode && toNode) { // edge is not always defined
const bothNodesOutside = fromNode.inside || toNode.inside;
return bothNodesOutside;
}
return false;
})
// tack index back on, including index 0
// cellPolygon.index ?? clippedCellPolygonEdges.index = cellPolygon.index // nullish coalescing operator not supported yet in Observable?
if (typeof cellPolygon.index !== "undefined") clippedCellPolygonEdges.index = cellPolygon.index
return clippedCellPolygonEdges;
}
// //Array of CellPolygons (which is an array of points), not edges.
// md`<code>allCellPolygons</code> consists of ${allCellPolygons.length} polygons, with polygons of ${d3.extent(allCellPolygons.map(polygon => polygon.length-1)).join(" to ")} edges, each containing x,y points. Therefore, shared edges of polygons are in here multiple times!
// `
function* cellPolygonClipper(polygons) {
for (const oneCellPolygon of polygons) {
const clippedCellPolygon = clipCellPolygon(oneCellPolygon).map(addNodeIds)
clippedCellPolygon.index = oneCellPolygon.index; // gets lost when mapped over
// yield await Promises.delay(1000, clippedCellPolygon);
yield clippedCellPolygon;
}
}
clippedCellPolygons = Array.from(cellPolygonClipper(allCellPolygons))
// dont care about cellPolygons only about unique edges
edgesWithIdsAll = clippedCellPolygons
.flat()
.map(edge => edge
.sort((a, b) => (a.id < b.id) ? 1 : -1 ) // sort nodes inside edges
)
.map(edge => {
edge.id = edge[0].id + "|" + edge[1].id;
return edge
})
uniqueEdges = {
// I love Map()!
const edgeMap = new Map();
edgesWithIdsAll.map(edge => edgeMap.set(edge.id, [edge[0], edge[1]] ) );
return Array.from(edgeMap.values());
}
uniqueNodes = {
// Man, I really love Map()!
const allNodes = uniqueEdges.flat()
const nodesMap = new Map();
allNodes.map(node => nodesMap.set(node.id, node ));
return Array.from(nodesMap.values())
}
clippedNodes = uniqueNodes.filter(e => e.clipped)
innerNodes = uniqueNodes.filter(e => e.inside)
graph = {
const graph = ngraph.ngraph()
uniqueNodes.forEach(node => { graph.addNode(node.id, { x: node[0], y: node[1] }); })
uniqueEdges.forEach(([fromNode, toNode]) => {
const dx = fromNode[0] - toNode[0];
const dy = fromNode[1] - toNode[1];
const distance = Math.sqrt(dx * dx + dy * dy);
graph.addLink(fromNode.id, toNode.id, { distance })
})
return graph;
}
pathfinderAGreedy = ngraph.path.aGreedy(graph, {
distance(fromNode, toNode) {
// In this case we have coordinates. Lets use them as
// distance between two nodes:
let dx = fromNode.data.x - toNode.data.x;
let dy = fromNode.data.y - toNode.data.y;
return Math.sqrt(dx * dx + dy * dy);
},
heuristic(fromNode, toNode) {
return Math.hypot(fromNode.data.x - toNode.data.x, fromNode.data.y - toNode.data.y);
}
});
pathfinderAStar = {
let distancePathFinder = ngraph.path.aStar(graph, {
distance(fromNode, toNode) {
// In this case we have coordinates. Lets use them as
// distance between two nodes:
let dx = fromNode.data.x - toNode.data.x;
let dy = fromNode.data.y - toNode.data.y;
return Math.sqrt(dx * dx + dy * dy);
},
heuristic(fromNode, toNode) {
// this is where we "guess" distance between two nodes.
return Math.hypot(fromNode.data.x - toNode.data.x, fromNode.data.y - toNode.data.y);
}
});
return distancePathFinder;
}
pointAreas = {
const length = clippedNodes.length
const areasArray = [];
for (let leftIndex = 0, index = 1, rightIndex = 2; rightIndex < length; leftIndex++, index++, rightIndex++) {
// the triangle around point b
const area = triangleArea(clippedNodes[leftIndex], clippedNodes[index], clippedNodes[rightIndex]);
areasArray.push({ area, leftIndex, index, rightIndex })
}
return areasArray;
}
noZeroArea = pointAreas.filter(d => d.area > areaThreshold)
prunedNodes = noZeroArea.map(({index}) => clippedNodes[index])
function triangleArea(a, b, c) {
const [ax, ay] = a;
const [bx, by] = b;
const [cx, cy] = c;
var area = Math.abs(((ay - cy) * (bx - cx) + (by - cy) * (cx - ax)) / 2);
return area;
}
mostGloballyDistantNode = sortedNodePairDistances[0]
mostDistantNodesPath = mostDistantNodesGraphPath.map(node => ([node.data.x, node.data.y]))
longestGraphPath = {
// heavy operation so only do it on toggle
if (strategy === "longest") {
let currentLongestPath = { path: null, length: 0 };
sortedNodePairDistances.map((nodeToNode) => {
const { fromIndex, toIndex, distance } = nodeToNode;
const firstNodeHash = clippedNodes[fromIndex].id;
const toNodeHash = clippedNodes[toIndex].id;
const currentPath = pathfinderAGreedy.find(firstNodeHash, toNodeHash)
const currentLength = sumGraphPathLength(currentPath);
if (currentLength > currentLongestPath.length) {
// console.log(currenLength)
currentLongestPath = { path: currentPath, length: currentLength };
}
})
return currentLongestPath
} else
return {path: []}
}
longestPath = longestGraphPath.path.map(node => ([node.data.x, node.data.y]));
simplifiedCenterline = (strategy === "longest") ? simplify(longestPath) : simplify(mostDistantNodesPath)
simplifiedCenterlineGeoJSON = turf.lineString(simplifiedCenterline.map(removeProjection))
findIntersectionWithFeature = findClosestPolygonIntersection(pointsOnPolygon)
// Rescale to fit at the current screen width
projection = d3
.geoIdentity()
.fitExtent([[5, 5], [width - 5, height - 5]], feature)
path = d3.geoPath().projection(projection)
s = projection.scale();
t = projection.translate();
applyProjection = ([x, y]) => [s * x + t[0], s * y + t[1]]
removeProjection = ([x, y]) => [(x - t[0])/s, (y - t[1])/s]
// From https://observablehq.com/@veltman/centerline-labeling
function getPointsAlongPolyline(polyline, count) {
// Calculate distance between each point of polyline
const distances = polyline.map((p, i) => {
return distanceBetween(p, polyline[i + 1] || polyline[0]);
});
const totalLength = d3.sum(distances);
const stepsize = totalLength / count;
let traversed = 0;
let next = stepsize / 2;
const done = polyline.reduce((arr, currentPoint, i) => {
const distanceBetweenCurrentPoints = distances[i];
while (next < traversed + distanceBetweenCurrentPoints) {
let nextPoint = polyline[i + 1] || polyline[0];
let percent = (next - traversed) / distanceBetweenCurrentPoints;
arr.push([
currentPoint[0] + (nextPoint[0] - currentPoint[0]) * percent,
currentPoint[1] + (nextPoint[1] - currentPoint[1]) * percent
]);
next += stepsize;
}
traversed += distanceBetweenCurrentPoints;
return arr;
}, []);
return done;
}
require('https://bundle.run/ngraph.path@1.4.0')
ngraph = ({
ngraph: await require('https://bundle.run/ngraph.graph@20.0.0'),
path: await require('https://bundle.run/ngraph.path@1.4.0'),
})
// TODO only import turf modules used in this notebook
turf = require("@turf/turf@5")
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.
