1

I am trying to find the nearest neighbors in a scatterplot using the data attached below, with the help of this snippet -

const voronoiDiagram = d3.voronoi()
                    .x(d => d.x)
                    .y(d => d.y)(data);
            data.forEach(function(d){   
                console.log(d, voronoiDiagram.find(d.x, d.y, 50));
            });

Now the dataset I am using is the standard iris sepal, petal lengths data in format -

{"sepalLength":7.7,"sepalWidth":3,"petalLength":"6.1","petalWidth":"2.3","species":"virginica","index":135,"x":374.99999999999994,"y":33.75,"vy":0,"vx":0},
{"sepalLength":6.3,"sepalWidth":3.4,"petalLength":"5.6","petalWidth":"2.4","species":"virginica","index":136,"x":524.9999999999999,"y":191.25,"vy":0,"vx":0},
{"sepalLength":6.4,"sepalWidth":3.1,"petalLength":"5.5","petalWidth":"1.8","species":"virginica","index":137,"x":412.5,"y":179.99999999999994,"vy":0,"vx":0},    
{"sepalLength":6,"sepalWidth":3,"petalLength":"4.8","petalWidth":"1.8","species":"virginica","index":138,"x":374.99999999999994,"y":225,"vy":0,"vx":0},
....

So, essentially it is in the form of {d: {x, y, sepal length, width, petal length, width}.

Now, I am trying to find the nearest neighbors with d3 voronoi from reference.

But, all I get is this in results -

Let point d in my dataset =

{"sepalLength":5.9,"sepalWidth":3,"petalLength":"5.1","petalWidth":"1.8","species":"virginica","index":149,"x":374.99999999999994,"y":236.24999999999997,"vy":0,"vx":0}

Now, the voronoiDiagram.find(d.x, d.y, 50) for this is resulting in -

"[375,236.25]"

That is, the same point with coordinates rounded off instead of another point.

So, how do I exclude current point being scanned in this case from the voronoi diagram. Also, If I exclude that point & re-calculate everything would this be good from the performance perspective ?

Can anyone help me with finding nearest neighbors from a set of points with d3 voronoi / quadtrees (I have tried a couple of examples already from Mike Bostock but couldn't get them to work in my case because of some errors, so will post them if d3 voronoi does not help).

2
  • The nearest neighbors could be interpreted as those immediately adjacent (those cells that share an edge with the target). So to clarify, are you looking cells within a certain radius or those cells that share an edge with a given cell? Mar 12, 2018 at 14:59
  • Looking for cells within a radius Mar 12, 2018 at 15:09

1 Answer 1

2

voronoiDiagram.find(y, x, r) will only ever return, at most, once cell. From the API documentation:

Returns the nearest site to point [x, y]. If radius is specified, only sites within radius distance are considered. (link)

I've previously read that as being plural, apparently I've never looked closely (and I think there is a large amount of utility in being able to find all points within a given radius).

What we can do instead is create a function fairly easily that will:

  1. start with voronoiDiagram.find() to find the cell the point falls in
  2. find the neighbors of the found cell
  3. for each neighbor, see if its point is within the specified radius
  4. if a neighbors point is within the specified radius:
    • add the neighbor to a list of cells with points within the specified radius,
    • use the neighbor to repeat steps 2 through 4
  5. stop when no more neighbors have been found within the specified radius, (keep a list of already checked cells to ensure none are checked twice).

The snippet below uses the above process (in the function findAll(x,y,r)) to show points within the specified distance as orange, the closest point will be red (I've set the function to differentiate between the two).

var width = 500;
var height = 300;

var data = d3.range(200).map(function(d) {
  var x = Math.random()*width;
  var y = Math.random()*height;
  var index = d;
  return {x:x,y:y,index:index}
});

var svg = d3.select("body")
  .append("svg")
  .attr("width",width)
  .attr("height",height);
  
var circles = svg.selectAll()
  .data(data, function(d,i) { return d.index; });
  
  
circles = circles.enter()
  .append("circle")
  .attr("cx",function(d) { return d.x; })
  .attr("cy",function(d) { return d.y; })
  .attr("r",3)
  .attr("fill","steelblue")
  .merge(circles);
  
var voronoi = d3.voronoi()
  .x(function(d) { return d.x; })
  .y(function(d) { return d.y; })
  .size([width,height])(data);
  

var results = findAll(width/2,height/2,30);

circles.data(results.nearest,function(d) { return d.index; })
  .attr("fill","orange");
circles.data([results.center],function(d) { return d.index; })
  .attr("fill","crimson");
  
var circle = svg.append("circle")
  .attr("cx",width/2)
  .attr("cy",height/2)
  .attr("r",30)
  .attr("fill","none")
  .attr("stroke","black")
  .attr("stroke-width",1);
  
  
circle.transition()
  .attrTween("r", function() {
    var node = this;
      return function(t) { 
        var r = d3.interpolate(30,148)(t);
        var results = findAll(width/2,height/2,r);
        circles.data(results.nearest,function(d) { return d.index; })
          .attr("fill","orange");
        return r;
      }
    })
    .duration(2000)
    .delay(1000);

	
function findAll(x,y,r) {
  var start = voronoi.find(x,y,r);
  
  if(!start) return {center:[],nearest:[]}  ; // no results.
  
  var queue = [start];
  var checked = [];
  var results = [];
	
  for(i = 0; i < queue.length; i++) {
    checked.push(queue[i].index);                           // don't check cells twice
    var edges = voronoi.cells[queue[i].index].halfedges;   
    // use edges to find neighbors
    var neighbors = edges.map(function(e) {
      if(voronoi.edges[e].left == queue[i]) return voronoi.edges[e].right; 
	  else return voronoi.edges[e].left;		
    })
    // for each neighbor, see if its point is within the radius:
    neighbors.forEach(function(n) { 
      if (n && checked.indexOf(n.index) == -1) {
      var dx = n[0] - x;
      var dy = n[1] - y;
      var d = Math.sqrt(dx*dx+dy*dy);
			
      if(d>r) checked.push(n.index)          // don't check cells twice
      else {
        queue.push(n);   // add to queue
        results.push(n); // add to results
      }
    }	
  })
}
  // center: the point/cell that is closest/overlapping, and within the specified radius, of point x,y
  // nearest: all other cells within the specified radius of point x,y
  return {center:start,nearest:results};
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.10.0/d3.min.js"></script>

4
  • Thanks for this update. I have read more & understood a lot more about voronois now with your answer. Mar 12, 2018 at 20:20
  • Hi @andrew-reid If you know something about d3 parallel coordinate charts, can you please help out with any of these questions too - stackoverflow.com/questions/49329600/… or stackoverflow.com/questions/49334965/… Mar 17, 2018 at 10:36
  • I haven't done much with parallel coordinates, but I can take a look - it may be a day or two before I have an opportunity, I will largely be a fair distance from mobile/cellular service (and the power grid) this weekend. Mar 17, 2018 at 15:41
  • Back in civilization again, but I'm not familiar with the plug-ins you're using - I'll need some time to take a closer look Mar 19, 2018 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.