Quadtree

Mit der Funktion count_nodes kann die Anzahl aller Knoten (en.: Nodes) ermittelt werden. Dieser Funktion wird ein Pointer zu einem Knoten übergeben, dessen Kinderknoten (rekursiv) gezählt werden. Wenn der Knoten geteilt wurde (wenn der Pointer zu northEast nicht der Nullpointer ist) wird die Funktion count_nodes rekursiv auf alle Kinderknoten angewendet solange bis die tiefste Ebene erreicht wird. Am Schluss wird die Gesamtanzahl der Knoten von der Funktion zurückgegeben.

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;
}

Markieren

Die Funktion count_elements, welche alle Elemente (Punkte) im Quadtree zählt arbeitet analog zu der oben beschriebenen Funktion (count_nodes).

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;
}

Markieren

Die Funktion fetch_node ist eine Hilfsfunktion. Dieser Funktion wird ein Punkt übergeben und wenn dieser Punkt im Quadtree liegt, wird der Pointer zum dazugehörigen Knoten (der Knoten in dem der Punkt liegt) zurückgegeben. Zuerst wird überprüft, ob der Punkt in den Grenzen des Knotens liegt (Zeile 007). Liegt der Punkt im Knoten wird nun überprüft, ob dieser Knoten der tiefst mögliche ist (Zeile 014 -> northWest == nullptr). Sollte dies der Fall sein, wird als nächstes der Punkt im children-std::vector gesucht (Zeile 019). Wenn der Punkt gefunden wurde, so wird der jeweilige Pointer zum Knoten zurückgegeben. Wird der Punkt nicht im children-std::vector gefunden, so wird von der Funktion der Nullpointer zurückgegeben. Ist der jeweilige Knoten nicht der tiefst mögliche, so arbeitet sich die Funktion rekursiv weiter nach unten (Zeile 036-039).

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; 
}

Markieren

Der Sinn und Zweck dieses Quadtrees ist, zu ermitteln welche Elemente möglicherweise kollidieren. Deswegen wird eine Routine benötigt, welche mögliche Kollisionselemente ermittelt: Ausgehend von einem Punkt, welche anderen Punkte können mit dem gegebenen Punkt kollidieren?. Zuerst wird in der Funktion fetch_points der Pointer zu dem Knoten des gegebenen Punktes ermittelt. Ausgehend von diesem Pointer werden alle Punkte im children-vector ermittelt und von der Funktion zurückgegeben.

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;
}

Markieren

Das Entfernen eines einzelnen Elements (Punktes) aus dem Quadtree macht die Funktion delete_element, welcher der Punkt welcher entfernt werden soll übergeben wird. Zuerst wird mittels fetch_node der Pointer ermittelt, in welchem der Punkt liegt welcher entfernt werden soll. Sollte dies der Nullpointer sein, so wird die Funktion beendet da der Punkt nicht gefunden wurde (er liegt offenbar nicht im QT). Wurde ein Knoten gefunden, so werden alle Elemente des Knotens durchsucht (Zeile 017) bis der Punkt gefunden und gelöscht (Zeile 022) wird. Dieses Löschen entfernt aber nur den Punkt und ändert nichts an der Struktur des Quadtrees. Eine Möglichkeit ist, hier aufzuhören weil das Element entfernt wurde. Für eine effiziente Arbeitsweise des Quadtrees sollte aber nach dem Entfernen der Quadtree auf eine mögliche Zusammenführung (Vereinigung) von Knoten überprüft werden. Wird nun ein Element zum Tree hinzugefügt und gleich danach wieder entfernt, so ändert sich an der Struktur des Quadtrees nichts. Das Zusammenführung von Knoten wird mit der Funktion concatenate_nodes durchgeführt (Zeile 033).

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; 
}

Markieren

Das Zusammenführen (Zusammenklappen) des Baumes wird mit der Funktion concatenate_nodes durchgeführt. Die Funktion übernimmt einen Pointer zu einem Knoten als Argument. Sollte dieser Pointer auf den Root-Knoten zeigen, so wird nichts gemacht (Zeile 004). Ausgehend von diesem Knoten überprüft die Funktion, ob alle Geschwisterknoten die tiefst mögliche Ebene darstellen (Zeile 010 -> nullptr). Wenn die drei Geschwisterknoten und der übergebene Knoten (Funktionsargument) die tiefst möglichen Ebenen darstellen, so können diese Knoten eventuell vereinigt werden (Zeile 010). Sollten alle vier Knoten diese Bedingung erfüllen, wo wird die Gesamtanzahl ihrer Punkte ermittelt. Ist diese Anzahl geringer oder gleich maxAmtElements (Zeile 020), so werden alle Punkte in den Elternknoten verschoben und die vier (Blatt)Knoten werden aus dem Baum entfernt (Zeile 066). Zum Schluss wird der Pointer auf den Elternknoten rekursiv and die Funktion übergeben.

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); 
			} 
		} 
	} 
}

Markieren

Zusammenführung eines Knotens mit der obig beschriebenen Funktion

Das obige Bild illustriert das Verhalten der Funktion concatenate_nodes. Ausgehend von einem Quadtree in welchem zwei Punkte eingefügt wurden , wird nun einer der Punkte entfernt: Der erste Schritt ist das entfernen des gewünschten Punktes (Blauer Punkt in (a)). Der Punkt wird entfernt und der Pointer zu dem Knoten (grün schraffierter Bereich) wird an die Funktion concatenate_nodes übergeben. Die Geschwisterknoten (1, 2, 3 und 4 in (b)) werden dann auf ihre Tiefe und Anzahl der Elemente überprüft. Sollte ein Zusammenführen möglich sein, so werden alle Punkte in den Elternknoten verschoben, was zu (c) führt. Der Pointer zum Elternknoten (grün schraffierter Bereich in (c)) wird an concatenate_nodes übergeben und die Funktion wird aufgerufen. Das Endresultat ist in (d) dargestellt und die Funktion ist beendet, da der Rootknoten erreicht wurde.

Die letzte Funktion heißt relocate_element und übernimmt zwei Punkte als Funktionsargumente. Der erste Punkt stellt die Position vor der Verschiebung und der zweite die Position nach der Verschiebung dar. Zuerst (Zeile 003) wird überprüft, ob die Punkte eventuell identisch sind. In diesem Fall macht die Funktion nichts. Sollte dies nicht der Fall sein, so wird der Pointer zu dem Knoten des ersten Punktes gesucht (mittels fetch_node). Sind die Koordinaten des Punktes nach der Verschiebung außerhalb der Knotengrenzen (Zeile 011), so wird der entsprechende Punkt komplett aus dem Baum entfernt und neu eingefügt. War die Einfügung erfolgreich, so wird true zurückgegeben und wenn sie fehlgeschlagen hat so wird false zurückgegeben (in diesem Fall bewegte sich der Punkt aus dem Rootknoten heraus). Wenn der Punkt selbst nach der Verschiebung nicht seinen Knoten verlassen hat, so wird nur seine Position überschrieben (Zeile 030 - 047). Ein komplettes Entfernen und neu Einfügen des Punktes ist hier nicht notwendig.

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; 
}

Markieren

Dies stellt einen der einfachsten Quadtrees dar (inklusive Manipulationen / Darstellung des Baums). Üblicherweise werden die Pointer auf die Kinderknoten (hier northEast, northWest, ...) in einem Array gespeichert um deren Zugriff (z.B. über Schleifen) zu erleichtern. Ein weiterer Punkt ist, das Einfügen von Elementen nicht direkt über den Rootknoten durchzuführen (in der Funktion relocate_element). Ein Einfügen in den Elternknoten bietet sich hier an und wird die Geschwindigkeit mit großer Wahrscheinlichkeit erhöhen. In der selben Funktion (relocate_element) wird die Funktion fetch_node zwei mal aufgerufen (einmal direkt in Zeile 008 und einmal durch delete_element in Zeile 014 - siehe obigen Code). Verbesserungen sind durchaus möglich und werden (eventuell) später durchgeführt.

Videos: #01 #02

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