Large scale GIS Mapping system project created using C++ and OpenStreetMap at the University of Toronto.
The source code for the project cannot be made public due to Academic Offense policies at the University of Toronto. This Repository only contains a demo of the Mapper Project that I created along with teammates Srinidhi Shankar and Prarthona Paul.
- C++
- GTK (GUI development)
- Extensively used Structs to create various objects for elements like features, points of interest and path tracing data.
- Created separate header files to split milestone global variables.
- Abstraction was implemented with functions that were used for streets, features, and pathfinding.
STL structures used:
- Vector
- List
- Unordered Map
- Priority Queue
- Multi Map
Dynamically allocated arrays were used for optimization purposes.
The project was split into four milestones:
- Data loading
- GUI implementation
- Path Finding Algorithms - A star and Dijkstra's
- The Travelling Salesman Problem
The team kept track of various tasks during these milestones through a wiki page and a Trello workflow.
My contribution to the project over the semester (14 weeks):
The project used the OpenStreetMap database to parse geographic data. The course team converted XML files to binary files for efficient data accessing. Data was processed using various keywords and structures based on OSM standards.
Reference: https://wiki.openstreetmap.org/wiki/Main_Page
The map was created with climate impact in mind. The team hopes to expand route finding to subways and buses in order to promote greener traveling. Transit paths will be given precedence and greener roadways will be highlighted when presenting paths to users. A carbon footprint approximate will be calculated and displayed to the user. Additionally, the map includes various Points Of Interest that promote greener methods of travel:
- Bicycle Rentals
- Electric Vehicle Charging
- Recycling Bins
Various data loading functions were created to load important OSM information into data structures. Functions were evaluated based on O complexity analysis
Users can choose to see transit options in a city by clicking on the transit button. The paths were laid out using the OSM database keys for subways and buses, giving accurate paths.
Maps are loaded in a function through OSM XML map files converted into binary files. Users can change maps and explore different cities around the world. Some maps included are:
- Toronto
- New York
- Sydney
- Singapore
- New Delhi
- Hong Kong
- Tokyo
When searching for POIs, users can select what POIs they want to see from a drop-down menu. All categorized POIs in the users' search area will appear and as the user zooms out, those are the ones that remain. This was a design decision made to keep POI querying fast and intuitive. If POIs are not present on the user's screen, the nearest POIs are displayed as the user looks around.
The search bar was created using the GTK search bar widget. It supports partial street name inputs and gives suggestions and autocompletes. Users can query partial street names and press enter, the search will consider all possible streets and find common intersections.
A dark mode feature allows eye comfort based on brightness.
The map turns green when in navigation mode. A navigation bar provides important information about the selected from and to, and has an additional feature to swap the two immediately. Detailed directions are presented in a text box on the right, and the path is highlighted as the user goes through the directions.
A help page was created using HTML/CSS to give users instructions on how to use the map.
[Git Repo] (https://github.com/PrarthonaPaul/Mapper_Instructions)
Three algorithms were used to achieve navigation on the map. Breadth-First Search was implemented as an initial solution and then iterated upon.
- Dijkstra's Algorithm
Dijkstra's algorithm was implemented using a min-heap (priority queue). The following video demonstrates Dijkstra's algorithm working on our map. The highlights are just a visualization tool to see the algorithm working (the actual finding is much quicker than that demonstrated through the highlights). Dijkstra's algorithm uses wavefronts to explore all paths until it finds the best one to the destination. These wavefronts are circular and expand outwards from the source.
- A Star Algorithm
A Star algorithm was implemented by making slight adjustments to Dijkstra's by including a new dimension of estimation - time remaining. The algorithm was significantly faster for single-source single destination searches. The visualization shows how the algorithm moves in a more focused direction rather than a circular wavefront.
The final milestone of the project was related to coding an acceptable solution to the Travelling Salesman Problem using various heuristics. For background, the Travelling Salesman Problem is an NP-complete problem relating to finding the shortest path for given pick-ups and deliveries. Dijkstra's algorithm was expanded to find paths to multiple destinations from a source, all at once. Multi-Destination Dijkstra's, coupled with a greedy algorithm gave an initial solution.
In order to improve our result path, we iterated through multiple pickup points and implemented a simple multi-start. Additionally, we implemented local perturbations through 2-opt, which improved our results by testing various different swaps between path links. This perturbation operation was used in our Simulated Annealing algorithm.
Simulated Annealing Result from our TSP solution implementation:
The graph represents how our TSP solution utilized simulated annealing for two different start points. The y axis is the total path time and the x axis is a new iteration for a path.
Demonstration of a greedy algorithm that takes the nearest neighbor:
For more information on the Travelling Salesman Problem (src): https://en.wikipedia.org/wiki/Travelling_salesman_problem