d3 v4 voronoi 在充满（点/圆圈）的散点图中找到最近的邻居

Question

我正在尝试使用下面附加的数据在散点图中找到最近的邻居，在此代码段的帮助下 -

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));
            });

现在我使用的数据集是标准的鸢尾萼片、花瓣长度数据格式 -

{"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},
....

所以，基本上它的形式是 {d: {x, y, sepal length, width, petal length, width}.

现在，我正在尝试从 reference 中找到具有 d3 voronoi 的最近邻居。

但是，我得到的结果就是这个 -

设我数据集中的d点=

{"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}

现在，voronoiDiagram.find(d.x, d.y, 50) 的结果是 -

"[375,236.25]"

即坐标四舍五入的同一个点，而不是另一个点。

那么，如何从 voronoi 图中排除在这种情况下正在扫描的当前点。另外，如果我排除那一点并重新计算一切，从性能的角度来看这会很好吗？

谁能帮我从一组点中找到最近的邻居使用 d3 voronoi / quadtrees（我已经尝试了 Mike Bostock 的几个示例，但由于一些错误无法让它们在我的案例中工作，如果 d3 voronoi 没有帮助，post 他们也会如此）。

Answer 1

voronoiDiagram.find(y, x, r) 只会 return，最多一次单元格。来自 API 文档：

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

我以前读过它是复数，显然我从来没有仔细看过（而且我认为能够找到给定半径内的所有点有很大的实用性）。

我们可以做的是相当容易地创建一个函数，它将：

从voronoiDiagram.find()开始寻找点所在的单元格
找到找到的单元格的邻居
对于每个邻居，查看其点是否在指定半径内
如果邻居点在指定半径内：
- 将邻居添加到点在指定半径内的像元列表中，
- 使用邻居重复步骤 2 到 4
在指定半径内找不到更多邻居时停止，（保留已检查单元格的列表以确保 none 检查两次）。

下面的代码片段使用上述过程（在函数findAll(x,y,r)中）将指定距离内的点显示为橙色，最近的点将显示为红色（我设置了区分两者的函数).

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>

d3 v4 voronoi 在充满（点/圆圈）的散点图中找到最近的邻居

d3 v4 voronoi find nearest neighbours in a scatterplot svg filled with (dots / circles)

voronoi

quadtree

scatter-plot

nearest-neighbor

d3.js