找到相对于给定坐标集最近的散点图点（圆）的最佳方法是什么？

Question

假设我在 2 x 8 网格中有 16 个圆圈：

svg = d3.select(body).append('svg').attr('height,h).attr('width',w);

svg.selectAll('.centroids')
      .data(d3.range(0,16))
      .enter()
      .append('circle')
      .attr('class','centroids')
      .attr('r','5')
      .attr('cx', function(d,i) { return i * 10; })
      .attr('cy', function(d,i) {
        if (i > 7) return 20;
        return 10;
      });

给定 space 中的随机坐标，我如何确定最近的 .centroid 点？

N次的一种方法当然是遍历所有的点，测量斜边到x和y坐标的差值，取最小值。

不过我想找到更好的方法。有谁知道优化的方法吗？

Answer 1

优化将取决于您的具体设置：

如果你有几个节点（在你的例子中是 16 个），在随机位置，那么你的方法可能是最优的（只计算斜边的平方，它获得一些平方根运算).
如果您有许多随机位置的节点，您将要开始考虑 quadtrees 来管理您的节点。开销是不可忽略的，所以在你有成百上千个节点之前不要理会它。从好的方面来说，d3已经为您编写了所有代码。
对于网格：
```
var startx=0;
var offsetx=10;
var cols=8;
var starty=10;
var offsety=10;
var rows=2; 
var xi=d3.median([0,cols-1, Math.round((x-startx)/stepx)])
var yi=d3.median([0,rows-1, Math.round((y-starty)/stepy)])
var i=xi + yi*cols
```
这是常数时间，根据你的尺寸调整（许多）常数。

一些细节：(x-startx)/stepx 允许缩放坐标，使第一个点为 0，下一个点为 1，等等。Math.round 给出最接近的整数，d3.median 将结果推到 0 和 cols-1 之间（检查每种情况，总的来说它比嵌套的 ifs 更好）......总的来说这给出了最近列的索引，然后你做同样的事情对于行，你就在那里！

找到相对于给定坐标集最近的散点图点（圆）的最佳方法是什么？

What is the best way to find the nearest scatter plot point (circle) relative to a given coordinate set?

geometry

nearest-neighbor

d3.js