Quadtrees for Space Decomposition, Java Implementation

Quadtree

As a continuation of the FADE graph drawing algorithm being implemented on my research internship, this week it was necessary to implement a quadtree data structure. The quadtree data structure will be utilised for the geometric clustering, by recursive decomposition, of the locations of graph vertices on a 2D plane. This data structure will facilitate the computation of non-edge forces in the graph drawing algorithm.

Quadtrees are a space decomposition technique. A quadtree is a data structure, not that different from a binary tree, which allows the recursive division of a space into four sections. The quadtree begins with a bounding box in a 2D plane; this is defined as the root of the tree. The boundaries of this tree are governed by the entirety of the graph drawing. This root node is divided into four smaller regions, each exactly one quarter the area of the root. Each child, in turn, can be divided into four sub-regions to get it’s children. This process is repeated until either a maximum tree depth is reached or every vertex object has been processed. A property can be declared to determine the maximum capacity of each node. Upon reaching this maximum capacity, the node is divided.

Quadtree Insertion

Inserting data into a quadtree is relatively straightforward. Given a point, starting at the root node, determine which quadrant this point occupies. Recurse to that child node and repeat the process until a leaf node is located. Subsequently, proceed to add the point to that node. If the maximum capacity of the node (as declared) is reached, split the node and reorganise the points with the appropriate sub-node.

Quadtree Search

To search a quadtree, again, starting at the root node, examine each child node, and check if it intersects the bounds being searched for. If this is the case, recurse into that child node. Upon reaching a leaf node, examine each data object to see if it intersects with the search bounds, and return the result.

Implementation

The quadtree is developed in Java. It was decided to implement a generic quadtree for potential use within other applications. The files included are not commented, because these particular files were for personal use and everything is relatively clear anyway. Anything you would like cleared up simply send me a quick message.

Feel free to use the quadtree code in any projects, I only ask that the authoring comments at the top of each file remain, and you do not try to pass the work off as your own. Thank you.

The source code is available on Github.