|
<html> |
|
<head> |
|
<style> |
|
.square { |
|
fill: none; |
|
stroke: #ddd; |
|
} |
|
|
|
.point { |
|
fill: #bbb; |
|
stroke: white; |
|
} |
|
|
|
.point.scanned { |
|
fill: orange; |
|
stroke: grey; |
|
} |
|
|
|
.point.selected { |
|
fill: red; |
|
stroke: grey; |
|
} |
|
|
|
.halo { |
|
fill: none; |
|
stroke: slategrey; |
|
stroke-width: 2px; |
|
stroke-dasharray: 4, 4; |
|
} |
|
</style> |
|
</head> |
|
<body> |
|
<script src="https://d3js.org/d3.v4.0.0-alpha.29.min.js" charset="utf-8"></script> |
|
<script src="https://d3js.org/d3-quadtree.v0.6.min.js"></script> |
|
<script> |
|
// overwrite d3.quadtree with later version, v0.6 |
|
d3.quadtree = d3_quadtree.quadtree; |
|
|
|
var width = 960, |
|
height = 500, |
|
r = 50; |
|
|
|
var svg = d3.select("body").append("svg") |
|
.attr("width", width) |
|
.attr("height", height); |
|
|
|
var data = d3.range(2000) |
|
.map(function(d) { return [width * Math.random(), height * Math.random()]; }); |
|
|
|
var quadtree = d3.quadtree() |
|
.extent([[-1, -1], [width + 1, height + 1]]); |
|
|
|
data.forEach(function(d, i) { |
|
var point = quadtree.add(d[0], d[1]); |
|
point.i = i; |
|
}); |
|
|
|
svg.append("g").attr("class", "squares") |
|
.selectAll(".square").data(squares(quadtree)) |
|
.enter().append("rect") |
|
.attr("class", "square") |
|
.attr("x", function(d) { return d.x0; }) |
|
.attr("y", function(d) { return d.y0; }) |
|
.attr("width", function(d) { return d.x1 - d.x0; }) |
|
.attr("height", function(d) { return d.y1 - d.y0; }); |
|
|
|
var points = svg.append("g").attr("class", "points") |
|
.selectAll(".point").data(quadtree.points()) |
|
.enter().append("circle") |
|
.attr("class", "point") |
|
.attr("cx", function(d) { return d.x; }) |
|
.attr("cy", function(d) { return d.y; }) |
|
.attr("r", 4); |
|
|
|
var x = width/3, |
|
y = height/2; |
|
|
|
var halo = svg.append("circle").attr("class", "halo") |
|
.attr("cx", width/3) |
|
.attr("cy", height/2) |
|
.attr("r", r); |
|
|
|
fixedRadiusSearch(quadtree, r, [x, y]); |
|
|
|
points |
|
.classed("scanned", function(d) { return d.scanned; }) |
|
.classed("selected", function(d) { return d.selected; }); |
|
|
|
svg.append("rect").attr("class", "event-canvas") |
|
.attr("width", width) |
|
.attr("height", height) |
|
.attr("fill-opacity", 0) |
|
.on("mousemove", function() { |
|
var mouse = d3.mouse(this); |
|
|
|
halo |
|
.attr("cx", mouse[0]) |
|
.attr("cy", mouse[1]); |
|
|
|
points.each(function(d) { d.scanned = d.selected = false; }); |
|
|
|
fixedRadiusSearch(quadtree, r, mouse); |
|
|
|
points |
|
.classed("scanned", function(d) { return d.scanned; }) |
|
.classed("selected", function(d) { return d.selected; }); |
|
}); |
|
|
|
// Get coordinates of all squares in the tree |
|
function squares(quadtree) { |
|
var squares = []; |
|
quadtree.visit(function(node, x0, y0, x1, y1) { |
|
if (node.length) squares.push({ x0:x0, y0:y0, x1:x1, y1:y1 }); |
|
}); |
|
return squares; |
|
} |
|
|
|
// Find all points in `quadtree` that are within radius `r` of `point` |
|
function fixedRadiusSearch(quadtree, r, point) { |
|
var cx = point[0], cy = point[1]; |
|
quadtree.visit(function(node, x0, y0, x1, y1) { |
|
if (!node.length) { |
|
node.scanned = true; |
|
node.selected = pointInCircle([node.x, node.y], [cx, cy, r]); |
|
} |
|
return rectangleOutsideCircle([[x0, y0],[x1, y1]], [cx, cy, r]); |
|
}); |
|
} |
|
|
|
function rectangleOutsideCircle(rect, circle) { |
|
var x0 = rect[0][0], y0 = rect[0][1], |
|
x1 = rect[1][0], y1 = rect[1][1]; |
|
|
|
// Rectangle is inside circle if... |
|
|
|
// ...circle center is inside rectangle |
|
var isInside = pointInRectangle(circle, [[x0, y0], [x1, y1]]) ? true : |
|
// ...any of the rectangle's corners is inside the circle |
|
pointInCircle([x0, y0], circle) ? true : |
|
pointInCircle([x0, y1], circle) ? true : |
|
pointInCircle([x1, y1], circle) ? true : |
|
pointInCircle([x1, y0], circle) ? true : |
|
// ...any of the rectangle's sides intersects the circle |
|
lineIntersectsCircle([[x0, y0], [x1, y0]], circle) ? true : |
|
lineIntersectsCircle([[x1, y0], [x1, y1]], circle) ? true : |
|
lineIntersectsCircle([[x1, y1], [x0, y1]], circle) ? true : |
|
lineIntersectsCircle([[x0, y1], [x0, y0]], circle) ? true : |
|
false; // ...otherwise it's outside |
|
|
|
return !isInside; |
|
} |
|
|
|
function lineIntersectsCircle(line, circle) { |
|
// Taken mostly from http://stackoverflow.com/a/1088058 |
|
|
|
var x0 = line[0][0], y0 = line[0][1], |
|
x1 = line[1][0], y1 = line[1][1], |
|
cx = circle[0], cy = circle[1], r = circle[2]; |
|
|
|
var lineDistance = distance([x0, y0], [x1, y1]); |
|
|
|
// [dx, dy] = direction vector of line |
|
var dx = (x1-x0)/lineDistance, |
|
dy = (y1-y0)/lineDistance; |
|
|
|
// Parametric equation for a line: |
|
// x = dx*t + x0 |
|
// y = dy*t + y0 |
|
// where 0 <= t <= 1 |
|
|
|
// Compute parameter t for closest point to circle center |
|
// (clamp t to be between line segment end points) |
|
var t = clamp(dx*(cx-x0) + dy*(cy-y0), 0, lineDistance); |
|
|
|
// Compute coordinates of point on line closest to circle center |
|
var px = t*dx + x0, |
|
py = t*dy + y0; |
|
|
|
// Get distance of this point from center |
|
var projectionDistance = distance([cx, cy], [px, py]); |
|
|
|
return projectionDistance <= r; |
|
} |
|
|
|
function pointInRectangle(point, rect) { |
|
var x = point[0], y = point[1], |
|
x0 = rect[0][0], y0 = rect[0][1], |
|
x1 = rect[1][0], y1 = rect[1][1]; |
|
return (x0 <= x) && (x <= x1) && (y0 <= y) && (y <= y1); |
|
} |
|
|
|
function pointInCircle(point, circle) { |
|
var x = point[0], y = point[1], |
|
cx = circle[0], cy = circle[1], r = circle[2]; |
|
return distance([cx, cy], [x, y]) <= r; |
|
} |
|
|
|
// Euclidean distance between two points |
|
function distance(p0, p1) { |
|
var x0 = p0[0], y0 = p0[1], |
|
x1 = p1[0], y1 = p1[1]; |
|
return Math.sqrt(Math.pow(x1-x0, 2) + Math.pow(y1-y0, 2)); |
|
} |
|
|
|
function clamp(d, min, max) { |
|
return d < min ? min : d > max ? max : d; |
|
} |
|
</script> |
|
</body> |
|
</html> |
