K-nearest neighbors search of a 2D set of points. Move the slider or scroll to change k.
The algorithm was adapted from this block
xxxxxxxxxx
<html>
<head>
<style>
body {
font-family: monospace;
}
.k {
position: absolute;
left: 10px;
top: 10px;
}
.k span {
position: relative;
bottom: 7px;
padding: 0 10px;
}
.hull {
fill: tomato;
fill-opacity: 0.25;
stroke: tomato;
pointer-events: none;
}
</style>
</head>
<body>
<div class="k">
<span>K = 25</span><input type="range" name="k" value="25" min="1">
</div>
<script src="https://d3js.org/d3.v3.min.js" charset="utf-8"></script>
<script src="k-nearest-neighbors.js"></script>
<script>
var width = 960,
height = 500,
k = 25;
var kDiv = d3.select(".k")
.on("change", function() {
k = +kDiv.select("input").node().value;
d3.select(this).select("span").text("K = " + k);
findNearest.k(k);
});
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
// add invisible rectangle that will pick up mouse movement
svg.append("rect")
.attr("width", width)
.attr("height", height)
.style("fill-opacity", 0)
.on("mousemove", mousemove)
.on("wheel", function() {
var wheelUp = event.deltaY < 0;
wheelUp ? k++ : k--;
k = clamp(k, 1, 100); // limit k to be between 1 and 100
kDiv.select("input").node().value = k;
kDiv.select("span").text("K = " + k);
findNearest.k(k);
mousemove.call(this);
});
var data = d3.range(500)
.map(function(d) {
return {
x: d3.random.normal(width/2, width/8)(),
y: Math.random() * height
};
});
var findNearest = d3.kNearestNeighbors()
.extent([[-1, -1], [width + 1, height + 1]])
.x(function(d) { return d.x; })
.y(function(d) { return d.y; })
.k(k)
.data(data);
var hull = svg.append("path").attr("class", "hull");
var circles = svg.append("g").attr("class", "circles")
.selectAll("circle").data(data)
.enter().append("circle")
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; })
.attr("r", 2)
.style("opacity", 0.5);
function mousemove() {
preventDefault(event);
var nearest = findNearest(d3.mouse(this));
// Draw convex hull around k-nearest points (if k > 1)
hull.datum(d3.geom.hull(nearest))
.attr("d", function(d) {
return d.length > 1 ? "M" + d.join("L") + "Z" : null;
});
// Get corresponding "nearest" data points from original data array
nearest = nearest
.map(function(d) { return data[d.i]; });
// Color nearest points red
circles
.style("fill", function(d) {
return nearest.indexOf(d) !== -1 ? "red" : null;
});
}
function clamp(d, min, max) {
return d < min ? min : d > max ? max : d;
}
function preventDefault(e) {
e = e || window.event;
if (e.preventDefault) e.preventDefault();
e.returnValue = false;
}
</script>
</body>
</html>
https://d3js.org/d3.v3.min.js