Skip to content

Instantly share code, notes, and snippets.

@emeeks

emeeks/d3map.css

Last active May 19, 2016 17:16
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save emeeks/2250a030e4ca22cd7bb8 to your computer and use it in GitHub Desktop.
Save emeeks/2250a030e4ca22cd7bb8 to your computer and use it in GitHub Desktop.
Download ZIP
Voronoi Network Flooding
Raw
readme.md

Simple network flooding represented with voronoi. Click anywhere on the map to see the network distance to the rest of the network. Basically the same thing as coloring the nodes but with more visual artifacts because voronoi can be problematic.

This example implements a simple weighted breadth-first search to calculate distance and should work with any topojson file that has linestrings. This kind of thing is very useful for identifying areas of a network dataset that need more correcting or additional data.

Raw
d3map.css
path,circle,rect,polygon,ellipse,line {
vector-effect: non-scaling-stroke;
}
svg, canvas {
top: 0;
}
#d3MapZoomBox {
position: absolute;
z-index: 10;
height: 100px;
width: 25px;
top: 10px;
right: 50px;
}
#d3MapZoomBox > button {
height:25px;
width: 25px;
line-height: 25px;
}
.d3MapControlsBox > button {
font-size:22px;
font-weight:900;
border: none;
height:25px;
width:25px;
background: rgba(35,31,32,.85);
color: white;
padding: 0;
cursor: pointer;
}
.d3MapControlsBox > button:hover {
background: black;
}
#d3MapPanBox {
position: absolute;
z-index: 10;
height: 100px;
width: 25px;
top: 60px;
right: 50px;
}
#d3MapPanBox > button {
height:25px;
width: 25px;
line-height: 25px;
}
#d3MapPanBox > button#left {
position: absolute;
left: -25px;
top: 10px;
}
#d3MapPanBox > button#right {
position: absolute;
right: -25px;
top: 10px;
}
#d3MapLayerBox {
position: relative;
z-index: 10;
height: 100px;
width: 120px;
top: 10px;
left: 10px;
overflow: auto;
color: white;
background: rgba(35,31,32,.85);
}
#d3MapLayerBox > div {
margin: 5px;
border: none;
}
#d3MapLayerBox ul {
list-style: none;
padding: 0;
margin: 0;
cursor: pointer;
}
#d3MapLayerBox li {
list-style: none;
padding: 0;
}
#d3MapLayerBox li:hover {
font-weight:700;
}
#d3MapLayerBox li input {
cursor: pointer;
}
div.d3MapModal {
position: absolute;
z-index: 11;
background: rgba(35,31,32,.90);
top: 50px;
left: 50px;
color: white;
max-width: 400px;
}
div.d3MapModalContent {
width:100%;
height: 100%;
overflow: auto;
}
div.d3MapModalContent > p {
padding: 0px 20px;
margin: 5px 0;
}
div.d3MapModalContent > h1 {
padding: 0px 20px;
font-size: 20px;
}
div.d3MapModalArrow {
content: "";
width: 0;
height: 0;
border-left: 20px solid transparent;
border-right: 20px solid transparent;
border-top: 20px solid rgba(35,31,32,.90);
position: absolute;
bottom: -20px;
left: 33px;
}
#d3MapSVG {
}
rect.minimap-extent {
fill: rgba(200,255,255,0.35);
stroke: black;
stroke-width: 2px;
stroke-dasharray: 5 5;
}
circle.newpoints {
fill: black;
stroke: red;
stroke-width: 2px;
}
path.newfeatures {
fill: steelblue;
fill-opacity: .5;
stroke: pink;
stroke-width: 2px;
}
Raw
dijkstra.js
var Graph = (function (undefined) {
var extractKeys = function (obj) {
var keys = [], key;
for (key in obj) {
Object.prototype.hasOwnProperty.call(obj,key) && keys.push(key);
}
return keys;
}
var sorter = function (a, b) {
return parseFloat (a) - parseFloat (b);
}
var findPaths = function (map, start, end, infinity) {
infinity = infinity || Infinity;
var costs = {},
open = {'0': [start]},
predecessors = {},
keys;
var addToOpen = function (cost, vertex) {
var key = "" + cost;
if (!open[key]) open[key] = [];
open[key].push(vertex);
}
costs[start] = 0;
while (open) {
if(!(keys = extractKeys(open)).length) break;
keys.sort(sorter);
var key = keys[0],
bucket = open[key],
node = bucket.shift(),
currentCost = parseFloat(key),
adjacentNodes = map[node] || {};
if (!bucket.length) delete open[key];
for (var vertex in adjacentNodes) {
if (Object.prototype.hasOwnProperty.call(adjacentNodes, vertex)) {
var cost = adjacentNodes[vertex],
totalCost = cost + currentCost,
vertexCost = costs[vertex];
if ((vertexCost === undefined) || (vertexCost > totalCost)) {
costs[vertex] = totalCost;
addToOpen(totalCost, vertex);
predecessors[vertex] = node;
}
}
}
}
if (costs[end] === undefined) {
return null;
} else {
return predecessors;
}
}
var extractShortest = function (predecessors, end) {
var nodes = [],
u = end;
while (u) {
nodes.push(u);
predecessor = predecessors[u];
u = predecessors[u];
}
nodes.reverse();
return nodes;
}
var findShortestPath = function (map, nodes) {
var start = nodes.shift(),
end,
predecessors,
path = [],
shortest;
while (nodes.length) {
end = nodes.shift();
predecessors = findPaths(map, start, end);
if (predecessors) {
shortest = extractShortest(predecessors, end);
if (nodes.length) {
path.push.apply(path, shortest.slice(0, -1));
} else {
return path.concat(shortest);
}
} else {
return null;
}
start = end;
}
}
var toArray = function (list, offset) {
try {
return Array.prototype.slice.call(list, offset);
} catch (e) {
var a = [];
for (var i = offset || 0, l = list.length; i < l; ++i) {
a.push(list[i]);
}
return a;
}
}
var Graph = function (map) {
this.map = map;
}
Graph.prototype.findShortestPath = function (start, end) {
if (Object.prototype.toString.call(start) === '[object Array]') {
return findShortestPath(this.map, start);
} else if (arguments.length === 2) {
return findShortestPath(this.map, [start, end]);
} else {
return findShortestPath(this.map, toArray(arguments));
}
}
Graph.findShortestPath = function (map, start, end) {
if (Object.prototype.toString.call(start) === '[object Array]') {
return findShortestPath(map, start);
} else if (arguments.length === 3) {
return findShortestPath(map, [start, end]);
} else {
return findShortestPath(map, toArray(arguments, 1));
}
}
return Graph;
})();
Raw
index.html
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Voronoi Network Flooding</title>
<meta charset="utf-8" />
<link type="text/css" rel="stylesheet" href="d3map.css" />
<link type="text/css" rel="stylesheet" href="https://raw.githubusercontent.com/emeeks/d3-carto-map/master/examples/example.css" />
</head>
<style>
html,body {
height: 100%;
width: 100%;
margin: 0;
}
#map {
height: 100%;
width: 100%;
position: absolute;
}
.reproject {
position: absolute;
z-index: 99;
left: 50px;
top: 250px;
}
.node {
fill: blue;
stroke: black;
stroke-width: 1
}
.voronoi {
fill-opacity: .5;
stroke-opacity: .25;
}
.roads {
stroke: brown;
stroke-width: 1px;
fill: none;
}
</style>
<script>
function makeSomeMaps() {
pathSource = 0;
map = d3.carto.map();
d3.select("#map").call(map);
map.centerOn([-88,39],"latlong");
map.setScale(4);
map.refresh();
wcLayer = d3.carto.layer.tile();
wcLayer
.tileType("stamen")
.path("watercolor")
.label("Watercolor")
.visibility(true)
postLayer = d3.carto.layer.topojson();
postLayer
.path("uspost.topojson")
.label("Postal Routes")
.cssClass("roads")
.renderMode("svg")
.on("load", createMatrix);
map.addCartoLayer(wcLayer).addCartoLayer(postLayer);
function createMatrix() {
postdata = postLayer.features()
edgeList = [];
edgeMap = {};
nodes = [];
nodeHash = {};
for (x in postdata) {
var line = postdata[x].geometry.coordinates;
var lS = line[0];
var lE = line[line.length - 1];
var nA = [lS,lE];
for (y in nA) {
if (!nodeHash["node" + Math.ceil(nA[y][0] * 1000) + (nA[y][1] * 1000)]) {
var newNode = {label: "Node " + nodes.length, id: nodes.length.toString(), coordinates: [nA[y]], x: nA[y][0], y: nA[y][1]}
nodeHash["node" + Math.ceil(nA[y][0] * 1000) + (nA[y][1] * 1000)] = newNode;
nodes.push(newNode)
}
}
postdata[x].properties.source = nodeHash["node" + Math.ceil(lS[0] * 1000) + (lS[1] * 1000)];
postdata[x].properties.target = nodeHash["node" + Math.ceil(lE[0] * 1000) + (lE[1] * 1000)];
postdata[x].properties.cost = d3.geo.length(postdata[x]) * 6371;
}
var xExtent = d3.extent(nodes, function(d) {return d.x});
var yExtent = d3.extent(nodes, function(d) {return d.y});
voronoi = d3.geom.voronoi()
.clipExtent([xExtent,yExtent])
.clipExtent([[xExtent[0],yExtent[0]],[xExtent[1],yExtent[1]]])
.x(function (d) {return d.x})
.y(function (d) {return d.y});
vorFeatures = voronoi(nodes).map(function(d,i) {
d.push(d[0]);
return {type:"Feature", id: i, node: nodes[i], geometry: {type: "Polygon", coordinates: [d]}}
})
featureLayer = d3.carto.layer.featureArray();
featureLayer
.features(vorFeatures)
.label("Feature Array")
.cssClass("voronoi")
.renderMode("svg")
.clickableFeatures(true)
.on("load", function() {d3.selectAll("path.voronoi").on("click", function(d) {flood(d.node.id)})});
map.addCartoLayer(featureLayer)
for (x in postdata) {
if (edgeMap[postdata[x].properties.source.id]) {
edgeMap[postdata[x].properties.source.id][postdata[x].properties.target.id] = postdata[x].properties.cost;
}
else {
edgeMap[postdata[x].properties.source.id] = {};
edgeMap[postdata[x].properties.source.id][postdata[x].properties.target.id] = postdata[x].properties.cost;
}
if (edgeMap[postdata[x].properties.target.id]) {
edgeMap[postdata[x].properties.target.id][postdata[x].properties.source.id] = postdata[x].properties.cost;
}
else {
edgeMap[postdata[x].properties.target.id] = {};
edgeMap[postdata[x].properties.target.id][postdata[x].properties.source.id] = postdata[x].properties.cost;
}
}
graph = new Graph(edgeMap);
}
function flood(siteID) {
siteDistance = d3.keys(graph.map).map(function(d) {return Infinity});
siteDistance[siteID] = 0;
var map = graph.map;
var calculatedSites = [siteID];
var connectedSites = d3.keys(graph.map[siteID]);
var visitedSites = [siteID];
var sitesToVisit = [siteID];
var currentNode = siteID;
var currentCost = 0;
while (sitesToVisit.length > 0) {
sitesToVisit.splice(0,1);
for (x in connectedSites) {
if (calculatedSites.indexOf(connectedSites[x]) == -1) {
calculatedSites.push(connectedSites[x]);
siteDistance[connectedSites[x]] = currentCost + map[currentNode][connectedSites[x]];
}
else {
siteDistance[connectedSites[x]] = Math.min(currentCost + map[currentNode][connectedSites[x]], siteDistance[connectedSites[x]]);
}
if (visitedSites.indexOf(connectedSites[x]) == -1 && sitesToVisit.indexOf(connectedSites[x]) == -1) {
sitesToVisit.push(connectedSites[x]);
}
}
visitedSites.push(currentNode)
//sort sitesToVisit
sitesToVisit = sitesToVisit.sort(function(a,b) {
if (siteDistance[a] < siteDistance[b])
return -1;
if (siteDistance[a] > siteDistance[b])
return 1;
return 0;
})
currentNode = sitesToVisit[0];
currentCost = siteDistance[currentNode];
connectedSites = d3.keys(graph.map[currentNode]);
}
color = d3.scale.linear().domain([0,500,3500]).range(["green","yellow","red"])
d3.selectAll("path.voronoi").style("fill", "lightgray")
.transition()
.delay(function(d) {return siteDistance[d.id] == Infinity ? 5000 : siteDistance[d.id] * 2})
.duration(1000)
.style("fill", function(d) {return siteDistance[d.id] == Infinity ? "gray" : color(siteDistance[d.id])})
}
}
</script>
<body onload="makeSomeMaps()">
<div id="map"></div>
<footer>
<script src="http://d3js.org/d3.v3.min.js" charset="utf-8" type="text/javascript"></script>
<script src="http://d3js.org/topojson.v1.min.js" type="text/javascript">
</script>
<script src="http://d3js.org/d3.geo.projection.v0.min.js" type="text/javascript">
</script>
<script src="http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/tile.js" type="text/javascript">
</script>
<script src="http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.quadtiles.js" type="text/javascript">
</script>
<script src="http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.geo.raster.js" type="text/javascript">
</script>
<script src="https://rawgit.com/emeeks/d3-carto-map/master/d3.carto.map.js" type="text/javascript">
</script>
<script src="dijkstra.js" type="text/javascript">
</script>
</footer>
</body>
</html>
Display the source blob
Display the rendered blob
Raw
uspost.topojson
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment