Kd-Tree

Another test on space-partitioning, using a Kd-Tree for fast nearest-neighbor-search (NNS).

the building of the tree is done in a view lines of code:

a given set of points is sorted along one Axis (e.g. X). The sorted list is split at the median. The result are two sets, one for each half-space (left and right). Then, for the current node, the splitting-plane position (or the median-point) and depth is saved. Finally, if the point-set has more than 1 point, two child-nodes (L/R one for each point-set) are created which themselfs repeat the pocedure. The split-axis gets alternated at each depth.

At the moment the tree works for 2 dimensions, but can easily be modified to work for 3 … dimensions too.

KdTree Node:

 public static class Node{
      int depth;
      Point pnt;
      Node L, R;

      public Node(int depth){
        this.depth = depth;
      }
      boolean isLeaf(){
        return (L==null) | (R==null);
      }
    }

Kd-Tree building (snippet):

    private void build(final KdTree.Node node, final Point[] points){

      final int e = points.length; // end of list
      final int m = e>>1;          // median

      if( e > 1 ){
        int depth = node.depth;
        Arrays.sort(points, ((depth&1)==0)?SORT_X:SORT_Y); //alternating split axis
//        quick_sort.sort(points, depth&1); // faster than Arrays.sort() !

        build( (node.L = new Node(++depth)), copy(points, 0, m));
        build( (node.R = new Node(  depth)), copy(points, m, e));
      }
      node.pnt = points[m];
    }

 

 

The nearest-neighbor-search is simple too:

To find a given points closest neighbor, always the halfspace
the point falls in is choosen to step down the tree.
Once at a leaf, the node (and its distance to the point) is temporarily
stored as being the closest.
While unwinding the tree (stepping up) it has to be testet if the normal distance
of the input-point to the splitting-plane is smaller than the currently
stored min-distance. In other words, if a circle [center=input-point, radius=min-distance] overlaps with the splitting-plane. If so, there might be a point in the other (yet unchecked)
halfspace that contains a point closer than the current one. In that case, the other
halfspace has to ba traversed too. A lot of words for a tiny portion code.

Nearest Neighbor Search (snippet)

    private void getNN(NN nn, KdTree.Node node){
      if( node.isLeaf() ){
        // test if the nodes-point is closer.
        nn.update(node);
      } else {
        // get distance of given point "pnt_in" to split-plane
        float dist_hp = planeDistance(node, nn.pnt_in);
        // ... to check the half-space, the point is in, an step down.
        getNN(nn, (dist_hp < 0) ? node.L : node.R);

        // unwinding tree...
        // check the other half-space when the current distance (to the
        // nearest-neighbor found so far) is greater, than the distance
        // to the other (yet unchecked) half-space's plane.
        if( (dist_hp*dist_hp) < nn.min_sq ){
          getNN(nn, (dist_hp < 0) ? node.R : node.L);
        }
      }
    }

 

the full code/demo can be viewed here: http://www.openprocessing.org/sketch/92253

 

Pixelbased Voronoi

A exhaustive test would be, to place random points in the scene, and find for each pixel the closest neighbor. The result is a voronoi-diagram.  This would also work for a voxel-based voronoi diagram by just adding the 3rd dimension.

… always wanted to do something with voxels/volume-rendering/etc, i guess i should give it a try soon …

Java Applet: START


code/demo: http://www.openprocessing.org/sketch/92254