KD-Trees are a special type of binary trees that are used to partition a k-dimensional space. They are used to solve the problem of finding the nearest neighbor of a point in a k-dimensional space. The name KD-Tree comes from the method of partitioning the space, the K stands for the number of dimensions in the space.
KD-tree are costly to mantain and balance. So use it only if you have a lot of queries to do, and the space is not changing. If you have a lot of queries, but the space is changing a lot, you should use a different data structure, such as a quadtree or a hash table.
On the binary tree KD-Tree, each node represents a k-dimensional point;
The tree is constructed by recursively partitioning the space into two half-spaces.
The partitioning is done by selecting a dimension and a value, and then splitting the space into two half-spaces.
The dimension and value are selected in such a way that the space is divided into two equal parts.
The left child of a node contains all the points for that dimension that are less than the value, and the right child contains all the points that are greater than or equal to the value.
The largest range is on the X axis, so we will select the median of the X axis as the root. The median of the X axis is (7, 15), and the starting dimension will be X.
For the next level, the left side candidates will be the ones with X less than (7, 15), and the right side, the ones that are greater or equal to (7, 15). But now this level will be governed sorted by Y:
#include<iostream>#include<vector>#include<algorithm>// vectorstructVector2f{floatx,y;Vector2f(floatx,floaty):x(x),y(y){}// subscript operator to be used in the KDTreefloat&operator[](size_tindex){returnindex%2==0?x:y;}// distanceSqrd between two vectorsfloatdistanceSqrd(constVector2f&other)const{return(x-other.x)*(x-other.x)+(y-other.y)*(y-other.y);}};// your object data structureclassGameObject{// your other datapublic:Vector2fposition;explicitGameObject(Vector2fposition={0,0}):position(position){}};// KDNodestructKDNode{GameObject*object;KDNode*left;KDNode*right;KDNode(GameObject*object,KDNode*left=nullptr,KDNode*right=nullptr):object(object),left(left),right(right){}};// KDTree managerclassKDTree{public:KDNode*root;KDTree():root(nullptr){}~KDTree(){// interactively delete the nodesstd::vector<KDNode*>nodes;nodes.push_back(root);while(!nodes.empty()){KDNode*current=nodes.back();nodes.pop_back();if(current->left!=nullptr)nodes.push_back(current->left);if(current->right!=nullptr)nodes.push_back(current->right);deletecurrent;}}voidinsert(GameObject*object){if(root==nullptr){root=newKDNode(object);}else{KDNode*current=root;size_tdimensionId=0;while(true){if(object->position[dimensionId]<current->object->position[dimensionId]){if(current->left==nullptr){current->left=newKDNode(object);break;}else{current=current->left;}}else{if(current->right==nullptr){current->right=newKDNode(object);break;}else{current=current->right;}}dimensionId++;}}}voidinsert(std::vector<GameObject*>objects,intdimensionId=0){if(objects.empty())return;if(objects.size()==1){insert(objects[0]);return;}// find the median for the current dimensionstd::sort(objects.begin(),objects.end(),[dimensionId](GameObject*a,GameObject*b){returna->position[dimensionId]<b->position[dimensionId];});// insert the medianautomedianIndex=objects.size()/2;insert(objects[medianIndex]);// insert the left and right exluding the medianinsert(std::vector<GameObject*>(objects.begin(),objects.begin()+medianIndex),(dimensionId+1)%2);insert(std::vector<GameObject*>(objects.begin()+medianIndex+1,objects.end()),(dimensionId+1)%2);}// get the nearest neighborGameObject*nearestNeighbor(Vector2fposition){returnNearestNeighbor(root,position,root->object,root->object->position.distanceSqrd(position),0);}GameObject*NearestNeighbor(KDNode*node,Vector2fposition,GameObject*best,floatbestDistance,intdimensionId){// create your own Nearest Neighbor algorithm. That's not hard, just follow the rules// 1. If the current node is null, return the best// 2. If the current node is closer to the position, update the best// 3. If the current node is closer to the position than the best, search the children// 4. If the current node is not closer to the position than the best, search the children// 5. Return the best}// draw the treevoiddraw(){std::vector<KDNode*>nodes;// uses space to shaw the level of the nodestd::vector<std::string>spaces;nodes.push_back(root);spaces.push_back("");while(!nodes.empty()){KDNode*current=nodes.back();std::stringspace=spaces.back();nodes.pop_back();spaces.pop_back();if(current->right!=nullptr){nodes.push_back(current->right);spaces.push_back(space+" ");}std::cout<<space<<":> "<<current->object->position.x<<", "<<current->object->position.y<<std::endl;if(current->left!=nullptr){nodes.push_back(current->left);spaces.push_back(space+" ");}}}};intmain(){// nodes: (3, 1), (7, 15), (2, 14), (16, 2), (19, 13), (12, 17), (1, 9)KDTreetree;std::vector<GameObject*>objects={newGameObject(Vector2f(3,1)),newGameObject(Vector2f(7,15)),newGameObject(Vector2f(2,14)),newGameObject(Vector2f(16,2)),newGameObject(Vector2f(19,13)),newGameObject(Vector2f(12,17)),newGameObject(Vector2f(1,9))};// insert the objectstree.insert(objects);// draw the treetree.draw();// get the nearest neighbor to (10, 10)GameObject*nearest=tree.nearestNeighbor(Vector2f(3,15));std::cout<<"Nearest neighbor to (3, 15): "<<nearest->position.x<<", "<<nearest->position.y<<std::endl;// will print 2, 14return0;}