QuadTree Visualizer

QuadTree Visualizer

Randeep Kaur Kahlon1, Amey Thakur2, Hasan Rizvi3, Mega Satish4, Ajay Davare5

1Assistant Professor, Department of Computer Engineering, University of Mumbai Affiliated Institute Terna Engineering College, Mumbai, Maharashtra, India

2-5Undergraduate Students, Department of Computer Engineering, University of Mumbai Affiliated Institute Terna Engineering College, Mumbai, Maharashtra, India

Abstract We propose to develop a program that can show a QuadTree view and data model architecture. Nowadays, many digital map applications have the need to present large quantities of precise point data on the map. Such data can be weather information or the population in towns. With the development of the Internet of Things (IoT), we expect such data will grow at a rapid pace. However, visualizing and searching in such a magnitude of data becomes a problem as it takes a huge amount of time. QuadTrees are data structures that are used to efficiently store point data in a two-dimensional environment. Each node in this tree has a maximum of four children. QuadTrees allow us to visualize the data easily and rapidly compared to other data structures. This project aims to build an application for interactively visualizing such data, using a combination of grid-based clustering and hierarchical clustering, along with QuadTree spatial indexing. This application illustrates the simulation of the working of the QuadTree data structure.

Keywords QuadTree Visualizer, Q-Tree, Data Structure, Spatial Indexing, Coefficient of Restitution, Collision Detection, QuadTree Algorithm.

1. INTRODUCTION

   The QuadTree is a spatial data structure with a hierarchical structure. It's a tree with each level corresponding to a further refinement of the space in question. Though QuadTrees come in a variety of shapes and sizes, they can be used in a variety of ways. The concept can be applied to any dimension, and it is always a recursive subdivision of space that aids in the storage of information and provides the most vital or interesting details regarding space. In QuadTrees, we begin by adding pointers to its root node, which defines all potential space. The node divides into four child nodes when the number of points in the node reaches a predetermined maximum capacity. When any of those nodes has reached its full point capacity, it splits into four child nodes, and so on. QuadTrees have a range of applications; from internet services handling millions of requests every second, image compression, handling geolocation services, searching for nodes in 2-D areas, collision detection and more. Collision detection is a crucial feature in the majority of video games. Detecting when two entities collide is critical in both 2D and 3D games, since bad collision detection may lead to some very intriguing effects. Numerous games need the use of collision detection techniques to identify whether two objects have interacted, however, these algorithms are frequently costly procedures that may significantly slow down a system. In this paper, we will be addressing QuadTrees, and how we can use them to speed up collision detection by skipping pairs of objects that are too far apart to collide. Well be writing a general-

   purpose, scalable and re-usable QuadTree library in Typescript and importing it into a visualization tool to depict its internal workings.

   This project aims to provide a web application for visualizing the QuadTree structure. QuadTree. The users should be able to understand the working of the QuadTree and experience the simulation provided on the web application. This Visualizer provides an interactive environment where users can change configurations of the QuadTree and environment conditions at runtime.

2. LITERATURE SURVEY

   1. Brief History of QuadTree

      A QuadTree [1][2][3] is a tree data structure with zero or four offspring at each node. Its key distinguishing feature is its method of recursively partitioning a flat 2-D [2] space into four regions. The data associated with a leaf cell differs depending on the application, but the leaf cell is a "unit of relevant spatial information." The subdivided areas or regions can be square or rectangular or any other form. This data structure was named a QuadTree by Raphael Finkel and J.L. Bentley in 1974.

   2. Existing Systems

   Table 1: Existing Systems

3. PROPOSED METHODOLOGY

1. Brief History of QuadTree

   The QuadTree is a data structure for organizing objects based on their locations in a two-dimensional space. By definition, a QuadTree [2] is a tree in which each node has at most four children. QuadTree implementations ensure that as points are added to the tree, nodes are rearranged such that none of them has more than four children. Figure 1 below illustrates the general concept of QuadTree data structure.

   Figure 1: QuadTree Data Structure

   The QuadTree partitioning strategy divides space [1][2] into four quadrants at each level. When a quadrant contains more than one object, the tree subdivides that region into four smaller quadrants, adding a level to the tree. A similar partitioning is also known as a Q-tree. QuadTrees are a way of partitioning space so that it's easy to traverse and search.

2. Applications of QuadTree

   It is used extensively in computer graphics, image compression and is also used to represent spatial relations. Visualizing data points with a QuadTree [3] and checking and detecting collisions. The computer issue of identifying the collision of two or more bodies is known as collision detection. Collision detection [5] is a basic problem in computational geometry that has applications in a wide range of computer domains. Figure 2 shows the use case of Quadtree Visualizer.

   Figure 2: QuadTree Visualizer

   QuadTrees are also implemented for spatial indexing [3] while searching a particular point or location in a map. QuadTrees are very efficient as they can sparse through the maps very easily and quickly compared to other methods. Figure 3 shows the use case of QuadTree Spatial Indexing.

   Figure 3: QuadTree Spatial Indexing

   QuadTrees, for example, can handle a sparse Mario level a billion tiles across, where one of the tiles contains the finishing spot. A QuadTree will split the arrival spot into different cells and still use gigantic cells for the empty spaces. Figure 4 shows the use case of QuadTree in Gaming.

   Figure 4: QuadTree in Gaming

   1. Some possible use cases of QuadTree

      1. Hit detection:

      For example, as seen in the maps above, there are a lot of points in space. If we wish to discover an arbitrary point P, we can do it inside that set of points. This quickly turns into a frantic process. We could check each and every single point to P, but when there are 1000 points yet none of them are P, we will have to do 1000 comparisons to figure out which point is P.

      Alternatively, we may get a very rapid lookup by retaining a matrix (a 2D array) of Booleans for each and every conceivable point in this space. However, suppose the area occupied by these points is 1 million × 1 million so we need to keep 1,000,000,000,000 variables.

      A QuadTree would seem to be a better choice in this scenario. To find P, the QuadTree [1] will determine which quadrant it is in. Then it will determine which quadrant within that quadrant it is in. Even if there are 1000 points in the space, it will only have to execute this seven

      times for a 100×100 space (provided points can have numerical value only). Once it's found that rctangle node, it just needs to test whether any of the four-leaf equals P.

      2. Sparse Data using QuadTree:

      QuadTrees are ideal for sparse data to search for a particular point. By only performing computations between items in comparable nodes/quads, QuadTrees aid in obtaining knowledge about which collisions in an environment are worth investigating.

      QuadTree nodes split into four evenly-sized leaf nodes when the number of objects inside them reaches a certain capacity. Objects are inserted into a fresh QuadTree every iteration, which places each object in its deepest possible node.The QuadTree algorithm improves upon the naive T(n) = (n2) algorithm and achieves T(n) = O(n2), T(n) = (nlog(n)). Inadvertently, QuadTrees depending on pixels are a sort of trie.

   2. Limitations of QuadTree

      The fundamental drawback of QuadTrees is that comparing two pictures [4] that vary only in rotations or translation is nearly difficult. This is due to the fact that the QuadTree depiction of such pictures will be so distinct. The picture rotation methods offered are limited to revolutions of 90 degrees. There is no alternative rotation available, thus there is no translation facility. Figure 5.1 shows the original image and Figure 5.2 shows the rotated images. As we can see, it is not possible to compare two images that are different in terms of rotation.

      (5.1) First Image (5.2) Rotated Image

      Figure 5: Image Translation in QuadTree

   3. Types of QuadTree

      There are three types of QuadTrees:

      1. Point QuadTree

      2. Edge QuadTree

      3. Polygonal Map QuadTree.

         Some characteristics are shared by all QuadTrees:

         • They break space down into flexible cells.

         • There is a maximum capacity for each cell (or bucket). When the bucket reaches its full capacity, it separates.

         • The QuadTree's spatial decomposition is followed by the tree directory.

   4. Working of QuadTree

      The Figure 6 below depicts how a QuadTree [7] alters as a result of insertion of a point E:

      1. Make four boxes out of the current two- dimensional space.

      2. If a box includes one or more points, make a child object that stores the box's two- dimensional space.

      3. Do not generate a child for a box that does not contain any points.

      4. Repeat with each of the children.

         Figure 6: Working of QuadTree

   5. Algorithm

      Three types of nodes are used in quadtree:

      1. Point node: It is used to represent a point. It is always a leaf node.

      2. Empty node: It is used as a leaf node to represent that no point exists in the region it represents.

      3. Region node: This is always an internal node. It is used to represent a region. A region node always has 4 children nodes that can either be a point node or an empty node.

         1. Insertion in QuadTree

            Insertion: A recursive function for storing a point in a QuadTree.

            1. As the current node, begin with the root node.

            2. If the specified point is not within the boundary indicated by the current node, the insertion should be terminated with an error.

            3. Determine the best child node to store the point.

            4. If the child node is empty, it should be replaced with a point node that represents the point. Insertion should be stopped.

            5. Replace the child node with a region code if it is a point node. For the point that was just

               replaced, use insert. Set the current node to be the region's freshly generated node.

            6. Set the specified child node as the current node if it is a region node. Proceed to step 2.

         2. Search in QuadTree

            Search: This is a boolean function that determines whether or not a point exists in 2D space.

            1. As the current node, begin with the root node.

            2. If the specified point is not within the boundary indicated by the current node, the search should be terminated with an error.

            3. Determine the best child node to hold the point in.

            4. Return FALSE if the child node is empty.

            5. Return TRUE if the child node is a point node and matches the specified point, else return FALSE.

            6. Set the current node as the child region node if the child node is a region node. Proceed to step 2.

         3. Complexity

            1. Time complexity:

               • Find: O(log2N)

               • Insert: O(log2N)

               • Search: O(log2N)

            2. Space complexity:

               • O(k log2N), where k is the count of points in the space and Space is of dimension N x M, N >= M

   6. Collision in QuadTree

      Because the data points in the visualizer are always shifting, collisions are unavoidable. Collision [5] is the meeting of two bodies, in this case data points in the shape of circles. The QuadTree visualization is built on top of a 2D Collision System with a restitution coefficient that can be adjusted to differentiate between elastic and inelastic impacts. Collision detection is a costly activity. One method for speeding up collision detection is to use QuadTrees

   7. Coefficient of Restitution

      The coefficient of restitution [6] is the ratio of the final velocity to the starting velocity of two objects after they collide. The restitution coefficient, written as 'e,' is a unitless quantity with values ranging from 0 to 1.

      The coefficient of restitution is a quantity that represents the nature of the colliding materials. The coefficient of restitution informs about the elasticity of the collision. A fully elastic collision is one in which there is no

      loss of total kinetic energy. The greatest coefficient of restitution for this sort of collision is e = 1. A fully inelastic collision is one in which all of the kinetic energy is wasted. They have a restitution coefficient of e = 0. The majority of real-life crashes occur in the middle. The Coefficient of Restitution mathematical formula is as follows:

      Coefficient of Restitution (e) =

      You can see from the following equation that you

      always divide the smaller number by a larger number. As a result, the restitution coefficient is always positive.

   8. Workflow of QuadTree

      Figure 7 illustrates the workflow of the QuadTree application. Next.js is responsible for both client and server- side scripting.

      Figure 7: Workflow of QuadTree

   9. Model Architecture

An architectural model is a simplified representation of a system. It is an estimate that captures the various system characteristics. It is a generalized form that has all of the system's critical elements. The process of modelling architecture entails determining the system's features and expressing them as models so that the system may be understood. Architecture models make it possible to see information about the system represented by the model. Figure 8 depicts the web application's model architecture.

A. Homepage

1. RESULTS

   Figure 11 illustrates the homepage of the web application. Here we can visualize a QuadTree with the data points and the different divisions of the QuadTree.

   Figure 8: Model Architecture of QuadTree

   IV. DESIGN

   1. Experimental Setup

      • Since we are using Next.js in our project, we first need to have Node.js.

      • The web application works on http://localhost:3000.

      • To run the application locally, we need to install the packages required using the npm command: npm install package.json

      • Figure 9 shows the command prompt with the packages installed using the npm install commands.

        Figure 9: Command: npm install package.json

      • After installing all the dependencies, w then run the command: npm run dev.

      • After we run the command: npm run dev. It will run the developer server.

      • Figure 10 depicts the compilation and running of the server. The server is working on http://localhost:3000.

        Figure 10: Compilation & Server Hosting

        Figure 11: Homepage

   2. Clear QuadTree

      Figure 12 shows a clean QuadTree without the data points. Since there are no points, we can see only the square.

      Figure 12: Clear QuadTree

   3. Spawn Bodies

      Figure 13 depicts the spawn circles in the QuadTree. Here we can see the clear division of the QuadTree.

      Figure 13: Spawn Bodies

   4. Random Bodies

      Figure 14.1 & Figure 14.2 show the random bodies generated randomly in the QuadTree.

      Figure 14.1: Random Bodies

      Figure 14.2: Random Bodies

   5. Random & Spawn Bodies

      Figure 15.1 & 15.2 Figure shows the combination of both random and spawn bodies in the QuadTree.

      Figure 15.1: Random & Spawn Bodies

      Figure 15.2: Random & Spawn Bodies

   6. Control Panel

      Figure 16 illustrates the control panel. The control panel here is used to simulate different environments in the QuadTree such as types of bodies, the coefficient of restitution and the frames per second of the movement of the bodies.

      Figure 16: Control Panel

2. FUTURE SCOPE

   Since QuadTrees are a type of tree data structure in which each internal node has exactly four children, they are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or areas. The areas can be rectangular, square, or any other form. The QuadTree is used as a utility as part of the Maps SDK for iOS Utility Library. Theyve also been heavily used in image compression algorithms and higher-level design of 8-bit games like Mario.

   Eventually, we believe that QuadTrees can be used for memory management in a big and hierarchical database. It is one of the most crucial places we can use the QuadTree and it can be used to access varied data points and make searching efficient and fast.

   Further work in this project can be to let the user visualize their own QuadTree using their own dataset. Users will have to give a dataset for the input and the visualizer will create a QuadTree based on the given dataset. Additional features could be added here such as the different color and shapes for different data points. Moreover, this project can be implemented as part of bigger projects such as Geolocation, Collision Detection Systems.

3. CONCLUSION

We explored a type of tree data structure named QuadTree, that can be used to represent 2-D spaces. In this process, we learnt how/why they are used in a range of applications from scaling up internet services to handle millions of requests per minute to their ever-present use in geolocation-based services like Maps and how we can build applications/libraries to implement the same in our apps/services. It can be concluded QuadTrees are extremely powerful data structures that are still heavily under-utilized in both the industry and community applications. By the time of completion of this project weve learned to develop scalable and reusable codebases for large projects, understood the fundamentals of API build and interaction and understood function in a time-bound manner and collaborate at scale across various tasks and disciplines.

REFERENCES

[1] An effective way to represent quadtrees, Communications of the ACM, Volume 25, Issue 12, Dec 1982 pp 905910, doi:10.1145/358728.358741.

[2] Q. Cai and Y. Zhou, A quadtree-based hierarchical clustering method for visualizing large point dataset, 2016 Sixth International Conference on Information Science and Technology (ICIST), 2016, pp. 372-375, DOI: 10.1109/ICIST.2016.7483441.

[3] Optimal quadtree construction algorithms Computer Vision, Graphics, and Image Processing, Volume 37, Issue 3, March 1987, pp 402419, doi:10.1016/0734-189X(87)90045-4

[4] Sullivan, Gary J., and Richard L. Baker. "Efficient quadtree coding of images and video." IEEE Transactions on image processing 3, no. 3 (1994): 327-331

[5] Berg, Mark de, Marcel Roeloffzen, and Bettina Speckmann. "Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes." In European Symposium on Algorithms, pp. 383-394. Springer, Berlin, Heidelberg, 2012.

[6] Sharma, Praveen K., and Harish N. Dixit. "Energetics of a bouncing drop: Coefficient of restitution, bubble entrapment, and escape." Physics of Fluids 32, no. 11 (2020): 112107.

[7] Mathew, Reji, and David S. Taubman. "Quad-tree motion modeling with leaf merging." IEEE Transactions on Circuits and Systems for Video Technology 20, no. 10 (2010): 1331-1345.

[8] Tilkov, Stefan, and Steve Vinoski. "Node. js: Using JavaScript to build high-performance network programs." IEEE Internet Computing 14, no. 6 (2010): 80-83.

[9] Fenton, Steve, Fenton, and Spearing. Pro TypeScript. Apress, 2014 [10] Cantelon, Mike, Marc Harter, T. J. Holowaychuk, and Nathan Rajlich.

Node. js in action. Greenwich: Manning, 2014.

[11] Wieruch, Robin. The road to react: Your journey to master plain yet pragmatic react. js. Robin Wieruch, 2017.

[12] Thakkar, Mohit. "Next. js." In Building React Apps with Server-Side Rendering, pp. 93-137. Apress, Berkeley, CA, 2022