This project utilizes open street maps (OSM) to build a geographic information system of different cities across the world. The GIS maps roads, buildings, geographical features, and any particular points of interest ie. restaurants, gas stations.
Note: The source code is not shared to maintain the academic integretity behind the course
Developed in C++ for front and backend. Utilized EZGL library for graphics.
A* calculates the best route for driving (default route mode), Multi-Start/Destination A* is used for the uber pool feature. This feature allows the user to specify how far they are willing to walk to get picked up with a driver.
The uber pool algorithm utilizes multi-destination A* to find all intersections within a range the user specifies (red) which multi-start A* finds all possible routes from those intersections to the final destination (blue).
Joining the two routes together forms the best path with the walking portion highlighted in red and the driving route in blue.
The algorithms have been tested against thousands of scenarios for legality, performance (time complexity) and the optimality (how well is the calculated path compared to the known best path). The results for the test cases are below.
R Trees were utilized to spatially organize geographical data to improve responsiveness and reduce FPS lag. Utilizing R Trees enables specific filtering of data to only display and access points that belong on the user's visible screen.
The GIF on the left illusrates the GIS before the R Tree implementation and on the right is After
The improvements range from 100x to 10000x faster depending on how zoomed in the map is, with a higher zoom yielding a larger filter resulting more noticable improvement.
- Uber Pool Mode
- Dark Mode
- Building Toggles
- Full mouse control
- Scalable code to display any city
- Search menu for intersections
The user can specify how far/long they are willing to walk and the GIS will find the most optimal destination for pickup.
Any city can be loaded provided the osm.bin file is installed
