KD TREES (3-D) Nearest Neighbor Search

Question

I look at the Wikipedia page trees KD Nearest neighbors search .

The pseudocode specified on Wikipedia works when the points are in 2-D (x, y).

I want to know what changes I should make when the points are 3-D (x, y, z).

I googled a lot and even looked at the link to similar questions in the stack overflow, but I did not find a 3-dimensional implementation anywhere, all the previous questions accept 2-D points as input, and not 3-D points that I am looking for.

Wiki pseudocode for building a KD tree:

function kdtree (list of points pointList, int depth) { // Select axis based on depth so that axis cycles through all valid values var int axis := depth mod k; // Sort point list and choose median as pivot element select median by axis from pointList; // Create node and construct subtrees var tree_node node; node.location := median; node.leftChild := kdtree(points in pointList before median, depth+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; } 

How to find the nearest neighbor now after the construction of KD Trees?

Thanks!

Answer 1

I recently coded KDTree to find the closest neighbor in three-dimensional space and ran into the same problems that NNS understands, especially 3.2 from the wiki. I ended up using this algorithm, which seems to work in all my tests:

Here is the initial sheet search:

 public Collection<T> nearestNeighbourSearch(int K, T value) { if (value==null) return null; //Map used for results TreeSet<KdNode> results = new TreeSet<KdNode>(new EuclideanComparator(value)); //Find the closest leaf node KdNode prev = null; KdNode node = root; while (node!=null) { if (KdNode.compareTo(node.depth, node.k, node.id, value)<0) { //Greater prev = node; node = node.greater; } else { //Lesser prev = node; node = node.lesser; } } KdNode leaf = prev; if (leaf!=null) { //Used to not re-examine nodes Set<KdNode> examined = new HashSet<KdNode>(); //Go up the tree, looking for better solutions node = leaf; while (node!=null) { //Search node searchNode(value,node,K,results,examined); node = node.parent; } } //Load up the collection of the results Collection<T> collection = new ArrayList<T>(K); for (KdNode kdNode : results) { collection.add((T)kdNode.id); } return collection; } 

Here is a recursive search starting at the nearest node sheet:

 private static final <T extends KdTree.XYZPoint> void searchNode(T value, KdNode node, int K, TreeSet<KdNode> results, Set<KdNode> examined) { examined.add(node); //Search node KdNode lastNode = null; Double lastDistance = Double.MAX_VALUE; if (results.size()>0) { lastNode = results.last(); lastDistance = lastNode.id.euclideanDistance(value); } Double nodeDistance = node.id.euclideanDistance(value); if (nodeDistance.compareTo(lastDistance)<0) { if (results.size()==K && lastNode!=null) results.remove(lastNode); results.add(node); } else if (nodeDistance.equals(lastDistance)) { results.add(node); } else if (results.size()<K) { results.add(node); } lastNode = results.last(); lastDistance = lastNode.id.euclideanDistance(value); int axis = node.depth % node.k; KdNode lesser = node.lesser; KdNode greater = node.greater; //Search children branches, if axis aligned distance is less than current distance if (lesser!=null && !examined.contains(lesser)) { examined.add(lesser); double nodePoint = Double.MIN_VALUE; double valuePlusDistance = Double.MIN_VALUE; if (axis==X_AXIS) { nodePoint = node.id.x; valuePlusDistance = value.x-lastDistance; } else if (axis==Y_AXIS) { nodePoint = node.id.y; valuePlusDistance = value.y-lastDistance; } else { nodePoint = node.id.z; valuePlusDistance = value.z-lastDistance; } boolean lineIntersectsCube = ((valuePlusDistance<=nodePoint)?true:false); //Continue down lesser branch if (lineIntersectsCube) searchNode(value,lesser,K,results,examined); } if (greater!=null && !examined.contains(greater)) { examined.add(greater); double nodePoint = Double.MIN_VALUE; double valuePlusDistance = Double.MIN_VALUE; if (axis==X_AXIS) { nodePoint = node.id.x; valuePlusDistance = value.x+lastDistance; } else if (axis==Y_AXIS) { nodePoint = node.id.y; valuePlusDistance = value.y+lastDistance; } else { nodePoint = node.id.z; valuePlusDistance = value.z+lastDistance; } boolean lineIntersectsCube = ((valuePlusDistance>=nodePoint)?true:false); //Continue down greater branch if (lineIntersectsCube) searchNode(value,greater,K,results,examined); } } 

The full source java can be found here .

Answer 2

You will find the nearest neighbor exactly as described on the Wikipedia page under the heading “Search for the nearest neighbor”. The description there applies in any number of dimensions. I.e:

• Go down the tree recursively from the root, as if you were going to insert the point you are looking for the nearest neighbor.
• When you reach the sheet, pay attention to it as the best side.
• On the way up the tree again, for each node, when you meet it:
  • If this is closer than the best, let's update the best - so far.
  • If the distance from the best point to the target point is greater than the distance from the target point to the splitting hyperplane on this node,
  • handles another child of the node too (using the same recursion).

Answer 3

I want to know what changes I should make when the points are 3-D (x, y, d).

You get the current axis in this row

 var int axis := depth mod k; 

Now, depending on the axis, you will find the median by comparing the corresponding property. For instance. if axis = 0 you compare with property x. One way to implement this is to pass the comparator function to a routine that performs the search.