|
<!DOCTYPE html> |
|
<meta charset="utf-8"> |
|
<style> |
|
|
|
.point { |
|
fill: #000; |
|
} |
|
|
|
.candidate .point { |
|
fill: #aaa; |
|
transition: fill 250ms linear; |
|
} |
|
|
|
.candidate .search { |
|
fill: none; |
|
stroke: #aaa; |
|
transition: stroke 250ms linear, stroke-width 250ms linear; |
|
} |
|
|
|
.candidate--best .point { |
|
fill: #f00; |
|
} |
|
|
|
.candidate--best .search { |
|
stroke: #f00; |
|
stroke-width: 1.5px; |
|
} |
|
|
|
</style> |
|
<body> |
|
<script src="http://d3js.org/d3.v3.min.js"></script> |
|
<script> |
|
|
|
var width = 960, |
|
height = 500; |
|
|
|
var k = 10; // number of candidates to consider per circle |
|
|
|
var quadtree = d3.geom.quadtree() |
|
.extent([[0, 0], [width, height]]) |
|
([[Math.random() * width, Math.random() * height]]); |
|
|
|
var svg = d3.select("body").append("svg") |
|
.attr("width", width) |
|
.attr("height", height); |
|
|
|
var gCandidate = svg.append("g") |
|
.attr("class", "candidate"); |
|
|
|
var gPoint = svg.append("g") |
|
.attr("class", "point"); |
|
|
|
gPoint.append("circle") |
|
.attr("r", 3.5) |
|
.attr("cx", quadtree.point[0]) |
|
.attr("cy", quadtree.point[1]); |
|
|
|
(function nextPoint() { |
|
var i = 0, |
|
maxDistance = -Infinity, |
|
bestCandidate = null; |
|
|
|
(function nextCandidate() { |
|
if (++i > k) { |
|
gCandidate.selectAll("*").transition() |
|
.style("opacity", 0) |
|
.remove(); |
|
|
|
gPoint.append("circle") |
|
.attr("r", 3.5) |
|
.attr("cx", bestCandidate.__data__[0]) |
|
.attr("cy", bestCandidate.__data__[1]); |
|
|
|
quadtree.add(bestCandidate.__data__); |
|
|
|
return nextPoint(); |
|
} |
|
|
|
var x = Math.random() * width, |
|
y = Math.random() * height, |
|
closest = search(quadtree, x, y), |
|
dx = closest[0] - x, |
|
dy = closest[1] - y, |
|
distance = Math.sqrt(dx * dx + dy * dy); |
|
|
|
var g = gCandidate.insert("g", "*") |
|
.datum([x, y]) |
|
.attr("class", "candidate--current"); |
|
|
|
g.append("circle") |
|
.attr("class", "point") |
|
.attr("r", 3.5) |
|
.attr("cx", x) |
|
.attr("cy", y); |
|
|
|
g.append("circle") |
|
.attr("class", "search") |
|
.attr("r", 2.5) |
|
.attr("cx", x) |
|
.attr("cy", y); |
|
|
|
g.append("line") |
|
.attr("class", "search") |
|
.attr("x1", x) |
|
.attr("y1", y) |
|
.attr("x2", x) |
|
.attr("y2", y); |
|
|
|
var t = g.transition() |
|
.duration(2500) |
|
.each("end", function() { |
|
if (distance > maxDistance) { |
|
d3.select(bestCandidate).attr("class", null); |
|
d3.select(this.parentNode.appendChild(this)).attr("class", "candidate--best"); |
|
bestCandidate = this; |
|
maxDistance = distance; |
|
} else { |
|
d3.select(this).attr("class", null); |
|
} |
|
nextCandidate(); |
|
}); |
|
|
|
t.select("circle.search") |
|
.attr("r", distance); |
|
|
|
t.select("line.search") |
|
.attr("x2", closest[0]) |
|
.attr("y2", closest[1]); |
|
})(); |
|
|
|
})(); |
|
|
|
// Find the closest node to the specified point. |
|
function search(quadtree, x, y) { |
|
var x0 = -Infinity, y0 = -Infinity, |
|
x1 = Infinity, y1 = Infinity, |
|
bestDistance2 = Infinity, |
|
bestPoint; |
|
|
|
(function search(node) { |
|
var point; |
|
|
|
// stop searching if this cell can’t contain a closer node |
|
if (node.x0 > x1 || node.y0 > y1 || node.x1 < x0 || node.y1 < y0) return; |
|
|
|
// visit this point |
|
if (point = node.point) { |
|
var dx = x - point[0], |
|
dy = y - point[1], |
|
distance2 = dx * dx + dy * dy; |
|
if (distance2 < bestDistance2) { |
|
var distance = Math.sqrt(bestDistance2 = distance2); |
|
x0 = x - distance, y0 = y - distance; |
|
x1 = x + distance, y1 = y + distance; |
|
bestPoint = point; |
|
} |
|
} |
|
|
|
// visit closest cell first |
|
var children = node.nodes, |
|
right = 2 * x > node.x0 + node.x1, |
|
below = 2 * y > node.y0 + node.y1; |
|
if (node = children[below << 1 | right]) search(node); |
|
if (node = children[below << 1 | !right]) search(node); |
|
if (node = children[!below << 1 | right]) search(node); |
|
if (node = children[!below << 1 | !right]) search(node); |
|
})(quadtree); |
|
|
|
return bestPoint; |
|
} |
|
|
|
</script> |
