tophtucker/README.md

## README.md

      
    Raw
  

              README.md
            
          
    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:


http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
http://stackoverflow.com/questions/8721406/how-to-determine-if-a-point-is-inside-a-2d-convex-polygon
https://github.com/mbostock/d3/wiki/Voronoi-Geom
https://en.wikipedia.org/wiki/Point_location
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/JukkaKaartinen/
https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=stochastic%20nearest%20neighbor
https://github.com/NathanEpstein/kNear
http://stackoverflow.com/questions/16774935/javascript-function-nearest-neighbor
https://en.wikipedia.org/wiki/Nearest_neighbor_search
http://stackoverflow.com/questions/1901139/closest-point-to-a-given-point
http://mathoverflow.net/questions/49516/n-dimensional-voronoi-diagram


## index.html
<!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>

## nearest-neighbor.js
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;
}

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!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;
	}