veltman/README.md

## README.md

      
    Raw
  

              README.md
            
          
    Use d3-quadtree to find the point in a group farthest away from its nearest neighbor without an extra knn implementation (biased towards the corners and edges since they can't have neighbors on all sides).

  
## index.html
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8" />
</head>
<body>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>

var width = 960,
    height = 500,
    radius = 2;

var canvas = d3.select("body").append("canvas")
  .attr("width", width)
  .attr("height", height);

var context = canvas.node().getContext("2d");

var dots = d3.range(1000).map(random);

var quadtree = d3.quadtree(dots)
  .extent([[-1, -1], [width + 1, height + 1]]);

d3.interval(update, 50);

function update(){

  // Change one dot
  var replace = Math.floor(Math.random() * dots.length);
  quadtree.remove(dots[replace]);
  quadtree.add(dots[replace] = random());

  // Find the loneliest dot
  var loneliest = dots.reduce(function(current, d){

    // Take it out of the quadtree so it doesn't find itself
    quadtree.remove(d);

    // Find the nearest neigbor
    var nearest = quadtree.find(d[0], d[1]),
        distance = Math.sqrt(Math.pow(nearest[0] - d[0], 2) + Math.pow(nearest[1] - d[1], 2));

    // Check whether it's farther from the nearest neighbor than the current leader
    if (distance > current.distance) {
      current.distance = distance;
      current.dot = d;
      current.nearest = nearest;
    }

    // Add it back
    quadtree.add(d);

    return current;

  }, { distance: -Infinity });

  context.clearRect(0, 0, width, height);

  // Draw the radius
  context.beginPath();
  context.fillStyle = "#fc0";
  context.arc(loneliest.dot[0], loneliest.dot[1], loneliest.distance - radius, 0, 2 * Math.PI);
  context.fill();

  context.fillStyle = "#d3008c";

  context.beginPath();

  // Draw the other dots
  dots.forEach(function(dot){

    context.moveTo(dot[0], dot[1]);
    context.arc(dot[0], dot[1], radius, 0, 2 * Math.PI);

  });

  context.fill();

}

function random() {
  return [
    Math.random() * width,
    Math.random() * height
  ];
}

</script>

## preview.png

      
    Raw
  

              preview.png
            
          
## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!DOCTYPE html>
	<html lang="en">
	<head>
	<meta charset="utf-8" />
	</head>
	<body>
	<script src="https://d3js.org/d3.v4.min.js"></script>
	<script>

	var width = 960,
	height = 500,
	radius = 2;

	var canvas = d3.select("body").append("canvas")
	.attr("width", width)
	.attr("height", height);

	var context = canvas.node().getContext("2d");

	var dots = d3.range(1000).map(random);

	var quadtree = d3.quadtree(dots)
	.extent([[-1, -1], [width + 1, height + 1]]);

	d3.interval(update, 50);

	function update(){

	// Change one dot
	var replace = Math.floor(Math.random() * dots.length);
	quadtree.remove(dots[replace]);
	quadtree.add(dots[replace] = random());

	// Find the loneliest dot
	var loneliest = dots.reduce(function(current, d){

	// Take it out of the quadtree so it doesn't find itself
	quadtree.remove(d);

	// Find the nearest neigbor
	var nearest = quadtree.find(d[0], d[1]),
	distance = Math.sqrt(Math.pow(nearest[0] - d[0], 2) + Math.pow(nearest[1] - d[1], 2));

	// Check whether it's farther from the nearest neighbor than the current leader
	if (distance > current.distance) {
	current.distance = distance;
	current.dot = d;
	current.nearest = nearest;
	}

	// Add it back
	quadtree.add(d);

	return current;

	}, { distance: -Infinity });

	context.clearRect(0, 0, width, height);

	// Draw the radius
	context.beginPath();
	context.fillStyle = "#fc0";
	context.arc(loneliest.dot[0], loneliest.dot[1], loneliest.distance - radius, 0, 2 * Math.PI);
	context.fill();

	context.fillStyle = "#d3008c";

	context.beginPath();

	// Draw the other dots
	dots.forEach(function(dot){

	context.moveTo(dot[0], dot[1]);
	context.arc(dot[0], dot[1], radius, 0, 2 * Math.PI);

	});

	context.fill();

	}

	function random() {
	return [
	Math.random() * width,
	Math.random() * height
	];
	}

	</script>