Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@tophtucker
Last active October 9, 2015 08:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tophtucker/7372a1286910a887cea6 to your computer and use it in GitHub Desktop.
Save tophtucker/7372a1286910a887cea6 to your computer and use it in GitHub Desktop.
Nearest neighbor

nearestNeighbor lets you find the closest neighbor to a given point in a two-dimensional space. Demo: click around up there.

It uses d3's voronoi geometry, but it convenient for more abstract uses where you might not want to draw anything onscreen at all. All it really adds is an algorithm from StackOverflow for finding which polygon generated by the voronoi geometry contains the point. And then it just brute-forces it. It's idiotic. At this point you might as well just brute-force distances to every neighboring point, right? But maybe I can improve it to be non-worthless. "If the polygons form a planar graph with each edge labelled with its two polygon neighbors, then one simple way is to run a semi-infinite ray up from the point until it hits its first edge. Then the relevant containing polygon is one of that edge's neighbors." OK rpi.edu, I don't know how to cast a ray until it hits its first edge.

Usage:

First, generate your neighbor-finding function.

var near = nearestNeighbor(friends)
  .x(function(d) { return d.age; })
  .y(function(d) { return d.salary; })

Then use it.

near({'age': 25, 'salary': 75000})

Now you have the person out of your friends who is closest to being 25 and having a salary of $75,000. I guess you could use the accessors to do weighting, right? But idk if...

Further reading:

<!DOCTYPE html>
<html>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title></title>
<style>
html, body {
margin: 0;
padding: 0;
width: 100%;
height: 100%;
overflow: hidden;
}
path {
stroke: black;
stroke-width: 1;
fill: yellow;
}
div {
position: absolute;
transform: translate(-50%, -50%);
}
</style>
<body>
</body>
<script src="//cdnjs.cloudflare.com/ajax/libs/d3/3.5.6/d3.min.js" charset="utf-8"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js" charset="utf-8"></script>
<script src="//cdn.rawgit.com/gka/d3-jetpack/master/d3-jetpack.js" charset="utf-8"></script>
<script src="nearest-neighbor.js" charset="utf-8"></script>
<script charset="utf-8">
var names = ["Michael","Christopher","Jason","David","James","Matthew","Joshua","John","Robert","Joseph","Daniel","Brian","Justin","William","Ryan","Eric","Nicholas","Jeremy","Andrew","Timothy","Jonathan","Adam","Kevin","Anthony","Thomas","Richard","Jeffrey","Steven","Charles","Brandon","Mark","Benjamin","Scott","Aaron","Paul","Nathan","Travis","Patrick","Chad","Stephen","Kenneth","Gregory","Jacob","Dustin","Jesse","Jose","Shawn","Sean","Bryan","Derek","Bradley","Edward","Donald","Samuel","Peter","Keith","Kyle","Ronald","Juan","George","Jared","Douglas","Gary","Erik","Phillip","Joel","Raymond","Corey","Shane","Larry","Marcus","Zachary","Craig","Derrick","Todd","Jeremiah","Antonio","Carlos","Shaun","Dennis","Frank","Philip","Cory","Brent","Nathaniel","Gabriel","Randy","Luis","Curtis","Jeffery","Russell","Alexander","Casey","Jerry","Wesley","Brett","Luke","Lucas","Seth","Billy","Jennifer","Amanda","Jessica","Melissa","Sarah","Heather","Nicole","Amy","Elizabeth","Michelle","Kimberly","Angela","Stephanie","Tiffany","Christina","Lisa","Rebecca","Crystal","Kelly","Erin","Laura","Amber","Rachel","Jamie","Mary","April","Sara","Andrea","Shannon","Megan","Emily","Julie","Danielle","Erica","Katherine","Maria","Kristin","Lauren","Kristen","Ashley","Christine","Brandy","Tara","Katie","Monica","Carrie","Alicia","Courtney","Misty","Kathryn","Patricia","Holly","Stacy","Karen","Anna","Tracy","Brooke","Samantha","Allison","Melanie","Leslie","Brandi","Cynthia","Susan","Natalie","Jill","Dawn","Dana","Vanessa","Veronica","Lindsay","Tina","Kristina","Stacey","Wendy","Lori","Catherine","Kristy","Heidi","Sandra","Jacqueline","Kathleen","Christy","Leah","Valerie","Pamela","Erika","Tanya","Natasha","Katrina","Lindsey","Melinda","Monique","Denise","Teresa","Tammy","Tonya","Julia","Candice","Gina","Toph","Evan","Dorothy","Cindy"];
var friends = d3.range(100).map(function(d) {
return {
"age": Math.random() * innerWidth,
"salary": Math.random() * innerHeight,
"name": _.sample(names)
};
});
var near = nearestNeighbor(friends)
.x(ƒ('age'))
.y(ƒ('salary'));
d3.select("body").on("click", function(d) {
var mouse = {"age": d3.mouse(this)[0], "salary": d3.mouse(this)[1]};
d3.select(this).append("div")
.datum(near(mouse))
.style('left', function(d) { return d.age + "px"; })
.style('top', function(d) { return d.salary + "px"; })
.text(ƒ('name'));
});
</script>
</html>
function nearestNeighbor(neighbors) {
var xValue = function(d) { return d[0]; },
yValue = function(d) { return d[1]; },
voronoi = d3.geom.voronoi().x(xValue).y(yValue),
polygons = voronoi(neighbors);
function nearest(point) {
return polygons.filter(function(polygon) {
return polygonContainsPoint(polygon, normalize(point));
})[0].point;
}
function normalize(point) {
return [xValue(point), yValue(point)]
}
function polygonContainsPoint(points, test) {
var result = false;
for (i = 0, j = points.length - 1; i < points.length; j = i++) {
if ((points[i][1] > test[1]) != (points[j][1] > test[1]) &&
(test[0] < (points[j][0] - points[i][0]) * (test[1] - points[i][1]) / (points[j][1]-points[i][1]) + points[i][0])) {
result = !result;
}
}
return result;
}
nearest.x = function(_) {
if (!arguments.length) return xValue;
xValue = _;
voronoi = voronoi.x(xValue);
polygons = voronoi(neighbors);
return nearest;
};
nearest.y = function(_) {
if (!arguments.length) return yValue;
yValue = _;
voronoi = voronoi.y(yValue);
polygons = voronoi(neighbors);
return nearest;
};
nearest.clipExtent = function(_) {
if(!arguments.length) return voronoi.clipExtent();
voronoi = voronoi.clipExtent(_);
polygons = voronoi(neighbors);
return nearest;
}
return nearest;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment