Skip to content

Instantly share code, notes, and snippets.

@mbostock

mbostock/.block

Last active January 21, 2018 22:06
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mbostock/5cfd3a46562461d7f2db to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
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
Copy Markdown

jonsadka commented Oct 30, 2014

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