Quadtree Geom - VividD/d3 GitHub Wiki

Wiki ▸ Geometry ▸ Quadtree Geom

A quadtree is a two-dimensional recursive spatial subdivision. This implementation uses square partitions, dividing each square into four equally-sized squares. Each point exists in a unique node; if multiple points are in the same position, some points may be stored on internal nodes rather than leaf nodes. Quadtrees can be used to accelerate various spatial operations, such as the Barnes-Hut approximation for computing n-body forces, or collision detection.

# d3.geom.quadtree()

Creates a new quadtree factory with the default x-accessor, y-accessor and extent. The returned function can be used to create any number of quadtrees from data with the factory’s configuration.

# quadtree(points)

Constructs a new quadtree for the specified array of data points, returning the root node of a new quadtree. The x- and y-coordinates of each point are determined using the current x- and y- accessor functions. To build a quadtree by adding points incrementally, the specified points array can be empty, and then points can be later added to the returned root node; in this case, you must also specify the extent of the quadtree.

Each node in the quadtree has several properties:

• nodes - a sparse array of the four child nodes in order: top-left, top-right, bottom-left, bottom-right
• leaf - a boolean indicating whether this is an internal node or a leaf node
• point - the point associated with this node, if any (may apply to either internal or leaf nodes)
• x - the x-coordinate of the associated point, if any
• y - the y-coordinate of the associated point, if any

The returned root node also defines add and visit methods.

# root.add(point)

Adds the specified new point to the quadtree.

# root.visit(callback)

Visits each node in the quadtree, invoking the specified callback with arguments {node, x1, y1, x2, y2} for each node. Nodes are traversed in pre-order. If the callback returns true for a the given node, then the children of that node are not visited; otherwise, all child nodes are visited.

# root.find(point)

Given any point [x,y], returns the closest point in the quadtree.

# quadtree.x([x])

If x is specified, sets the x-coordinate accessor and returns this quadtree factory. If x is not specified, returns the current x-coordinate accessor, which defaults to:

function(d) { return d[0]; }

For each point added to the quadtree, either during initial construction or lazily added, the x-accessor is invoked with the arguments {d, i}, where d is the current point and i is its index in the array of all points. The x-accessor must then return a numeric value indicating the x-coordinate of the given point. The x-accessor may also be defined as a constant number rather than a function, if desired.

# quadtree.y([y])

If y is specified, sets the y-coordinate accessor and returns this quadtree factory. If y is not specified, returns the current y-coordinate accessor, which defaults to:

function(d) { return d[1]; }

For each point added to the quadtree, either during initial construction or lazily added, the y-accessor is invoked with the arguments {d, i}, where d is the current point and i is its index in the array of all points. The y-accessor must then return a numeric value indicating the y-coordinate of the given point. The y-accessor may also be defined as a constant number rather than a function, if desired.

# quadtree.extent([extent])

If extent is specified, sets the current extent and returns this quadtree factory. If extent is not specified, returns the current extent, which defaults to null. When the extent is null, an extent will be computed automatically by scanning the array of input points passed to the quadtree constructor. Otherwise, the extent must be specified as a two-dimensional array [​[x0, y0], [​x1, y1]​], where x0 and y0 are the lower bounds of the extent, and x1 and y1 are the upper bounds of the extent. Setting an extent is required when constructing a quadtree lazily from an initially-empty set of nodes.