Quad_Tree_Component

Figure 5-4. Quad_Tree_Component Overview Diagram

Quad_Tree_Component Diagram

Motivation

Mechanics

The class Root_Quad_Tree is only a wrapper class for the class Quad_Tree_Component. This class is necessary to encapsulate the class Quad_Tree_Component because many methods in the Quad_Tree_Component call themself recursivly and the Root_Quad_Tree has the job to hold the root of the Quad-Tree and it also represents a kind of interface for the accessing components.

The class Quad_Tree_Component is a data structure which is a component of a Quad-Tree. A Quad-Tree is a tree of nodes and leafs. Our Quad-Tree is a special tree because each node has always four child nodes. Again each child node can be a node or a leaf. A node in the Quad-Tree is represented by an object of the class Quad_Tree_Component. Our Quad-Tree is always a full Quad-Tree with a particular depth. The root of the Quad-Tree covers an area of a particular Width and Height positioned by the Center_Point. All Node_Displays and Edge_Displays should be within this area. Otherwise they won't be drawn or couldn't be selected. A Node_Display/Edge_Display represents a node/edge in the Graph_Window. The four childs a Quad-Tree represent four quadrants of this area which are called Upper_Left, Upper_Right, Lower_Left and Lower_Right. Each child Quad-Tree covers the area with the size Width/2 and Height/2 and the according new Center_Point.

If you want to insert a new Node_Display into the Quad-Tree you call the method e.g. Insert_Node and the Node_Display will be passed on to the right position in the Quad-Tree. This position depends on the position of the Node_Display and the size of its pixmap. If the position is in the left and above of the Center_Point it will be passed on to the child Upper_Left and so on. But if the Node_Display lies on a border e.g. the pixmap lies on the x value of the Center_Point the Node_Display will be attached to the single-linked list Node_List of the current Quad_Tree_Component. The Node_Display also will be attached to the Node_List if the Quad-Tree is a leaf. The edges will be insert in a similar way.

The methode Remove_Node works like Insert_Node.

If the Node_Display lies outside of the area which is covered by the Quad-Tree. The Quad-Tree will be enhanced by a new object of the class Quad_Tree_Component and it will be placed on the top of the old Quad-Tree. So the new root of the Quad-Tree is this new object with the according size and position. The depth of the Quad-Tree increments by one.

If we want to know which nodes and edges are visible in our viewport all nodes and edges which come into question are on the path to the least quadrants which are within the viewport. Selecting an Object_Display works in a similar way but there you have to check only these Object_Displays which are on the path to the leaf which covers the position where you want to select an object. With the Quad-Tree we can reduce the set of Object_Displays which we have to handle.

Our Quad-Tree hasn't to be balanced or reorganized, so the structure of it remains constant which improves the performance of the Quad-Tree with a little drawback in allocating memory.

We never have to traverse the whole Quad-Tree unless the whole coverage of the Quad-Tree has to be displayed on the screen.

Figure 5-5. Quad_Tree_Component Overview Diagram

rough structure of the Quad-Tree

Rough structure of the access paths of the Quad-Tree to the Node_Displays and Edge_Displays