Shortest-Path Route Extraction From City Map

Project Plan and Milestones

Our final goal is to create a simple Google-Maps-style navigation tool for the past. The user will be able to select two points, and see the shortest path between these two points. This would be a useful for someone to estimate how they would navigate through a city - possibly hundreds of years ago. Florian has been tasked with pre-processing the historical map. This involves searching for the best maps and cleaning them. Cleaning is crucial to ensure that an accurate graph is extracted from the map. Jonathan is working on representing the graph visually, creating interactivity, and hosting it on a website.

Note that, by design, this section is a snapshot of the project planning at an intermediary stage (as of November 14), and therefore might not accurately reflect all steps taken at later stages.

Already Completed

• Researched software that will help us with graph extraction

• Took the first steps to developing a cleaning process for each map

• Written Python code to display a graph from a text list of nodes and edges

• Completed simple routing between two nodes

• Setup a website and domain (www.dhproject.cf) to showcase our project

Future Goals

• Take a decision on which overall direction to pursue for the remainder of the project: Generality, by including several other maps? Or adding functionality for routing based on address input, to more closely mimic the interface of services like Google Maps? (November 23)

• Letting a user select two nodes on the map, and displaying the shortest path between the two nodes. (November 23)

• Displaying the interactive graph on the website. (November 23)

• Calculating and displaying the actual estimated distance between the two points. (end of November)

• Overlay the graph representation onto the historical map. (end of November)

• Develop a manual process for assessing how accurate graph extraction is, and correcting if necessary. (end of November)

• Some buffer time, to allow for unforeseen work. (December 1 to 9)

• Finish Wiki writing (December 12)

• Refine (and automate) the cleaning process. This may involve researching other maps and choosing the best ones for our needs. (no hard time frame, depending on feasibility and necessity)

• Possibly move the network extraction, which is currently done via GUI, to a script. (no hard time frame, depending on feasibility and necessity)

• (Stretch goal) Allow a user to upload their own map which will be processed and displayed.