Quadtree Simplified

Imagine a case where you have 10000 random points in a two-dimensional space, and you need to write a program that detects points in a given rectangular area.

 

Let’s visualize this for a better understanding of the problem.

 

 image02

 

We need to identify all the dots in the region marked in blue. Well, the first thing that runs to your mind will be to iterate through all the points and check if they lie within the blue region—something like the algorithm below.

 

For (Iterate all points){

           //Check if points lie in the marked region.

           If (Yes){

                      Add the point in array, A1.

           }

}

Return array A1

 

But if you have millions of scattered points, it may not be a good solution to iterate through all the points and check if they lie within the blue region.

 

Let’s consider another example.

You have to prepare a report of all students in class 10 who got 75% or more in the last monthly test.

 

You can ask the teacher handling class 10 for the list of students who scored 75% or above in the monthly test. Yay, you have the list. Simple! Well, you didn’t ask each student in the school if he was studying in class 10 and if he had scored more than 75% in the test.

 

Here, we applied the famous ‘Divide and Conquer’ technique. The same can be applied to the problem mentioned above.

 

But how?

 

Quadtree gives you the solution.

 

A quadtree is a tree data structure in which each internal node has exactly X children {where X can be one, two, three, four or any positive integer greater than zero}. A quadtree algorithm recursively subdivides cells into equal-sized sub-cells such that each cell has exactly X or lesser number of points.

 

If a quadtree takes 10 as the value of X, it means that each cell has 10 points. When a cell has more than 10 points, it will subdivide itself into equal halves, and this will recursively go on till all sub-cells have 10 or less than 10 points.

 

Let’s take the example of a school once again to understand this better.

 

Imagine each classroom in a school has 25 chairs and tables. This means that each room can seat a maximum of 25 students. So to occupy 120 students in class 10, the school will need 5 rooms and each room will have 25 students or less.

 

image00
 

The same thing happens in quadtree. It recursively divides cells until each cell has exactly X number or less points in it.

 

Coming back to our original problem, we can apply the quadtree algorithm to 10000 points.

 

Now, the selection algorithm will be:

 

// Here each cell has 10 points

For (Iterate all cells){

           //Check if cell lies in the marked region.

           If (Yes){

                      Add the point in array,A1.

           }

}

For (Iterate all points in array A1){

           //Check if point lies in the marked region.

           If (Yes){

                      Add the point in array, A2.

           }

}

return A2

 

In this way, you can ‘Divide and Conquer’ this problem!