CASE STUDY
Quad-Tree Data Structure
Quad-Tree multidimensional data structure demonstration with interactive insertion and deletion.
Abstract
Teamed with 3 people to code and deploy a Quad Tree. A web application is the main interface for users to interact with the data structure.
About Quad-Tree
The Quad Tree is a data structure that is used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. Each node in the tree corresponds to a rectangular region in the plane. The tree is constructed by recursively subdividing the space until each region contains at most one point. The tree is then traversed to find the region that contains a given query point.
Interface
The upper part of the interface is the designer of the canvas and the plotted tree. From there you can set the size (order) from the QuadTree which must be a power of 2. You can also set the width and height of the resulting tree.
The middle part of the interface is the canvas. From there you can insert a point just clicking in some region of the canvas. The point is automatically assigned an ID. To delete a point, you can click on a region that contains a point. Any changes made to the canvas are reflected in the tree.
The lower part of the interface is the tree. It represents the tree resulting from the points inserted in the canvas