d3.geom.quadtree

四叉树也被称为Q树（Q-Tree）。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等，对游戏编程，这会很有用。

四叉树（Q-Tree）是一种树形数据结构。四叉树的定义是：它的每个节点下至多可以有四个子节点，通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。

四叉树的每一个节点代表一个矩形区域（如上图黑色的根节点代表最外围黑色边框的矩形区域），每一个矩形区域又可划分为四个小矩形区域，这四个小矩形区域作为四个子节点所代表的矩形区域。

通过一个示例来展示。

1、数据

var width = 500,
    height = 500;

// 生成一份模拟数据，表示图上的10个点坐标
var dataset = d3.range(10).map(function() {
  return [Math.random() * width, Math.random() * height];
});

2、数据转换

var quadtree = d3.geom.quadtree()
    .extent([[0, 0], [width, height]])

var root = quadtree(dataset);
var data = [];
// 遍历四叉树中的每个节点，获得rect的坐标数据
root.visit(function(node, x1, y1, x2, y2) {
  node.x1 = x1;
  node.y1 = y1;
  node.x2 = x2;
  node.y2 = y2;
  data.push(node);
});

通过quadtree转换后的数据如图所示：

转换后的数据都在nodes中，为了生成矩形图，我们需要用root.visit方法再次将数据做一层转换，最终用来生成SVG的数据如下：

3、绘制图形

生成SVG容器

    var svg = d3.select('body').append('svg')
      .attr('width',width)
      .attr('height',height)

颜色比例尺

var color = d3.scale.category10();

生成矩形

var rect = svg.selectAll("rect")
    .data(data)
    .enter()
    .append("rect")
    .attr("fill", "none")
    .attr('stroke',function(d,i){
      return color(i)
    })
    .attr('stroke-width',1)
    .attr("x", function(d) { return d.x1; })
    .attr("y", function(d) { return d.y1; })
    .attr("width", function(d) { return d.x2 - d.x1; })
    .attr("height", function(d) { return d.y2 - d.y1; });

生成随机数据中的坐标点

var point = svg.selectAll("circle")
    .data(dataset)
    .enter()
    .append("circle")
    .attr("cx", function(d) { return d[0]; })
    .attr("cy", function(d) { return d[1]; })
    .attr("r", 3);

查看在线演示