Quadtree

The function count_nodes is used, to count all the nodes in the Quadtree. As an argument, this function takes a pointer to a Quadtree and traverses recursively down this Quadtree. If the node has been split, i.e., if the pointer to northEast is not equal to the nullptr, the function will continue its recursion. Finally the total amount of nodes in the tree will be returned.

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015

// count the nodes of the tree
int Quadtree::count_nodes(Quadtree *t)
{
     // node has been split
     if (t->northEast != nullptr)
     {
          int nodes_NE = northEast->count_nodes(northEast);
          int nodes_SE = southEast->count_nodes(southEast);
          int nodes_SW = southWest->count_nodes(southWest);
          int nodes_NW = northWest->count_nodes(northWest);
          return nodes_NE + nodes_SE + nodes_SW + nodes_NW;
     }

     return 1;
}

Mark Code

The function to count all elements in the tree count_elements works similarly as the function described above:

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024

// count the elements residing in the tree
int Quadtree::count_elements(Quadtree *t)
{
     int fetch_elements = 0;

     // node has been split - continue with the recursion
     if (t->northEast != nullptr)
     {
          fetch_elements += northEast->count_elements(northEast);
          fetch_elements += southEast->count_elements(southEast);
          fetch_elements += southWest->count_elements(southWest);
          fetch_elements += northWest->count_elements(northWest);
     }
     // deepest (child)node possible
     else
     {
          if (t->children.size() > 0)     // there are elements in this node
          {
               fetch_elements += t->children.size();
          }
     }

     return fetch_elements;
}

Mark Code

The function fetch_node serves as an auxiliary function. Its purpose is to retrieve the pointer to the node, in which the given point resides. From the top of the tree (which is the root node) the function checks, if the coordinates of the given point matches the boundaries of the node (line 007). With the point inside of the node and the pointer to the child nodes being empty (line 014) we can conclude that the program reached the deepest node possible in which the given point may reside. If the given point matches the point passed to the function, the corresponding pointer to the node is returned. If the given point lies in the boundaries but the node has been split, the function recursively traverses (line 036-039) down until the deepest node has been reached. If the function fails to find (a) the node in which the point resides which means the point is not even located in the root node or (b) the point can not be found in the children-vector of the deepest reached node, it will return zero.

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044

// fetch the node in which the given element resides
Quadtree *Quadtree::fetch_node(pt2d seekPt)
{
 static Quadtree *ReturnNode;

 // point outside of node
 if (seekPt.x > boundary2->cx+boundary2->dim or seekPt.x <= boundary2->cx-boundary2->dim or seekPt.y > boundary2->cy+boundary2->dim or seekPt.y <= boundary2->cy-boundary2->dim)
 {
 }
 // else -> point is inside of the node
 else
 {
 // deepest node corresponding to this point reached. Return the pointer to this node
 if (northWest == nullptr)
 {
 bool foundNode = false;
 ReturnNode = nullptr;

 for (int i = 0; i < (int)children.size(); i++)
 {
 if (seekPt.x == children[i].x and seekPt.y == children[i].y)
 {
 foundNode = true;
 }
 }

 if (foundNode == true)
 {
 ReturnNode = this;
 }

 return ReturnNode;
 }
 else
 {
 ReturnNode = northEast->fetch_node(seekPt);
 ReturnNode = northWest->fetch_node(seekPt);
 ReturnNode = southWest->fetch_node(seekPt);
 ReturnNode = southEast->fetch_node(seekPt);
 }
 }

 return ReturnNode;
}

// fetch the node in which the given element resides 
Quadtree *Quadtree::fetch_node(pt2d seekPt) 
{ 
	static Quadtree *ReturnNode; 
 
	// point outside of node 
	if (seekPt.x > boundary2->cx+boundary2->dim or seekPt.x &amp;lt;= boundary2->cx-boundary2->dim or seekPt.y > boundary2->cy+boundary2->dim or seekPt.y &amp;lt;= boundary2->cy-boundary2->dim) 
	{ 
	} 
	// else -> point is inside of the node 
	else 
	{ 
		// deepest node corresponding to this point reached. Return the pointer to this node 
		if (northWest == nullptr) 
		{ 
			bool foundNode = false; 
			ReturnNode = nullptr; 
 
			for (int i = 0; i &amp;lt; (int)children.size(); i++) 
			{ 
				if (seekPt.x == children[i].x and seekPt.y == children[i].y) 
				{ 
					foundNode = true; 
				} 
			} 
 
			if (foundNode == true) 
			{ 
				ReturnNode = this; 
			} 
 
			return ReturnNode; 
		} 
		else 
		{ 
			ReturnNode = northEast->fetch_node(seekPt); 
			ReturnNode = northWest->fetch_node(seekPt); 
			ReturnNode = southWest->fetch_node(seekPt); 
			ReturnNode = southEast->fetch_node(seekPt); 
		} 
	} 
 
	return ReturnNode; 
}

Mark Code

The whole point of this Quadtree is to determine which elements may collide without checking all elements possible. Therefore we need a function which retrieves possible collision-candidates: Given a certain point in the tree, which elements are possible candidates to collide with this point?. After retrieving the pointer to the node in which the given point lies, all elements in the std::vector children are returned.

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016

// searches the node in which seekPt resides and returns all the elements from this node
std::vector<pt2d> Quadtree::fetch_points(pt2d seekPt)
{
 std::vector <pt2d> return_elements;

 // search the node in which the point seekPt resides
 Quadtree *search_node = fetch_node(seekPt);

 // retrieve all the pts from the node
 for (int i = 0; i < (int)search_node->children.size() ; i++)
 {
 return_elements.push_back(search_node->children[i]);
 }

 return return_elements;
}

Mark Code

Not only do we want to add, but also remove elements from the tree. As an argument the function takes a point which should be removed from the Quadtree. First the function delete_element tries to locate the pointer to the node in which deletePt lies through the function fetch_node. If this query returns the nullptr, something went wrong (e.g., the point lies outside the root node or the point can not be found in the children std::vector in the deepest node). If a corresponding node has been found its elements (line 017) are searched through. If the point can be found it will be removed from the node (line 022). This removes the element from the tree and we could stop here. But to reverse the insertion during a deletion, one must collapse the Quadtree which is performed with the function concatenate_nodes which is called (line 033) after the removal of the point.

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037

// remove a single element from the tree
bool Quadtree::delete_element(pt2d deletePt)
{
 // try to locate the node where the point lies
 Quadtree *nodePtReside = fetch_node(deletePt);

 if (nodePtReside == nullptr) // this element is not in the QT
 {
 return false;
 }
 else
 {
 // retrieve location of deletePt in the children std::vector
 int del_index = -1;
 bool foundItem = false;

 for (del_index = 0; del_index < (int)nodePtReside->children.size(); del_index++)
 {
 if (deletePt.x == nodePtReside->children[del_index].x and deletePt.y == nodePtReside->children[del_index].y)
 {
 foundItem = true;
 nodePtReside->children.erase(nodePtReside->children.begin()+del_index);
 break;
 }
 }

 // element was not found -> deletion failed
 if (foundItem == false)
 {
 return false;
 }

 concatenate_nodes(nodePtReside);
 }

 return true;
}

// remove a single element from the tree 
bool Quadtree::delete_element(pt2d deletePt) 
{ 
	// try to locate the node where the point lies 
	Quadtree *nodePtReside = fetch_node(deletePt); 
 
	if (nodePtReside == nullptr) // this element is not in the QT 
	{ 
		return false; 
	} 
	else 
	{ 
		// retrieve location of deletePt in the children std::vector 
		int del_index = -1; 
		bool foundItem = false; 
 
		for (del_index = 0; del_index &amp;lt; (int)nodePtReside->children.size(); del_index++) 
		{ 
			if (deletePt.x == nodePtReside->children[del_index].x and deletePt.y == nodePtReside->children[del_index].y) 
			{ 
				foundItem = true; 
				nodePtReside->children.erase(nodePtReside->children.begin()+del_index); 
				break; 
			} 
		} 
 
		// element was not found -> deletion failed 
		if (foundItem == false) 
		{ 
			return false; 
		} 
 
			concatenate_nodes(nodePtReside); 
		} 
 
	return true; 
}

Mark Code

Collapsing or concatenating of the tree is performed with the function concatenate_nodes. This function takes a pointer to a node as an argument. If this node is the root node, the function does nothing (line 004). Starting from the passed node the function checks, if the sibling nodes are the deepest nodes possible (line 010). Sibling node means, if we for example deleted a point from northEast, the sibling nodes are northWest, southEast and southWest of the parent node (literally its siblings). Since all the points in the tree are stored in the deepest (leaf)nodes possible, we know that if all four nodes (target node and all three siblings) are the deepest ones possible we may be able to collapse these four nodes (line 010). If this is the case, the amount of elements in the four nodes is determined. If the sum is smaller or equal to maxAmtElements (line 020), all points from the four nodes are moved into their parent node. The four nodes are then cleared (line 066) and the pointer of the parent is passed to the function concatenate_nodes to recursively collapse the quadtree.

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073

// auxiliary function used by delete_element(). Used to collapse nodes and redistribute elements after collapsing
void Quadtree::concatenate_nodes(Quadtree *concat_this_node_maybe)
{
 if (concat_this_node_maybe->parent == concat_this_node_maybe) // point resides in parent -> do nothing
 {
 }
 else
 {
 // Concatenate because all four nodes (3 sibling nodes and the one where the point lies) are empty
 if (concat_this_node_maybe->parent->northEast->northEast == nullptr && concat_this_node_maybe->parent->northWest->northEast == nullptr && concat_this_node_maybe->parent->southEast->northEast == nullptr && concat_this_node_maybe->parent->southWest->northEast == nullptr)
 {
 int amtElemntsNE = concat_this_node_maybe->parent->northEast->children.size();
 int amtElemntsNW = concat_this_node_maybe->parent->northWest->children.size();
 int amtElemntsSE = concat_this_node_maybe->parent->southEast->children.size();
 int amtElemntsSW = concat_this_node_maybe->parent->southWest->children.size();

 unsigned int sumElements = amtElemntsNE + amtElemntsNW + amtElemntsSE + amtElemntsSW;

 // move all elements from the leaf nodes into their parents node and delete the leaf nodes
 if (sumElements <= maxAmtElements)
 {
 // move elements from the northEast node to the parent node
 for (int i = 0; i < amtElemntsNE; i++)
 {
 float reshufflex = concat_this_node_maybe->parent->northEast->children[i].x;
 float reshuffley = concat_this_node_maybe->parent->northEast->children[i].y;

 pt2d reinsertPt(reshufflex, reshuffley);
 concat_this_node_maybe->parent->children.push_back(reinsertPt);
 }

 // move elements from the northWest node to the parent node
 for (int i = 0; i < amtElemntsNW; i++)
 {
 float reshufflex = concat_this_node_maybe->parent->northWest->children[i].x;
 float reshuffley = concat_this_node_maybe->parent->northWest->children[i].y;

 pt2d reinsertPt(reshufflex, reshuffley);
 concat_this_node_maybe->parent->children.push_back(reinsertPt);
 }

 // move elements from the southEast node to the parent node
 for (int i = 0; i < amtElemntsSE; i++)
 {
 float reshufflex = concat_this_node_maybe->parent->southEast->children[i].x;
 float reshuffley = concat_this_node_maybe->parent->southEast->children[i].y;

 pt2d reinsertPt(reshufflex, reshuffley);
 concat_this_node_maybe->parent->children.push_back(reinsertPt);
 }

 // move elements from the southWest node to the parent node
 for (int i = 0; i < amtElemntsSW; i++)
 {
 float reshufflex = concat_this_node_maybe->parent->southWest->children[i].x;
 float reshuffley = concat_this_node_maybe->parent->southWest->children[i].y;

 pt2d reinsertPt(reshufflex, reshuffley);
 concat_this_node_maybe->parent->children.push_back(reinsertPt);
 }

 // generate a pointer to the next node to concatinate (prevents an invalid read)
 Quadtree *concat_next = concat_this_node_maybe->parent;

 // delete the sibling nodes (of the removed point)
 concat_this_node_maybe->parent->clearNode();

 // proceed with the recursion
 concatenate_nodes(concat_next);
 }
 }
 }
}

// auxiliary function used by delete_element(). Used to collapse nodes and redistribute elements after collapsing 
void Quadtree::concatenate_nodes(Quadtree *concat_this_node_maybe) 
{ 
	if (concat_this_node_maybe->parent == concat_this_node_maybe) // point resides in parent -> do nothing 
	{ 
	} 
	else 
	{ 
		// Concatenate because all four nodes (3 sibling nodes and the one where the point lies) are empty 
		if (concat_this_node_maybe->parent->northEast->northEast == nullptr && concat_this_node_maybe->parent->northWest->northEast == nullptr && concat_this_node_maybe->parent->southEast->northEast == nullptr && concat_this_node_maybe->parent->southWest->northEast == nullptr) 
		{ 
			int amtElemntsNE = concat_this_node_maybe->parent->northEast->children.size(); 
			int amtElemntsNW = concat_this_node_maybe->parent->northWest->children.size(); 
			int amtElemntsSE = concat_this_node_maybe->parent->southEast->children.size(); 
			int amtElemntsSW = concat_this_node_maybe->parent->southWest->children.size(); 
 
			unsigned int sumElements = amtElemntsNE + amtElemntsNW + amtElemntsSE + amtElemntsSW; 
 
			// move all elements from the leaf nodes into their parents node and delete the leaf nodes 
			if (sumElements &amp;lt;= maxAmtElements) 
			{ 
				// move elements from the northEast node to the parent node 
				for (int i = 0; i &amp;lt; amtElemntsNE; i++) 
				{ 
					float reshufflex = concat_this_node_maybe->parent->northEast->children[i].x; 
					float reshuffley = concat_this_node_maybe->parent->northEast->children[i].y; 
 
					pt2d reinsertPt(reshufflex, reshuffley); 
					concat_this_node_maybe->parent->children.push_back(reinsertPt); 
				} 
 
				// move elements from the northWest node to the parent node 
				for (int i = 0; i &amp;lt; amtElemntsNW; i++) 
				{ 
					float reshufflex = concat_this_node_maybe->parent->northWest->children[i].x; 
					float reshuffley = concat_this_node_maybe->parent->northWest->children[i].y; 
 
					pt2d reinsertPt(reshufflex, reshuffley); 
					concat_this_node_maybe->parent->children.push_back(reinsertPt); 
				} 
 
				// move elements from the southEast node to the parent node 
				for (int i = 0; i &amp;lt; amtElemntsSE; i++) 
				{ 
					float reshufflex = concat_this_node_maybe->parent->southEast->children[i].x; 
					float reshuffley = concat_this_node_maybe->parent->southEast->children[i].y; 
 
					pt2d reinsertPt(reshufflex, reshuffley); 
					concat_this_node_maybe->parent->children.push_back(reinsertPt); 
				} 
 
				// move elements from the southWest node to the parent node 
				for (int i = 0; i &amp;lt; amtElemntsSW; i++) 
				{ 
					float reshufflex = concat_this_node_maybe->parent->southWest->children[i].x; 
					float reshuffley = concat_this_node_maybe->parent->southWest->children[i].y; 
 
					pt2d reinsertPt(reshufflex, reshuffley); 
					concat_this_node_maybe->parent->children.push_back(reinsertPt); 
				} 
 
				// generate a pointer to the next node to concatinate (prevents an invalid read) 
				Quadtree *concat_next = concat_this_node_maybe->parent; 
 
				// delete the sibling nodes (of the removed point) 
				concat_this_node_maybe->parent->clearNode(); 
 
				// proceed with the recursion 
				concatenate_nodes(concat_next); 
			} 
		} 
	} 
}

Mark Code

Concatenation of nodes using the function above

The figure above illustrates the behaviour of the function concatenate_nodes. Starting with a quadtree in which two points are inserted with a maximum of one point per node. The first step ist to delete the desired point (blue point in (a)) and pass the pointer to the node in which this point lies to the function concatenate_nodes (green highlighted node in (a)). The points in the sibling nodes (1, 2, 3 and 4 in (b)) are then checked whether the sum of their points is smaller or equal than maxAmtElements. If this is true all the points from the nodes are relocated into their parent node which leads to (c). The parent is then passed again to the function concatenate_nodes and similarly the nodes are concatenated which results in (d). Since we reached the root node the function stops here.

The last function is called relocate_element and takes two points as arguments. The first point is the location before movement and the second point passed to the function is the location past the movement. First (line 003) it is checked, if the points are the same - we can abort here because movement is impossible here. If this is not the case, we search the node in which the point lies before movement (through fetch_node). If the coordinates of the point after movement are outside of the node (line 011), we delete the point and reinsert it. If the insertion succeeded the function returns true and if not it returns false (which means the point moved out of the root node). If the point does not pass the borders of the node during movement, removal and reinsertion is not needed. In this case the coordinates in the children std::vector are overwritten (line 045, 046).

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050

bool Quadtree::relocate_element(pt2d ptOrigin, pt2d PtMoveTo)
{
 if (ptOrigin.x == PtMoveTo.x and ptOrigin.y == PtMoveTo.y)
 {
 return false;
 }

 Quadtree *nodePtReside_Origin = fetch_node(ptOrigin);

 // PtMoveTo lies outside of the node -> remove and reinsert this element
 if (PtMoveTo.x > nodePtReside_Origin->boundary2->cx+nodePtReside_Origin->boundary2->dim or PtMoveTo.x <= nodePtReside_Origin->boundary2->cx-nodePtReside_Origin->boundary2->dim or PtMoveTo.y > nodePtReside_Origin->boundary2->cy+nodePtReside_Origin->boundary2->dim or PtMoveTo.y <= nodePtReside_Origin->boundary2->cy-nodePtReside_Origin->boundary2->dim)
 {
 // TODO - remove element, reinsert into the parent node not the root node
 delete_element(ptOrigin);

 bool check_insert = insert(PtMoveTo);

 if (check_insert)
 {
 return true;
 }
 // element could not be fit into the root node, i.e., exited the root tree
 else
 {
 return false;
 }

 }
 //overwrite the point since it did not move out of the node
 else
 {
 // find the position of ptOrigin and overwrite its coordinates with the ones of PtMoveTo
 int foundIndex = -1;

 for (int i = 0; i < (int)nodePtReside_Origin->children.size(); i++)
 {
 if (nodePtReside_Origin->children[i].x == ptOrigin.x and nodePtReside_Origin->children[i].y == ptOrigin.y)
 {
 foundIndex = i;
 break;
 }
 }

 // update the coordinates, i.e., move the element
 nodePtReside_Origin->children[foundIndex].x = PtMoveTo.x;
 nodePtReside_Origin->children[foundIndex].y = PtMoveTo.y;
 }

 return true;
}

bool Quadtree::relocate_element(pt2d ptOrigin, pt2d PtMoveTo) 
{ 
	if (ptOrigin.x == PtMoveTo.x and ptOrigin.y == PtMoveTo.y) 
	{ 
		return false; 
	} 
 
	Quadtree *nodePtReside_Origin = fetch_node(ptOrigin); 
 
	// PtMoveTo lies outside of the node -> remove and reinsert this element 
	if (PtMoveTo.x > nodePtReside_Origin->boundary2->cx+nodePtReside_Origin->boundary2->dim or PtMoveTo.x &amp;lt;= nodePtReside_Origin->boundary2->cx-nodePtReside_Origin->boundary2->dim or PtMoveTo.y > nodePtReside_Origin->boundary2->cy+nodePtReside_Origin->boundary2->dim or PtMoveTo.y &amp;lt;= nodePtReside_Origin->boundary2->cy-nodePtReside_Origin->boundary2->dim) 
	{ 
		// TODO - remove element, reinsert into the parent node not the root node 
		delete_element(ptOrigin); 
 
		bool check_insert = insert(PtMoveTo); 
 
		if (check_insert) 
		{ 
			return true; 
		} 
		// element could not be fit into the root node, i.e., exited the root tree 
		else 
		{ 
			return false; 
		} 
 
	} 
	//overwrite the point since it did not move out of the node 
	else 
	{ 
		// find the position of ptOrigin and overwrite its coordinates with the ones of PtMoveTo 
		int foundIndex = -1; 
 
		for (int i = 0; i &amp;lt; (int)nodePtReside_Origin->children.size(); i++) 
		{ 
			if (nodePtReside_Origin->children[i].x == ptOrigin.x and nodePtReside_Origin->children[i].y == ptOrigin.y) 
			{ 
				foundIndex = i; 
				break; 
			} 
		} 
 
		// update the coordinates, i.e., move the element 
		nodePtReside_Origin->children[foundIndex].x = PtMoveTo.x; 
		nodePtReside_Origin->children[foundIndex].y = PtMoveTo.y; 
	} 
 
	return true; 
}

Mark Code

This concludes the easiest quadtree possible with basic functionality. Usually the pointer to the child-nodes (here northEast, northWest, ...) are stored in an array to make iteration over these objects easier. Another thing would be, not to insert the elements through the root node in the function relocate_element. Just insert it into the parent node. Also in the same function (relocate_element), the function fetch_node is called twice (once directly at line 008 and once through delete_element at line 014 - see the code above). Possible optimizations are not sparse and will (probably) be discussed later.

Videos: #01 #02

Source files (Github):
https://github.com/clauskovacs/quadtree-vertices-2d