Screen Shot 2019-08-29 at 12.07_edited.p

Background

Bear maps was the last project that my partner and I were assigned during Data Structures and Algorithms over summer 2019. We were given the front-end of this software and required to program back-end features. For the grade we were only required to program rastering and shortest path finder. We furthered the project by implementing Autocomplete and Turn-by-Turn navigation. To try out the application click the image above.

Results

Rastering

Rastering was completed using a for-loop and some arithmetic. We were only given the amount of images to create up to seven levels of zoom. Using the inputs from the front end we were able to calculate the depth that the user required. With the depth calculated, the program picks the picture to display at the user that is the correct zoom and correct location from the entire map layer (which made up of 4^D images D being the depth of zoom). This process runs in O(k), k being the number of 255 images thats needed to cover the users window with the correct images.

Shortest Path

We completed the shortest path by completed by starting with a 2-dimensional k-d tree, to determine where the start and end points are located in the map graph. Once the end points are located, we used A* algorithm to find the shortest path and send it back to the front end. The heuristic chosen for this A* algorithm the distance left to reach the destination.

Autocomplete

Autocomplete was implemented using a trie. Once two characters are given, the trie finds all the names in the graph that start with the given prefix. Once the user clicks the location a red marker will be placed on the given location. If multiple locations with the same name exist, multiple markers are placed.

Turn by Turn Navigation

Using some of the given methods, I was able to determine the angle of the nodes were significant enough to be a change in direction. Until it was time to change the direction I added the distances between nodes. Both the directions and the distances were all stored in a linked list which was sent over to the front-end.

Improvements

One of the major flaws in this software is that it doesn't one recognize one-way streets. This happens because we worked with an undirected graph. If I was going to make a second version of this, I would create a directed graph. Unfortunately xml file that we worked with didn't have enough information to create a directed graph.

Steven