Mapping Service

Software Design Class Project

Project Overview

I worked in a team of 3 students to create a navigational mapping service for tourists using C++. We used the OpenStreetMap API to retrieve information about major cities including Toronto, Beijing, Singapore, New York, and London.

My Contributions

I was responsible for a lot of the visual elements of the map including the colour scheme and the icons. I coded a gridding algorithm to improve the visual responsiveness of our map by over 600%. We also collaborated on path-finding algorithms such as Dijkstra's and A*.

Visual Components

I drew all the icons for the points of interest (POIs) including restaurants, hotels, education, healthcare, etc. and transferred them to the user interface API we used (EZGL).

The gridding algorithm I implemented improved the frame rate of the map from 3 fps to an average of around 20-25 fps (minimum fps of 15 fps and maximum of 34 fps). Prior to gridding, the map was being completely redrawn every time there was an update from the user (such as moving the camera) which made it very slow. I "cut" the map into several sections according to a grid and whenever the camera was viewing a certain number of grids only those grids would be drawn. I was able to achieve this on multiple "layers" of the map to display more or less information depending on the camera's zoom level.

The Travelling Salesman Problem

Dijkstra's (depth-first search) and A* (breadth-first search) algorithms were able to find the most shortest path between two intersections. Next, we wanted to find the most optimal path between several destinations. The top figure on the left is A* algorithm; show how it's a guided breadth-first search in the direction of the destination. The bottom figure shows Dijkstra's algorithm and how it indiscriminately searches for the fastest path for all surrounding interestions.

Obviously we could spend hours upon hours to find the best path, but to be efficient we needed to find the fastest and most optimal algorithms within a 50 second time limit. To accomplish this, we preloaded all the path travel times with a city-wide search using Dijkstra's.

We started with an initial greedy algorithm to go to the nearest intersection each time. We expanded on that by swapping intersection orders using 2-Opt and Random Node insertion. More information about the algorithms are in our full presentation (link at bottom of page)!