voronoi.findAll(x,y,r)

[Andrew-Reid]

The d3.voronoi module has the handy voronoi.find(x,y,r) (#17 ) method, which returns the closest site to a given point, which is very useful for a number of applications. But what if we wanted all the sites within a given radius?

I've been working on a few things where a built in method would be handy, but also saw a question question on StackOverflow yesterday on the same topic that got me thinking, if we have a method to find the closest site, why not a method to find all sites within a given radius?

I've mocked up a potential method here, it takes the same parameters as voronoi.find, but spits out an array of sites rather than a single one.

  findAll: function(x, y, r) {
    var diagram = this, center = diagram.find(x,y,r); // use the existing method to find central point
      if(!center) return [];
      var queue = [center], checked = [];      // queue holds cells within the boundary

      for(var i = 0; i < queue.length; i++) {
          checked.push(queue[i].index);           // don't check any cell twice
          
          // find neighbors of current item:
          var edges = diagram.cells[queue[i].index].halfedges;   
          var neighbors = edges.map(function(e) {
            return (diagram.edges[e].left == queue[i]) ?  diagram.edges[e].right : diagram.edges[e].left;
          })
         
          // for each neighbor, see if it is within the radius (and unchecked), if so, add to queue
          neighbors.forEach(function(n) {
             if(n && checked.indexOf(n.index) == -1) {
               var dx = n[0] - x, dy = n[1] - y;
               var d2 = dx*dx+dy*dy;
               (d2>r*r) ? checked.push(n.index) : queue.push(n);
             }
          })
      }
    return queue;  
  }

And here's a demonstration.

Granted, this implementation leads to some cells potentially being examined more than once (first through the use of voronoi.find() to get the initial cell); consequently, it could be re-worked to include a slightly modified voronoi.find() method to get started.

But, this might be getting ahead of myself. Is there value in including such a method in d3.voronoi?

[Fil]

The demo is quite nice and I can totally see how it will be useful for some of my projects — but IMO there is no dire need to add it to the d3-voronoi module, as it is quite easy to add externally.

[Fil]

Updated this method to d3-delaunay: https://bl.ocks.org/Fil/3faaaf1b5f34b03a7a2235bf22e20b73