Spring semester of 2017, I took UMD's infamous data structures course: CMSC420. The reason this course is so famous in the computer science department is because of the challenging, semester-long project known as MeeshQuest. For this project, students are supposed to work independently to implement a stripped down version of MapQuest. The end result is supposed to be an application capable of efficiently computing the shortest distance between two points and returning the directions to take, through certain roads or airports.

This project exposed me to quadtrees (of the PM and PR varieties), which were essential to the overall efficiency of the application. A quadtree is a 4-ary tree used to divide a 2D region into more manageable parts. Quadtrees are often used in video games such as Crash Bandicoot, for their blazing fast collision detection.

In a similar vein, we utilized quadtrees to quickly compute the shortest distance between two cities and generate optimal directions. Imagine if we have 100 cities stored in our application. If we decide to compare every city to find the nearest neighbor to City A, then that would require 10,000 operations - that's a lot of checks! One way to speed up this brute force is to avoid searching for cities that are on completely opposite ends of the map from City A. This is where quadtrees come into play.

Let's imagine our quadtrees as a representation of a spatial map, where each node represents a region. If we insert a city, then that point will occupy a region within the map. Once we insert a second city, then the key space will be recursively divided into 4 regions until the two cities no long occupy the same quadrant (**By the definition of PR Quadtrees).

As you can see above, each node contains a few objects. We know then that, for instance, the objects in the top-left node cannot be close to objects in the bottom-right node, which leads us to derive very efficient algorithms for shortest distance, and other geographic queries.

Overall, this was one of the most challenging projects in my undergraduate career and definitely made me a stronger developer. The above is a screenshot of various submission trials for the project, where red bars denote failing tests and green bars denote passing tests. This project made me a stronger debugger as well. Some notable debugging skills I refined were rubber ducking and becoming proficient with the eclipse debugger, which was invaluable while tracing through multiple recursive calls on the call stack to find a bug.

Some notable data structures I implemented from scratch for this project include:

  • AVL-g Tree (a variation of the AVL tree)
      Used to represent a data dictionary
  • Point Region (PR) Quadtree
       Used to represent metropoles (clusters of cities)
  • Polygonal Map (PM) Quadtree
       Used to store cities, airports, and roads

View project wiki