I enjoy graph theory and the algorithms behind it and wanted to see if I could run Dijkstra's algorithm on road data.

How it works

This project uses data from Open Street map to allow the user to find where they can get from their location in a certain amount of time. The data is pulled from Open Street Map, stored in Clusterpoint as a graph, and then will use Dijskatra's algorithm to traverse the data. It calculates how long each individual road will take to travel and continues in all directions until it reaches how long the user is willing to drive. It then takes these points and draws a concave hull around them to display to the user the area they can cover in that amount of time.

Challenges I ran into

Dealing with a large amount of data was a challenge for me. I had to write a separate pre-processing program to parse and store the data as needed. At this time, I only provide a limited region of data for this app since I couldn't fully get everything working with lots of data but I hope, in the future, to expand the region of data provided.

Accomplishments that I'm proud of

I enjoyed making this application run efficiently. I wasn't sure if Dijkstra could run on this large set of data in a reasonable amount of time, but with a few optimizations and tweaks in the base algorithm, it runs in a very reasonable amount of time.

What I learned

The project taught me about perseverance. I ran into many problems (like all programmers do!) with bugs and loading large files and hacking together multiple languages and libraries into one project. Its nice to finally be able to use it all in one application.

What's next for Where Can I Go?

I want to add the ability to display locations on the side of restaurants or entertainment or gas stations that exist within the shaded polygon regions. This allows the user to say "I want to see a movie but I only want to drive no more than 15 minutes for it". The application will traverse the road data and give them all the theaters within that region.

Built With

Share this project: