Skip to content

Instantly share code, notes, and snippets.

@veltman
Last active October 26, 2018 17:20
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save veltman/b2358aaa4716d6fe103f1f8456241ec2 to your computer and use it in GitHub Desktop.
Save veltman/b2358aaa4716d6fe103f1f8456241ec2 to your computer and use it in GitHub Desktop.
Scribble map
height: 600

A randomized scribbled map building on this example. It adds the additional step of fuzzing the points a bit at the end so that you get a looser scribble that doesn't follow the original boundary precisely. Works pretty well for the more convex shapes but it tends to leave gaps at spots with sharp angles, like the Oklahoma panhandle or the Olympic Peninsula.

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<style>
path {
fill: none;
stroke-width: 1px;
}
</style>
</head>
<body>
<svg width="960" height="600"></svg>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.3/d3.min.js"></script>
<script src="https://d3js.org/topojson.v2.min.js"></script>
<script>
const svg = d3.select("svg"),
spline = d3.line().curve(d3.curveCardinal.tension(0));
colors = ["#00d565", "#d5008e", "#d5d500", "#0ab0cc", "#bf5a15"];
// Fuzz bigger features more
const fuzzer = d3.scaleLinear()
.domain([0, 30000])
.range([5, 25]);
d3.json("https://d3js.org/us-10m.v1.json", function(err, us){
const neighbors = topojson.neighbors(us.objects.states.geometries),
features = topojson.feature(us, us.objects.states).features;
// Greedy color selection
features.forEach(function(d,i){
d.properties.color = colors.filter(function(c){
return neighbors[i].every(n => features[n].properties.color !== c);
})[0];
// Mix up a bit
colors.push(colors.shift());
});
svg.selectAll("path")
.data(features)
.enter()
.append("path")
.attr("stroke", d => d.properties.color)
.attr("d", function(d){
let polygons = d.geometry.type === "MultiPolygon" ? d.geometry.coordinates : [d.geometry.coordinates];
let scribbleAngle = Math.PI * (1 / 16 + Math.random() * 3 / 8) * (Math.random() < 0.5 ? -1 : 1),
fuzzFactor = 10;
return polygons.map(function(polygon){
let lineFrequency = 2 + Math.random() * 2,
lineVariation = lineFrequency * 3 / 8,
fuzzFactor = fuzzer(Math.abs(d3.polygonArea(polygon[0])));
return scribble(polygon, scribbleAngle, lineFrequency, lineVariation)
.map(line => fuzzPoints(line, fuzzFactor))
.map(spline)
.join(" ");
}).join(" ");
});
});
function scribble(polygon, scribbleAngle, lineFrequency, lineVariation) {
// TODO check intersections against holes
let outer = polygon[0],
midpoint = getMidpoint(outer),
rotator = rotateAround(midpoint, scribbleAngle),
rotated = outer.map(rotator),
gridlines = getGridlines(rotated, lineFrequency, lineVariation),
intersections = getIntersections(gridlines, rotated);
if (intersections.length < 2) {
return [];
}
return getScribbles(intersections, rotated).map(function(scribble){
return scribble.map(rotateAround(midpoint, -scribbleAngle));
});
}
function getScribbles(rows, ring) {
let top = 0,
bottom = 1,
i = j = 0,
p1 = rows[top][i],
p2 = rows[bottom][j],
scribbles = [];
checkSegment();
return scribbles;
function checkSegment() {
if (isInFront() && isContained()) {
addSegment();
} else {
nextBottom();
}
}
function addSegment() {
let found = scribbles.find(scribble => distanceBetween(scribble[scribble.length - 1], p1) < 1);
if (found) {
found.push(p2);
} else {
scribbles.push([p1, p2]);
}
scribbles.sort((a, b) => scribbleLength(b) - scribbleLength(a));
nextTop();
}
function isInFront() {
return (top % 2 ? -1 : 1) * (p2[0] - p1[0]) > 0
}
function isContained() {
if (p1[2] === p2[2] || !d3.polygonContains(ring, pointBetween(p1, p2, 0.5))) {
return false;
}
return ring.every(function(a, segmentIndex){
const b = ring[segmentIndex + 1] || ring[0];
return segmentIndex === p1[2] || segmentIndex === p2[2] || !segmentsIntersect([a, b], [p1, p2]);
});
}
function nextRow() {
if (bottom + 1 < rows.length) {
p1 = rows[++top][i = 0];
p2 = rows[++bottom][j = 0];
checkSegment();
}
}
function nextTop() {
if (i + 1 >= rows[top].length) {
nextRow();
} else {
p1 = rows[top][++i];
checkSegment();
}
}
function nextBottom() {
if (j + 1 >= rows[bottom].length) {
nextTop();
} else {
p2 = rows[bottom][++j];
checkSegment();
}
}
function scribbleLength(points) {
return points.reduce(function(length, point, i){
return i ? length + distanceBetween(point, points[i - 1]) : 0;
}, 0);
}
}
function fuzzPoints(polyline, magnitude) {
return polyline.map(function(point, i){
if (i === 0 || i === polyline.length - 1) {
return point;
}
return moveAlongBisector(polyline[i - 1], point, polyline[i + 1], Math.random() * magnitude);
});
}
function getGridlines(points, lineFrequency, lineVariation) {
let bounds = getBounds(points),
i = bounds[0][1],
gridY = [],
space = lineFrequency - lineVariation / 2 + Math.random() * lineVariation;
while (i + space < bounds[1][1]) {
i += space;
gridY.push(i);
space = lineFrequency - lineVariation + Math.random() * lineVariation * 2;
}
return gridY.map(y => [[bounds[0][0] - 5, y], [bounds[1][0] + 5, y]]);
}
function getIntersections(gridlines, ring){
return gridlines.map(function(gridline, i){
const y = gridline[0][1],
row = [],
direction = i % 2 ? - 1 : 1;
ring.forEach(function(p1, j){
const p2 = ring[j + 1] || ring[0],
m = (p2[1] - p1[1]) / (p2[0] - p1[0]),
b = p2[1] - m * p2[0],
x = (y - b) / m;
if ((p1[1] <= y && p2[1] > y) || (p1[1] >= y && p2[1] < y)) {
row.push([x, y, j]);
}
});
row.sort((a, b) => direction * (a[0] - b[0]));
return row;
});
}
function rotateAround(center, angle) {
const cos = Math.cos(angle),
sin = Math.sin(angle);
return function(p) {
return [
center[0] + (p[0] - center[0]) * cos - (p[1] - center[1]) * sin,
center[1] + (p[0] - center[0]) * sin + (p[1] - center[1]) * cos
];
};
}
function getBounds(ring) {
let x0 = y0 = Infinity,
x1 = y1 = -Infinity;
ring.forEach(function(point){
if (point[0] < x0) x0 = point[0];
if (point[0] > x1) x1 = point[0];
if (point[1] < y0) y0 = point[1];
if (point[1] > y1) y1 = point[1];
});
return [
[x0, y0],
[x1, y1]
];
}
function getMidpoint(ring) {
const bounds = getBounds(ring);
return [
(bounds[1][0] + bounds[0][0]) / 2,
(bounds[1][1] + bounds[0][1]) / 2
];
}
function segmentsIntersect(a, b) {
if (orientation(a[0], a[1], b[0]) === orientation(a[0], a[1], b[1])) {
return false;
}
return orientation(b[0], b[1], a[0]) !== orientation(b[0], b[1], a[1]);
}
function orientation(p, q, r) {
const val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
return val > 0 ? 1 : val < 0 ? -1 : 0;
}
function pointBetween(a, b, pct) {
const point = [
a[0] + (b[0] - a[0]) * pct,
a[1] + (b[1] - a[1]) * pct
];
return point;
}
function distanceBetween(a, b) {
const dx = a[0] - b[0],
dy = a[1] - b[1];
return Math.sqrt(dx * dx + dy * dy);
}
function moveAlongBisector(start, vertex, end, amount) {
let at = getAngle(start, vertex),
bt = getAngle(vertex, end),
adjusted = bt - at,
angle;
if (adjusted <= -Math.PI) {
adjusted = 2 * Math.PI + adjusted;
} else if (adjusted > Math.PI) {
adjusted = adjusted - 2 * Math.PI;
}
angle = (adjusted - Math.PI) / 2 + at + (Math.random() < 0.5 ? Math.PI : 0);
return [
vertex[0] + amount * Math.cos(angle) / 2,
vertex[1] + amount * Math.sin(angle) / 2
];
}
function getAngle(a, b) {
return Math.atan2(b[1] - a[1], b[0] - a[0]);
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment