d3-hexadectree

Four-dimensional recursive spatial subdivision module.

A hexadectree (or 16-tree) recursively partitions four-dimensional space into hyper-rectangles, dividing each box into sixteen equally-sized partitions. Each distinct point exists in a unique leaf node; coincident points are represented by a linked list. Hexadectrees can accelerate various spatial operations in 4D, such as collision detection, spatial hashing, and searching for nearby points.

Installing

If you use npm, npm install d3-hexadectree. You can also load directly as a bundled standalone library. In vanilla, a d3 global is exported:

<script src="https://unpkg.com/d3-hexadectree"></script>
<script>

const tree = d3.hexadectree();

</script>

API Reference

# d3.hexadectree([data[, x, y, z, w]])

Creates a new, empty hexadectree with an empty extent and the default x-, y-, z-, and w- accessors. If data is specified, adds the specified array of data to the hexadectree. This is equivalent to:

const tree = d3.hexadectree()
    .addAll(data);

If x, y, z, and w are also specified, sets the x-, y-, z-, and w- accessors to the specified functions before adding the specified array of data to the hexadectree, equivalent to:

const tree = d3.hexadectree()
    .x(x)
    .y(y)
    .z(z)
    .w(w)
    .addAll(data);

# hexadectree.x([x])

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

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

The x-accessor is used to derive the x-coordinate of data when adding to and removing from the tree.

# hexadectree.y([y])

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

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

# hexadectree.z([z])

If z is specified, sets the current z-coordinate accessor and returns the hexadectree. If z is not specified, returns the current z-accessor, which defaults to:

function z(d) {
  return d[2];
}

# hexadectree.w([w])

If w is specified, sets the current w-coordinate accessor and returns the hexadectree. If w is not specified, returns the current w-accessor, which defaults to:

function w(d) {
  return d[3];
}

# hexadectree.extent([extent])

If extent is specified, expands the hexadectree to cover the specified points [[x0, y0, z0, w0], [x1, y1, z1, w1]] and returns the hexadectree. If extent is not specified, returns the current extent [[x0, y0, z0, w0], [x1, y1, z1, w1]].

# hexadectree.cover(x, y, z, w)

Expands the hexadectree to cover the specified point ⟨x,y,z,w⟩, and returns the hexadectree.

# hexadectree.add(datum)

Adds the specified datum to the hexadectree and returns the hexadectree.

# hexadectree.addAll(data)

Adds the specified array of data to the hexadectree and returns this hexadectree.

# hexadectree.remove(datum)

Removes the specified datum from the hexadectree and returns the hexadectree.

# hexadectree.removeAll(data)

Removes the specified data from the hexadectree and returns the hexadectree.

# hexadectree.copy()

Returns a copy of the hexadectree.

# hexadectree.root()

Returns the root node of the hexadectree.

# hexadectree.data()

Returns an array of all data in the hexadectree.

# hexadectree.size()

Returns the total number of data in the hexadectree.

# hexadectree.find(x, y, z, w[, radius])

Returns the datum closest to the position ⟨x,y,z,w⟩ within the search radius.

# hexadectree.findAllWithinRadius(x, y, z, w, radius)

Returns all the data points within the given search radius of the position ⟨x,y,z,w⟩.

# hexadectree.visit(callback)

Visits each node in the hexadectree in pre-order traversal, invoking the specified callback with arguments node, x0, y0, z0, w0, x1, y1, z1, w1.

# hexadectree.visitAfter(callback)

Visits each node in the hexadectree in post-order traversal, invoking the specified callback with arguments node, x0, y0, z0, w0, x1, y1, z1, w1.

Nodes

Internal nodes of the hexadectree are represented as 16-element arrays in binary partition order fourth << 3 | deep << 2 | bottom << 1 | right:

• 0 - w0, z0, y0, x0
• 1 - w0, z0, y0, x1
• 2 - w0, z0, y1, x0
• 3 - w0, z0, y1, x1
• 4 - w0, z1, y0, x0
• 5 - w0, z1, y0, x1
• 6 - w0, z1, y1, x0
• 7 - w0, z1, y1, x1
• 8 - w1, z0, y0, x0
• 9 - w1, z0, y0, x1
• 10 - w1, z0, y1, x0
• 11 - w1, z0, y1, x1
• 12 - w1, z1, y0, x0
• 13 - w1, z1, y0, x1
• 14 - w1, z1, y1, x0
• 15 - w1, z1, y1, x1

Leaf nodes are represented as objects with the following properties:

• data - the data associated with this point.
• next - the next datum in this leaf, if any.