GIS Mapper
A semester-long project focused on building mapping software for place searching and navigation using C++. It combines geographic data visualization, pathfinding algorithms, and delivery constraints to simulate real-world logistics optimization.
(Due to school regulations, it is not permitted to share the code on GitHub.)
Tech Stack: C++, EZGL, libCurl, STL library.
Implemented by: Kaeul Lee, Alex Hu.
Overall Functions
The software is designed to provide a user-friendly interface for searching and navigating maps. It offers the following key functions:
- Geographical Display: Retrieves data from the libStreetMap API and uses EZGL graphics to render it on a canvas.
- Point Query: Allows users to click on a point to display its related information, or input information to locate a point.
- Points of Interest (POI): Enables users to display all POIs in a city using the provided UI buttons—such as restaurants or clinics.
- Two-Point Navigation: Input two points and the software calculates and displays the optimal path on the map.
- Navigation Directions: Processes the data from two-point navigation and generates a list of directions for real-world navigation.
- Solving TSP Problem: Solves a given Traveling Salesman Problem (TSP) using specialized algorithms based on the collected data.
Map Graphics
The map graphics are created using EZGL, a C++ graphics library that provides functions to draw shapes, text, and images on a canvas. The map data is obtained from the libStreetMap API, and at different zoom levels, the software displays varying levels of detail.
Graphic examples: different zoom levels display varying details.
Interactions on the Map
The map is designed to be interactive, allowing users to click on points to retrieve information or navigate the map. The software handles text input through a UI form; users can enter either navigation points or specific intersection names. Additionally, clicking on the map provides details about the selected point.
Example: Given start and end points, the software displays a graphic route with detailed directions.
Button Interactions
Buttons on the right allow users to select POIs, toggle light mode, and switch cities.
Features in dark mode.
When "Cafes" is selected, all the cafes in the city are displayed on the map.
Switch city: this instance shows Beijing, China.
Algorithms: Dijkstra
The software implements Dijkstra's algorithm to find the shortest path between two points. It uses a priority queue to efficiently select the next point to explore and updates the distances of neighboring points dynamically. This algorithm is designed to handle large maps efficiently, making it suitable for real-world applications.
By planning an efficient data structure in the loadMap function and utilizing the STL library wisely, the software finds the shortest path between two points in a very short time—even on a map with over 10,000 points, such as in New York City or Tokyo. Typically, it takes less than 0.1 seconds to determine the path. All test cases for two-point navigation are passed, as shown below.
All test cases passed for Dijkstra's algorithm.
Algorithm: Traveling Salesman Problem
The software also implements a solution for a modified Traveling Salesman Problem, called the Traveling Delivery Problem (TDP), using a mixed approach. It first opened 64 threads (on an 8-core computer) to run different greedy algorithms that calculate feasible paths between all points.
Then, based on the 64 results, it performs simulated annealing to find a globally optimized solution. Finally, depending on the remaining time, the software runs 2-opt or 3-opt to further optimize the path locally.
Take London as an example: if there are approximately 260 delivery points (130 × 2) in the city (with some overlaps), the optimized time will be around 37 hours (133214 seconds). It may seem like a huge number, but considering the density of points in such a city, it is extremely fast!
An extreme TDP case: 260 points in London.
What's Next
Currently, the software serves as a proof of concept for map navigation and delivery optimization. In the future, we plan to enhance the software with the following features:
- Add AI suggestions based on the navigation path and real-time information (e.g., weather conditions).
- Fetch real-time traffic data for each city and display it within the graphics.
- Add a voice broadcast function.
- Rebuild the system using JavaScript and deploy it!