Many animations appear simple but actually require complex calculation on each frame. This week, I worked to simplify an animation algorithm using a data structure called the k-dimensional tree. To demonstrate k-d trees, I created an HTML canvas visualization of a nearest-neighbor search.

The animation involves a group of nodes floating around inside a container. Each time the user moves the mouse, the node closest to the pointer is highlighted. The highlighted node connects to its closest neighbor nodes, which repeat the process to connect to their neighbors. This process recurs up to a certain depth.

Problem

On each frame, the "dumb" way to create this effect would be by iterating through the nodes and choosing the one with the minimum distance to the user's cursor. Although this is a simple algorithm, it requires many calculations each time the user moves the cursor. The computation time of each frame increases exponentially with the number of nodes. At a certain point, this load is too heavy for the browser, and the animation starts to skip frames.

Solution: K-Dimensional Trees

This problem can be solved with data structures called k-dimensional trees. These are similar to binary search trees but support data of arbitary dimensions.

A k-d tree may seem difficult to imagine. To visualize how the tree stores data, let's take the simplest case: one dimension. It turns out that a one-dimensional k-d tree is just a binary search tree. Each binary search tree contains a root node with two leaves. In a balanced BST, the root represents the median of the data; it splits the data into two equal halves. Down the tree, each node splits its subset of the data in half again.

Now imagine this in two dimensions. Instead of representing a single number, each node represents two: a point on the Cartesian plane. This point also represents a line down the center of the data set. (The line is determined based on the k-d tree algorithm and varies by implementation.) To split a set of points in two dimensions, you just have to figure out which side of the line each point falls on.

Take this up one more dimension and each node represents a three numbers: a point in a three-dimensional coordinate system. This point is used to determine a plane in three-dimensions. Each node in its subtree represents another point in three dimensions. If the tree is balanced, exactly half of the nodes are on one side of the root node's plane and half are on the other.

Now we've taken a one-dimensional tree (a BST) and abstracted it to two and three dimensions. A point became a line and then a plane. It's easy now to take these concepts up to four dimensions. And five. All we need for a tree in k dimensions is a set of k-dimensional points and a function that can find the distance between them.

As we know from Binary Search Tree implementations, sorting data into a tree speeds up search dramatically. Each step of search can discard half of the data by slicing it down the middle. Therefore, in a tree of k dimensions, the average search time of the data set is reduced from O(n) time to O(log n) time.

Implementation

To create my animation, each node was tagged with an x and y position. All points were sorted into a two-dimensional tree and differentiated with distance formula. This means that, in a way, each node represented a line. Each node determined positive or negative distance from its "line" and used this information to sort its descendants into two subtrees.

When the user's mouse position changes within the container, the algorithm searches the tree for the nodes closest to the mouse. Then, for each of these nodes, it searches for the next-closest nodes. These steps recur until the maximum depth for each frame. I've chosen a shallow depth for demonstration purposes.

Computation time could be reduced by pre-computing each node's neighbors. However, in my implementation, I chose to add a bit of life by giving each node a slight velocity in a random direction. As such, the list of neighbors could change on each frame and must be recomputed.

Final Product

Below is the animation I created using a simple k-d tree implementation. This wouldn't even be usable with so many nodes if I had used the "brute force" implementation.