Shortest path / Fil | Observable

Fil

Vocateur.

Workspace

Published

Edited

Nov 4, 2021

Fork of Manhattan Voronoi

13 stars

Algorithms

Chandrupatla’s root-finding method Sidi’s root-finding method Regular numbers DruidJS worker Natural breaks Distance to a segment Ray out of a convex hull Word Tour: 40k words and their friends Hello, @thi.ng/grid-iterators Head/tail breaks Pseudo-blue noise shader How fast does walk-on-spheres converge?AoC 12: shortest path under constraints KDE estimation Plot: Correlation heatmap Poisson Finish 2 Poisson disk sampling functions WoS with transport Simple and surprising sort Local median Time series topological subsampling Union-Find Level set experiment 1 Mean value coordinates Poisson potential Middle-square World of squares (spherical)World of squares Largest Inscribed Square Hello, PyWavelets Geothmetic meandian Hello, Reorder.js Geometric Median Image FFT Transport to a map Disc Transport TP3: Power Diagram and Semi-Discrete Optimal Transport The blue wave Hello, genetic-js Sliced Optimal Transport DruidJS Self-Organizing Maps meet Delaunay Hello, polygon-clipping seedrandom, minimal Walk on Spheres 2 Walk on Spheres Hello, Autoencoder Kaprekar’s number VoronoiMap2D Hello, ccwt.js Polygon Triangulation Quantile.invert?Linear congruential generator Hue blur Needle in a haystack Moving average blur Apollo 11 implementation of trigonometric functions, by Margaret H. Hamilton (march 1969)2D curves intersection The 2D approximate Newton-Raphson method Inverting Lee’s Tetrahedral projection Linde–Buzo–Gray stippling Mean shift clustering with kd-tree 2D point distributions

Shortest path

Kahan Summation Hello, delatin Dijkstra’s algorithm in gpu.js Lloyd’s relaxation on a graph Manhattan Diameter Manhattan Voronoi Mobility landscapes — an introduction Dijkstra’s shortest-path tree H3 oddities Protein Matrix Convex Spectral Weights Sort stuff by similarity Kriging Delaunay.findTriangle n-dimensions binning?Travelling with a self-organizing map UMAP-o-Matic MNIST & UMAP-js Hello UMAP-js Mean shift clustering Levenshtein transition Rd quasi-random sequences Automated label placement (countries)Phyllotaxis explained Motionrugs Planar hull (Andrew’s monotone chain algorithm)South Africa’s medial axis Travelling salesperson approximation with t-SNE Distance to shore Worker ngraph: pagerank, louvain…t-SNE Voronoi Cloud Contours Circular function drawing Kruskal Maze Mycelium Travelling salesperson approximation on the globe, with t-SNE tsne.js tsne.js & worker

Also listed in…

Graphs

paths = {

const paths = [];

const P = shortest_junctions(graph, tree);

for (const code of P.costs.keys()) {

const cost = P.costs.get(code),

junction = P.junctions.get(code),

path = junction.slice();

path.reverse();

while (tree.predecessor[path[0]] > -1)

path.unshift(tree.predecessor[path[0]]);

path.reverse();

while (tree.predecessor[path[0]] > -1)

path.unshift(tree.predecessor[path[0]]);

paths.push({ cost, junction, path });

}

return paths;

}

src = "https://gist.githubusercontent.com/Fil/450db51a15fdc8bd34a12cb8a9961976/raw/680961da57d2b11a0e3e6993e5f79bd035729831"

nodes = d3.csv(`${src}/node_list.csv`, d3.autoType)

edges = d3.csv(`${src}/edge_list.csv`, d3.autoType)

nodesIndex = new Map(nodes.map((d, i) => [d.osmid, i]))

function createGraph(nodesIndex, edges) {

const graph = { sources: [], targets: [], costs: [] };

edges.forEach(({ u, v, length }) => {

const i = nodesIndex.get(u),

j = nodesIndex.get(v),

cost = length;

graph.sources.push(i);

graph.targets.push(j);

graph.costs.push(cost);

graph.sources.push(j);

graph.targets.push(i);

graph.costs.push(cost);

});

return graph;

}

graph = createGraph(nodesIndex, edges)

import { shortest_tree, shortest_junctions } from "@fil/dijkstra"

tree = shortest_tree({ graph, origins })

pts = nodes.map(d => projection([d.x, d.y]))

projection = d3.geoMercator().fitExtent([[10, 10], [width - 10, height - 10]], {

type: "MultiPoint",

coordinates: nodes.map(d => [d.x, d.y])

})

color = (replay, d3.scaleOrdinal(d3.schemeCategory10))

d3 = require("d3@5")

height = width * 0.9

import { slider } from "@jashkenas/inputs"

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.

Learn more