Skip to content

Instantly share code, notes, and snippets.

@mbostock

mbostock/.block

Last active January 21, 2018 22:06
Show Gist options
  • Save mbostock/5cfd3a46562461d7f2db to your computer and use it in GitHub Desktop.
Save mbostock/5cfd3a46562461d7f2db to your computer and use it in GitHub Desktop.
Download ZIP
Line Segment Intersection
Raw
.block
license: gpl-3.0
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.segment {
fill: none;
stroke: #000;
stroke-width: 1.5px;
stroke-linecap: round;
}
.segment--test {
stroke: blue;
}
.segment--intersect {
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 width = 960,
height = 500,
intersections = [];
var topology = {
arcs: [
d3.range(40, width - 40 + 1, 30).map(function(x) {
return [x, (Math.sin(x / 200)) * 200 + height / 2];
})
]
};
var path = d3.geo.path()
.projection(null);
var svg = d3.select("svg")
.on("mousemove", mousemoved);
var test = svg.append("path")
.datum([[width / 2, height / 2], [width / 2, height / 2]])
.attr("class", "segment segment--test")
.attr("d", function(d) { return path({type: "LineString", coordinates: d}); });
svg.append("rect")
.attr("class", "overlay")
.attr("width", "100%")
.attr("height", "100%");
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; }) // TODO better two-way binding
.attr("class", "segment")
.attr("d", function(d) { return path({type: "LineString", coordinates: d}); });
var root = tree(topology);
function mousemoved() {
var d = test.datum();
d[1] = d3.mouse(this);
test.attr("d", path({type: "LineString", coordinates: d}));
intersections.forEach(function(i) {
d3.select(i.coordinates[0].node)
.classed("segment--intersect", false);
});
intersections = root.intersections(d[0], d[1]); // TODO better API
intersections.forEach(function(i) {
d3.select(i.coordinates[0].node)
.classed("segment--intersect", true);
});
}
(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>
Raw
tree.js
(function() {
// TODO support quantized, delta-encoded arcs
// TODO group arcs based on connectedness!
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])]
];
}
// accumulates intersections with line segment AB
// TODO it might be better to check whether the segment intersects this box,
// rather than simply checking whether the segment’s box overlaps this box
function node_intersections(a, b) {
var intersections = [],
x2 = a[0],
y2 = a[1],
x3 = b[0],
y3 = b[1],
t;
if (x3 < x2) t = x2, x2 = x3, x3 = t;
if (y3 < y2) t = y2, y2 = y3, y3 = t;
(function intersectNode(node) {
if (node.extent[0][0] <= x3 && x2 <= node.extent[1][0]
&& node.extent[0][1] <= y3 && y2 <= node.extent[1][1]) {
node.children.forEach(function(child) {
if (child.children) {
intersectNode(child);
} else if (intersectLeaf(child, a, b)) {
intersections.push(child);
}
});
}
})(this);
return intersections;
}
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,
intersections: node_intersections
};
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])]
];
}
// TODO cleanup and simplify this code
function intersectLeaf(leaf, q, q2) {
var p = leaf.coordinates[0],
p2 = leaf.coordinates[1],
r = subtractPoints(p2, p),
s = subtractPoints(q2, q),
qp = subtractPoints(q, p),
uNumerator = crossProduct(qp, r),
denominator = crossProduct(r, s);
if (!denominator) {
return !uNumerator &&
((q[0] < p[0]) ^ (q[0] < p2[0]) ^ (q2[0] < p[0]) ^ (q2[0] < p2[0]) ||
(q[1] < p[1]) ^ (q[1] < p2[1]) ^ (q2[1] < p[1]) ^ (q2[1] < p2[1]));
}
var u = uNumerator / denominator,
t = crossProduct(qp, s) / denominator;
return t >= 0 && t <= 1 && u >= 0 && u <= 1;
}
function leaf_intersections(q, q2) {
return intersectLeaf(this, q, q2) ? [this] : [];
}
function subtractPoints(a, b) {
return [b[0] - a[0], b[1] - a[1]];
}
function crossProduct(a, b) {
return a[0] * b[1] - a[1] * b[0];
}
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,
intersections: leaf_intersections
};
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; // invalid request
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;
}
})();
@jonsadka
Copy link

Ah awesome, this is really great Mike. Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment