index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.segment {
fill: none;
stroke: #000;
stroke-width: 1.5px;
stroke-linecap: round;
}
.segment--hover {
stroke: red;
stroke-width: 5px;
}
.overlay {
fill: none;
pointer-events: all;
}
.extent {
fill: none;
stroke: #aaa;
shape-rendering: crispEdges;
}
</style>
<svg width="960" height="500"></svg>
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="//d3js.org/topojson.v1.min.js"></script>
<script src="tree.js"></script>
<script>
var topology = {
arcs: [
d3.range(40, 921, 30).map(function(x) {
return [x, (Math.sin(x / 200)) * 200 + 250];
})
]
};
var svg = d3.select("svg")
.on("mousemove", mousemoved);
svg.append("rect")
.attr("class", "overlay")
.attr("width", "100%")
.attr("height", "100%");
var path = d3.geo.path()
.projection(null);
var segment = svg.append("g").selectAll(".segment")
.data(d3.merge(topology.arcs.map(function(arc) { return d3.pairs(arc); })))
.enter().append("path")
.each(function(d) { d[0].node = this; })
.attr("class", "segment")
.attr("d", function(d) { return path({type: "LineString", coordinates: d}); });
var root = tree(topology);
function mousemoved() {
var leaf = root.nearest(d3.mouse(this));
d3.select(".segment--hover")
.classed("segment--hover", false);
d3.select(leaf.coordinates[0].node)
.classed("segment--hover", true)
.each(function() { this.parentNode.appendChild(this); });
}
(function visit(node) {
svg.insert("path", "*")
.attr("class", "extent")
.attr("d", path({type: "Polygon", coordinates: [[
[Math.round(node.extent[0][0]), Math.round(node.extent[0][1])],
[Math.round(node.extent[1][0]), Math.round(node.extent[0][1])],
[Math.round(node.extent[1][0]), Math.round(node.extent[1][1])],
[Math.round(node.extent[0][0]), Math.round(node.extent[1][1])],
[Math.round(node.extent[0][0]), Math.round(node.extent[0][1])]
]]})).node();
if (node.children) node.children.forEach(visit);
})(root);
</script>
tree.js
(function() {
tree = function(topology) {
return group(topology.arcs.map(function(arc) {
var i = 0,
n = arc.length,
p0,
p1 = arc[0],
children = new Array(n - 1);
while (++i < n) {
p0 = p1, p1 = arc[i];
children[i - 1] = new Leaf(p0, p1);
}
return group(children);
}));
};
function group(children) {
var i0,
i1,
n0,
n1,
child0,
child1,
children1;
while ((n0 = children.length) > 1) {
children1 = new Array(n1 = Math.ceil(n0 / 2));
for (i0 = 0, i1 = 0; i0 < n0 - 1; i0 += 2, i1 += 1) {
child0 = children[i0];
child1 = children[i0 + 1];
children1[i1] = new Node(child0, child1);
}
if (i0 < n0) {
children1[i1] = children[i0];
}
children = children1;
}
return children[0];
}
function Node(child0, child1) {
var e0 = child0.extent,
e1 = child1.extent;
this.children = [child0, child1];
this.extent = [
[Math.min(e0[0][0], e1[0][0]), Math.min(e0[0][1], e1[0][1])],
[Math.max(e0[1][0], e1[1][0]), Math.max(e0[1][1], e1[1][1])]
];
}
function node_nearest(point) {
var minNode,
minDistance = Infinity,
heap = minHeap(compareDistance),
node = this,
distance = node.distance(point),
candidate = {distance: distance, node: node};
do {
node = candidate.node;
if (node.children) {
heap.push({distance: node.children[0].distance(point), node: node.children[0]});
heap.push({distance: node.children[1].distance(point), node: node.children[1]});
} else {
distance = node.distance(point);
if (distance < minDistance) minDistance = distance, minNode = node;
}
} while ((candidate = heap.pop()) && (distance = candidate.distance) <= minDistance);
return minNode;
}
function node_distance(point) {
var x = point[0],
y = point[1],
x0 = this.extent[0][0],
y0 = this.extent[0][1],
x1 = this.extent[1][0],
y1 = this.extent[1][1];
return x < x0 ? pointLineSegmentDistance(point, [x0, y0], [x0, y1])
: x > x1 ? pointLineSegmentDistance(point, [x1, y0], [x1, y1])
: y < y0 ? y0 - y
: y > y1 ? y - y1
: 0;
}
Node.prototype = {
extent: null,
children: null,
distance: node_distance,
nearest: node_nearest
};
function Leaf(point0, point1) {
this.coordinates = [point0, point1];
this.extent = [
[Math.min(point0[0], point1[0]), Math.min(point0[1], point1[1])],
[Math.max(point0[0], point1[0]), Math.max(point0[1], point1[1])]
];
}
function leaf_distance(point) {
return pointLineSegmentDistance(point, this.coordinates[0], this.coordinates[1]);
}
function pointLineSegmentDistance(c, a, b) {
var dx = b[0] - a[0],
dy = b[1] - a[1],
d2 = dx * dx + dy * dy,
t = d2 && ((c[0] - a[0]) * dx + (c[1] - a[1]) * (b[1] - a[1])) / d2;
return pointDistance(c, t <= 0 ? a : t >= 1 ? b : [a[0] + t * dx, a[1] + t * dy]);
}
function pointDistance(a, b) {
var dx = a[0] - b[0],
dy = a[1] - b[1];
return dx * dx + dy * dy;
}
Leaf.prototype = {
extent: null,
coordinates: null,
distance: leaf_distance
};
function compareDistance(a, b) {
return a.distance - b.distance;
}
function minHeap(compare) {
var heap = {},
array = [],
size = 0;
heap.size = function() { return size; };
heap.push = function(object) {
up(array[object._ = size] = object, size++);
return size;
};
heap.pop = function() {
if (size <= 0) return;
var removed = array[0], object;
if (--size > 0) object = array[size], down(array[object._ = 0] = object, 0);
return removed;
};
heap.remove = function(removed) {
var i = removed._, object;
if (array[i] !== removed) return;
if (i !== --size) object = array[size], (compare(object, removed) < 0 ? up : down)(array[object._ = i] = object, i);
return i;
};
function up(object, i) {
while (i > 0) {
var j = ((i + 1) >> 1) - 1,
parent = array[j];
if (compare(object, parent) >= 0) break;
array[parent._ = i] = parent;
array[object._ = i = j] = object;
}
}
function down(object, i) {
while (true) {
var r = (i + 1) << 1,
l = r - 1,
j = i,
child = array[j];
if (l < size && compare(array[l], child) < 0) child = array[j = l];
if (r < size && compare(array[r], child) < 0) child = array[j = r];
if (j === i) break;
array[child._ = i] = child;
array[object._ = i = j] = object;
}
}
return heap;
}
})();