Kd-tree in Javascript

I needed to get my head around how kd-trees work, so I coded up a simple implementation that just builds a tree. Naturally, add, delete, balancing etc methods would be required.

See wikipedia: kd-tree

    /*
     * Builds a kd-tree given an array of points
     */
    var kdtree = function(points, depth) {
        var axis, median, node = {};

        if (!points || points.length == 0) return;

        // alternate between the axis
        axis = depth % points[0].length;

        // sort point array
        points.sort((a, b) => a[axis] - b[axis]);

        median = Math.floor(points.length / 2);

        // build and return node
        node.location = points[median];
        node.left = kdtree(
            points.slice(0, median), depth + 1);
        node.right = kdtree(
            points.slice(median + 1), depth + 1);
        return node;
    }

Example usage would be:

var points = [ [2,3], [5,4], [4,7], [8,1], [7,2], [9,6] ];
kdtree(points, 0);

Published by

oughton

Senior software engineer with extensive experience in enterprise software development targeting wholesale financial organisations and cloud solution providers.

4 thoughts on “Kd-tree in Javascript”

  1. Just wondering about a couple things about this.

    First where does the buildTree() function come from. I can’t seem to run this without this function throwing a error.

    Secondly, what does depth refer to? As in what should be supplying for that function argument?

    Finally, if I had a array of objects with a set of coordinates in it how would I process them so that the rest of the function works as is? points.pos[‘x’] for example

    1. First where does the buildTree() function come from. I can’t seem to run this without this function throwing a error.
      This was a copy and paste / re-factor error. It should be ‘kdtree’ not ‘buildTree’. I have updated this in the post now. Thanks for that.

      Secondly, what does depth refer to? As in what should be supplying for that function argument?
      Depth is the tree depth, so pass it 0 to begin with. Alternatively you could check if there is a second parameter passed into the function and if not then set depth to be 0.
      Finally, if I had a array of objects with a set of coordinates in it how would I process them so that the rest of the function works as is? points.pos[‘x’] for example
      You could just pre process these point objects before passing them to the function. eg:


      var points = [ { pos: { x: 1, y: 2 } }, { pos: { x: 5, y: 1 } }, { pos: { x: 3, y: 2 } } ];
      var flat = [];
      for (var i in points) {
      var point = points[i].pos;
      flat.push([ point.x, point.y ]);
      }

      kdtree(flat, 0);

  2. Thank you for your post.
    .sort() takes a function that returns number, not boolean.
    I just wondering why don’t subtract two items if the first item is smaller; positive if it’s larger, or zero if they’re equal.

    points.sort((a, b) => a[axis]- b[axis]);

Comments are closed.