d3-quadtree module overview
d3-quadtree implements two-dimensional recursive spatial subdivision. It provides quadtree creation with accessors, extent management, adding/removing data, copying, finding closest datum, and selective node visiting.
d3-quadtree
24 notes, read out of this brain and free to use. Each one was extracted from a source and is re-checked against its exam.
d3-quadtree accessor configuration
Quadtree accessor configuration methods: quadtree.x (set x accessor), quadtree.y (set y accessor).
d3-quadtree extent and coverage methods
Quadtree extent and coverage methods: quadtree.extent (extend to cover extent), quadtree.cover (extend to cover point).
d3-quadtree data manipulation methods
Quadtree data manipulation methods: quadtree.add (add datum), quadtree.addAll (add array of data), quadtree.remove (remove datum), quadtree.removeAll (remove array of data), quadtree.copy (copy quadtree).
d3-quadtree query methods
Quadtree query methods: quadtree.root (get root node), quadtree.data (retrieve all data), quadtree.size (count data), quadtree.find (find closest datum), quadtree.visit (selectively visit nodes), quadtree.visitAfter (visit all nodes).
quadtree constructor signature
d3.quadtree(*data*, *x*, *y*) creates a new quadtree. If *data* is specified, adds the iterable of data to the quadtree. If *x* and *y* are also specified, sets the x and y accessors before adding data. Equivalent to d3.quadtree().x(x).y(y).addAll(data).
quadtree.y() accessor
Sets or gets the y-coordinate accessor function. Used to derive the y coordinate when adding, removing, or finding points in the tree. The accessor must be consistent, returning the same value for the same input. Defaults to function(d) { return d[1]; }. Returns the quadtree when setting.
quadtree.extent() method
Sets or gets the quadtree's extent [[*x0*, *y0*], [*x1*, *y1*]], where *x0* and *y0* are inclusive lower bounds and *x1* and *y1* are inclusive upper bounds. When setting, expands the quadtree to cover the specified points. Returns undefined if the quadtree has no extent. The extent may be expanded by calling quadtree.cover() or quadtree.add().
quadtree.cover() method
quadtree.cover(*x*, *y*) expands the quadtree to cover the specified point ⟨*x*,*y*⟩ and returns the quadtree. If the extent already covers the point, does nothing. If the quadtree has an extent, it is repeatedly doubled to cover the point, wrapping the root node as necessary. If the quadtree is empty, the extent is initialized to [[⌊*x*⌋, ⌊*y*⌋], [⌈*x*⌉, ⌈*y*⌉]].
quadtree.add() method
quadtree.add(*datum*) adds the specified datum to the quadtree, deriving its coordinates ⟨*x*,*y*⟩ using the current x and y accessors, and returns the quadtree. If the new point is outside the current extent, the quadtree is automatically expanded to cover it.
quadtree.addAll() method
quadtree.addAll(*data*) adds the specified iterable of data to the quadtree, deriving each element's coordinates using the current x and y accessors, and returns the quadtree. Results in a more compact quadtree than calling add() repeatedly because the extent of the data is computed first.
quadtree.remove() method
quadtree.remove(*datum*) removes the specified datum from the quadtree, deriving its coordinates ⟨*x*,*y*⟩ using the current x and y accessors, and returns the quadtree. If the datum does not exist (determined by strict equality), does nothing.
quadtree.removeAll() method
quadtree.removeAll(*data*) removes the specified data from the quadtree, deriving their coordinates ⟨*x*,*y*⟩ using the current x and y accessors, and returns the quadtree. Ignores any datum that does not exist in the quadtree.
quadtree.copy() method
quadtree.copy() returns a copy of the quadtree. All nodes in the returned quadtree are identical copies of the corresponding node; however, any data in the quadtree is shared by reference and not copied.
quadtree.root() method
quadtree.root() returns the root node of the quadtree.
quadtree.data() method
quadtree.data() returns an array of all data in the quadtree.
quadtree.size() method
quadtree.size() returns the total number of data in the quadtree.
quadtree.find() method
quadtree.find(*x*, *y*, *radius*) returns the datum closest to the position ⟨*x*,*y*⟩ within the given search radius. If *radius* is not specified, it defaults to infinity. If there is no datum within the search area, returns undefined.
quadtree.visit() method
quadtree.visit(*callback*) visits each node in the quadtree in pre-order traversal, invoking the callback with arguments (*node*, *x0*, *y0*, *x1*, *y1*), where ⟨*x0*, *y0*⟩ are the lower bounds and ⟨*x1*, *y1*⟩ are the upper bounds. If the callback returns true, child nodes are not visited; otherwise all children are visited in sibling order: top-left, top-right, bottom-left, bottom-right. Returns the quadtree.
quadtree.visitAfter() method
quadtree.visitAfter(*callback*) visits each node in the quadtree in post-order traversal, invoking the callback with arguments (*node*, *x0*, *y0*, *x1*, *y1*), where ⟨*x0*, *y0*⟩ are the lower bounds and ⟨*x1*, *y1*⟩ are the upper bounds. Returns the quadtree.
Quadtree internal nodes structure
Internal nodes are represented as sparse four-element arrays in left-to-right, top-to-bottom order: [0] top-left quadrant, [1] top-right quadrant, [2] bottom-left quadrant, [3] bottom-right quadrant. Child quadrants may be undefined if empty. The length property is 4 for internal nodes.
Quadtree leaf nodes structure
Leaf nodes are represented as objects with properties: data (the associated data passed to quadtree.add()), and next (the next datum in the leaf if any). The length property is undefined for leaf nodes. To iterate over all data in a leaf: if (!node.length) do console.log(node.data); while (node = node.next);
Quadtree coordinate mutation warning
The point's x and y coordinates must not be modified while the point is in the quadtree. To update a point's position, remove the point and then re-add it at the new position, or discard the existing quadtree and create a new one.
Quadtree.visit() search example
Example of using visit() to return all nodes within a rectangular extent [xmin, ymin, xmax, ymax]: function search(quadtree, xmin, ymin, xmax, ymax) { const results = []; quadtree.visit((node, x1, y1, x2, y2) => { if (!node.length) { do { let d = node.data; if (d[0] >= xmin && d[0] < xmax && d[1] >= ymin && d[1] < ymax) { results.push(d); } } while (node = node.next); } return x1 >= xmax || y1 >= ymax || x2 < xmin || y2 < ymin; }); return results; }