The usual Navigation System tries to get the shortest or the fastest path from one point to another. However, in some cases, having the ability to further customize the path is desirable. Such a case could arise if, while working out, following a path that maximizes or minimizes the elevation gain is more convenient than the usual shortest path in order to get better training results. Therefore, the EleNa project tries to find the best path between two points according to the user preferences regarding elevation gain and some distance constraint with respect to the shortest path.
Simply clone the following repository to your local machine:
git clone https://github.com/clankster99/CS520.git
You need to have installed python 2.7. Also, the OSMnx library is needed:
pip install osmnx
If you are using Anaconda, then you may use the following command:
conda install -c conda-forge osmnx
Once the repository is cloned, simply go to the directory's repository and run
python Main.py --strategy STRATEGY_VALUE
The screen will show what to do next. It will ask for the following :
- Origin's Latitude and Longitude
- Destination's Latitude and Longitude
- The percentage of distance, the user is willing to travel extra over shortest path length
- User is trying to 'maximize' or 'minimize' the elevation.
We have implemented three different algorithms to solve the above problem. Please input the STRATEGY_VALUE [default is 1] to 1 / 2 / 3 in the main.py to try our algorithms.
1 is an approximation algorithm which is the fastes and only minimizes 2 is an exact algorithm which both maximize and minimize 3 is another try at an exact algorithms [almost exact] which both maximizes and minimizes
The output would the program would be a graph figure showing the route between origin and destination.
Once the repository is cloned, simply go to the directory's repository and run
python Test.py
The Test program will take extra percent travel data and number of destinations for testing as input. It would generate graphs comparing total length and elevation of routes by using different strategies.
Modified_Dijsktra_SP_LE.png compares Strategy 1 for distance with Shortest Path and Least Elevation DFS_1_max_elevation_SP_LE.png compares Strategy 2 for distance with Shortest Path and Least Elevation DFS_1_min_elevation_SP_LE.png compares Strategy 2 for distance with Shortest Path and Least Elevation DFS_2_max_elevation_SP_LE.png compares Strategy 3 for distance with Shortest Path and Least Elevation DFS_2_min_elevation_SP_LE.png compares Strategy 3 for distance with Shortest Path and Least Elevation
Elev_Modified_Dijsktra_SP_LE.png compares Strategy 1 for elevation with Shortest Path and Least Elevation Elev_DFS_1_max_elevation_SP_LE.png compares Strategy 2 for elevation with Shortest Path and Least Elevation Elev_DFS_1_min_elevation_SP_LE.png compares Strategy 2 for elevation with Shortest Path and Least Elevation Elev_DFS_2_max_elevation_SP_LE.png compares Strategy 3 for elevation with Shortest Path and Least Elevation Elev_DFS_2_min_elevation_SP_LE.png compares Strategy 3 for elevation with Shortest Path and Least Elevation
- OSMnx - API used
We use Git for versioning.
See also the list of contributors who participated in this project.