Maps represent the world we live in. They are central in many computer applications. The goal of this project is to create a map-based application including some of the underlying data structures and algorithms.

As we all know, the numbering of the houses in Ryd can be quite confusing. It has been rumored that there is a research report stating that there is no simple set of rules that describe the numbering. To help you find your way to your friends you need a map application that shows the shortest path between your house and your friends houses. Since you want to become an expert programmer you decide to write your own application to learn more about the data structures, algorithms, and techniques involved in map applications.

In the introductory phase of the project you will develop a basic web-based map application which you will then improve on in the main phase of the project by adding functionality for finding and displaying shortest paths between locations on the map. Finally, we offer several suggestions on how to improve your map application even further.

Maps have always played a central role in human society. According to Wikipedia, a map is "a visual representation of an area -- a symbolic depiction highlighting relationships between elements of that space such as objects, regions, and themes."

Computerized maps have gained popularity especially with the introduction of smart phones with GPS receivers. Equipped with a GPS receiver you know the coordinates of your current location, i.e. you know where you are (roughly, depending on the accuracy of the receiver). To make those coordinates much more useful, you also need to know where those coordinates are in the world. In other words, you need a map. With a map displaying your location, according to the GPS, you can do many things such as finding your way to your friend somewhere in Ryd and find the closest pizza place.

There are many popular map-based applications:

• Navigation aids for smart phones and cars.
• Data visualization aids to explore and interact with data such as corruption, crimes and natural resources.
• Use crowd sourcing to monitor elections and support disaster relief, such as Crowdmap by Ushahidi.
• Recreational applications such as Geocaching, FourSquares, and MapMyRun.
• For more examples, see googlemapsmania.blogspot.se.

Below is an overview of the map application that you are going to produce. It is showing how the information is flowing in the project (when you are browsing the web-page) and what third party resources that you are going to use e.g. the Google Maps API.

It is okay to not understand it at first glance. The purpose of this chapter is to make it easier to understand how the project is going to be organized. You can look at this chapter again when you fell unsure of how to structure your code.

Almost everything you are going to code is on the server side. The application is divided in three parts.

• Map Application: The core of the application, coordinates the work using the Map Op API and the Map Vis API based on POSTed information.
• Map Operations API: Provides a set of operations on maps, such as computing the shortest path.
• Map Visualization API: Provides functionality to visualize map information, such as a shortest path.

Below an example file structure is shown. It is only an example, you may organize your files differently. Don't worry about what these files are, because you are going to create them yourself in part 3. As said before, it is useful to look back to this chapter when you need an overview of the application and when you feel uncertain about where to put your code.

The goal of the introductory phase is to create a web application using the Django framework, display a map using the Google Maps API and to explore map data from the Open Street Map project.

This part of the project is structured around the following four milestones that each consists of a series of exercises. Each exercise has a number of tasks that should be completed.

1. Create a web application with Django
2. Display a map in your web application using the Google Maps API
3. Explore Open Street Map data
4. Display Open Street Map data on the map in your web application

When you have completed the last milestone you will have a web application that displays data from Open Street Map on a map using the Google Maps API.

Creating a Web Application with Django

The goal of this milestone is to create a basic web application using the Django framework. Django is a Python framework for creating websites. It is very easy to get started with and provides all the functionality needed for this project.

Create a Django Project

To get started you need to create a Django project. This is done with the help of the django-admin.py program. A Django project is a Python package, i.e. a directory containing the code and the settings for an instance of Django. This includes database configurations, Django-specific options and application-specific settings.

Installing Django

If you are using IDA's Linux Mint system, use the following steps to install Django:

• Create a virtual environment: virtualenv -p python3.4 ~/python3_django, (you only need to do this once)
• Activate your virtual environment: source ~/python3_django/bin/activate, and
• Install Django: pip install django==1.10.6 (you only need to do this once).

If you would like some more information on using virtual environments for Python development you can start here.

If you are using your own UNIX (Linux, Mac) system then you can install Django 1.10.x by using a similar process as above. If you are a Windows user you have to find out how to set up Django yourself. Check how to install it here.

Create the lmap project

Explore project files

Start a web server

To test your application you need to start a web server. Django comes with a development server which you can use. Change into the outer lmap directory, if you haven't already, and run the command python3 manage.py runserver 0.0.0.0:80XY, where X is your group number (1-6) and Y is a number that each group assigns to each student in their group (0-9). The command starts the development web server and informs you about potential problems and the URL of the server. To get the URL, find the line "Development server is running at URL".

Check that your web server is working by opening the URL in your browser.

Set up a SQLite database

To store information your application needs a database. SQLite is a simple database which is stored in a single file in the file system.

Update database configuration

To configure Django to use an SQLite database open the file lmap/settings.py, find the variable DATABASES, assign the variable 'ENGINE' the value 'django.db.backends.sqlite3', and change the value of 'NAME' (removing '') to
os.path.abspath(os.path.join(os.path.dirname( __file__ ), '..', 'lmap.sqlite3').replace( '\\', '/' ))

Read about the database configuration

Read more about the database options at docs.djangoproject.com.

Create the database and initial tables

Your Django project is by default configured to use several database tables. These must be created in the database before they can be used. To do this, execute the command python3 manage.py migrate.

If you want to use Django's built in admin page you will need to create a super user. Type python3 manage.py createsuperuser in the terminal and fill in the prompts.

Create a Django app

A Django app is a Python package, somewhere in your Python path, that follows a certain convention. Django comes with a utility that automatically generates the basic directory structure of an app, so you can focus on writing code rather than creating directories. An app is a reusable Django component that can be used in multiple projects.

Projects vs. Apps

Read about the differences between a project and an app at docs.djangoproject.com.

Create the mapvis app

Change directories to the lmap directory so that you are in the directory with manage.py. To create the mapvis app, execute the command python3 manage.py startapp mapvis. You are free so use something other than mapvis, but please be aware that all mapvis references on this page is to the Django app.

Explore app files

Explore the file structure created by Django and read about the files here.

Make your app generate a web page

The next step towards a web application is to generate your first web page. In Django, and in other frameworks based on the Model View Controller design pattern, this is done through a view. To make a page available to a user it has to be associated with a URL. From a Django programming perspective, the content of a page is produced by a view function and a URL is specified in a URLconf.

Read about views and associating URLs to views here.

Create a view displaying a message

In the mapvis app directory, there is a file views.py. This is were you should place your view functions. Enter the code below to create a view function that generates a page with the classical message "Hello world".

from django.http import HttpResponse

def hello(request):
    return HttpResponse("Hello world")

Read about what this code does here.

Connect a URL to your view

Let us continue by associating a URL with the view function so that you can view the result in your web browser. To do this you have to edit the file lmap/urls.py. When you created the lmap project a default files was created. The important part of that file is the variable urlpatterns. If you inspect the file, you will see several examples of how to associate URLs with views.

To associate the view you created in the previous task with the relative URL "hello" you need to do two things:

1. Import the view function by adding from mapvis.views import hello after the existing import statement.
2. Create a URL pattern by adding the line url('^hello/$', hello), after the admin section.

The file will then look something like this:

"""lmap URL Configuration

The `urlpatterns` list routes URLs to views. For more information please see:
    https://docs.djangoproject.com/en/1.10/topics/http/urls/
Examples:
Function views
    1. Add an import:  from my_app import views
    2. Add a URL to urlpatterns:  url(r'^$', views.home, name='home')
Class-based views
    1. Add an import:  from other_app.views import Home
    2. Add a URL to urlpatterns:  url(r'^$', Home.as_view(), name='home')
Including another URLconf
    1. Import the include() function: from django.conf.urls import url, include
    2. Add a URL to urlpatterns:  url(r'^blog/', include('blog.urls'))
"""


from django.conf.urls import url
from django.contrib import admin
from mapvis.views import hello

urlpatterns = [
    url(r'^admin/', admin.site.urls),
    url(r'^hello/$', hello),	
]

Now you can start the development web server and open the page URL/hello in your web browser. Congratulations, you have now generated a web page using Python!

Again, make sure you understand what the above code does. If you don't, read here.

Create a view that generates a page showing the current time

It is important to emphasize that the view function you just created is a plain Python function which generates a string, which is interpreted as an HTML page by your browser.

The hello view you created returns a static string. Let us make it a bit more interesting by including the current date and time. This means that every time your reload the page a new string is generated (unless you reload it faster than the resolution of the clock, but then you have to be pretty darn fast).

To achieve this you need to import datetime, get the current date and time with the function datetime.datetime.now() and then generate an HTML page in the form of a string. Why not try doing this on your own?

When you are done your code should look something like this:

from django.http import HttpResponse
import datetime

def hello(request):
    now = datetime.datetime.now()
    html = "<html><body>Hello world! It is now %s.</body></html>" % now
    return HttpResponse(html)

Note: If you are wondering why the application are showing the wrong time, it is probably because you haven't set up the right timezone. How to fix that you have to find out yourself, it is a good exercise.

If you still have a hard time understanding what the code snippets above do. Take some time and read through the whole Views and URLconfs from django book.

Play around with your view

If you know some HTML this would be a good time to play around with the view function and elaborate the page generated. For example, make the current time bold. You can also use your Python skills to for example display only the current time or format the date a bit nicer.

A good HTML tutorial is available here.

Generate a web page using a template

In the previous exercise you created a web page by hard coding the content. A much better approach is to use the Django template facility. It allows you to combine hard coded and generated HTML/CSS/JavaScript in more user friendly manner than creating a very long string by concatenating smaller strings.

You can read more about Django's templates here.

Create a directory for your templates

You need somewhere to store your templates. The convention is to create a directory called templates in the project directory and in it a sub directory for each application with the same name as the application.

Create a directory templates in the project directory and a directory mapvis in that directory.

Update the project configuration to find your templates

Now that you have a directory for templates you need to configure your project to find those templates. This is done by editing the file lmap/settings.py.

Find the variable TEMPLATE_DIRS in the file lmap/settings.py and add the absolute path to newly created templates directory. If you have followed the instructions, you should add os.path.abspath(os.path.join(os.path.dirname( __file__ ), '..', 'templates')).replace( '\\', '/' ), to the list TEMPLATE_DIRS.

Create a view rendering a page from the template

A template is basically a text file where some parts are interpreted as variables and macros which are expanded to generate several different instances of the text. To generate an instance of a template instantiate it with a context which is basically a Python dictionary.

Create a view called mapapp in the file views.py with the following code. The code creates a context associating the key NOW with the current date and time, instantiates the template map/mapapp.html and returns it as a response to an HTTP request.

from django.shortcuts import render_to_response
from django.template import Template, Context

def mapapp(request):
    now = datetime.datetime.now()
    c = Context({'NOW': now})
    return render_to_response('mapvis/mapapp.html', c)	

You also need to associate a URL with the view, this is done by adding ('^mapapp/$', mapapp), to urlpatterns in the file lmap/urls.py.

Create a page template

The template itself is a text file mapapp.html in the directory templates/mapvis.

To create a page with the same content as the hello view use the following template:

from django.shortcuts import render_to_response
from django.template import Template, Context

class Member:
    def __init__(self, name, age):
        self.name = name
        self.age = age

def memb_reg(request):
    members = dict()
    members[2] = Member("Kurt", 64)
    members[5] = Member("Anne", 39)
    members[3] = Member("Berit", 15)
    members[8] = Member("Julius_Caesar", 2113)

    c = Context({
                    'NUMBER_OF_MEMBERS': len(members),
                    'MEMBER_INFO': members,  # Important, note the last ","!
                })

    return render_to_response('bobbin_lace/memb_reg.html', c)

<html>
<head>
	<title>Member register</title>
</head>
<body>
	<h1>Member register of the bobbin lace association</h1>
	There are {{MEMBER_INFO|length}} members in the association.<br>

	<h2>List of all members:</h2>
	<ul>
		{% for id, member in MEMBER_INFO.items %}
    		<li>{{member.name}}</li>
		{% endfor %}
	</ul>

	<h2>Members that are older than 50 years</h2>
	<ul>
		{% for id, member in MEMBER_INFO.items %}
    		{% if member.age > 50 %}
    			<li>{{member.name}}, {{member.age}} year(s) old.</li>
			{% endif %}
		{% endfor %}
	</ul>
</body>
</html>

What happens if you open the site root?

Open the site root. What happens? Why?

Associate the mapapp view with the site root

Now you should know enough to be able to create a URL pattern that associates the mapapp view with the site root. If you need advice, read Django book ch 2.

Play around with views and templates

To learn more about views and templates we suggest that you play around with them for a while. Try to create something impressive and show it to the other groups.

Displaying a Map with the Google Maps API

Learn more about Google Maps

Learn more about the Google Maps JavaScript API

Get your own Google Maps API Key

Display a map

Import Google Maps JavaScript code

<!DOCTYPE html>
<html>
    <head>
        <meta name="viewport"content="initial-scale=1.0, user-scalable=no"/>
        <style type="text/css">
            html { height: 100% }
            body { height: 100%; margin: 0; padding: 0 }
            #map_canvas { height: 80%; width: 80% }
        </style>
        <script type="text/javascript"
            src="http://maps.googleapis.com/maps/api/js?key={{ GMAPS_API_KEY }}&sensor=false">
        </script>
        <script type="text/javascript">
            var map;
            function initialize() {
                var mapOptions = {
                    center: new google.maps.LatLng(-34.397, 150.644),
                    zoom: 8,
                    mapTypeId: google.maps.MapTypeId.ROADMAP
                };
                map = new google.maps.Map(document.getElementById("map_canvas"), mapOptions);
            }
            google.maps.event.addDomListener(window, 'load', initialize);
        </script>
    </head>
    <body>
        <div id="map_canvas"></div>
    </body>
</html>

To understand what the code above does, take a look at the Google Maps JavaScript API tutorial.

var a = 0;			//Declares a number
var b = 10;
var c = 'hello';		//Declares a string
var d = 10.3;
//Makes an pop-up box show up on-screen displaying the given information.
alert('a: ' + a.toString() + '\n' +
      'b: ' + b.toString() + '\n' +
      'c: ' + c.toString() + '\n' +
      'd: ' + d.toString() + '\n');
console.log("Hello world!");	//Logs "Hello world!" to the JS console.

Create a view that generates the map page

To display the map, you also need to update the mapapp view function by including your Google Maps API key in the Context so that it is included in the generated web page. The complete code for the view function is:

def mapapp(request):
    c = Context({'GMAPS_API_KEY': '+++YOUR_GMAPS_API_KEY+++'})
    return render_to_response('mapvis/mapapp.html', c)

Remember to replace +++YOUR_GMAPS_API_KEY+++ which your actual API key!

The Context object works like a dictionary but with some extensions. Read about Context and Templates in the documentation.

Change the map center

Currently the map is centered on Sydney, Australia. This can be changed. The latitude and longitude of Linköping University is 58.3985303, 15.5745319. To change the center of the map, update the value of the mapOptions property center to center: new google.maps.LatLng(58.3985303, 15.5745319),.

Change the zoom level

When you reload the page you see that the map is centered on Linköping. To zoom in on the university change the zoom level in the template code from 8 to 16.

Change the map type

There are several types of maps that can be displayed. The following map types are available in the Google Maps API:

1. MapTypeId.ROADMAP displays the default road map view,
2. MapTypeId.SATELLITE displays Google Earth satellite images,
3. MapTypeId.HYBRID displays a mixture of normal and satellite views, and
4. MapTypeId.TERRAIN displays a physical map based on terrain information.

Try the different types out! In the end we suggest you use either ROADMAP or HYBRID.

Place a marker with a click on the map

You now have a web application displaying a map. To make it more interesting you will now allow a user to add markers to the map by clicking on it and displaying the latitude and longitude of that location when the mouse is over the marker.

Create a JavaScript function for displaying a marker

To display a marker you need to create a new object of the type google.maps.Marker with a reference to the map, the latitude and longitude of the marker, and the title of the marker. The title is a string that is displayed when the mouse is placed on the marker.

Copy the following helper function into your template after the line
google.maps.event.addDomListener(window, 'load', initialize);:

function createMarker(map, latlng, title) {
    var marker = new google.maps.Marker({
        map: map,
        position: latlng,
        title: title
    });
}

Create a marker on the click of the mouse

To create a marker when the user clicks the mouse on the map you need to associate a function with the event handler for the event click. When a user clicks on the map, a click event is generated which contains the latitude and longitude of the position of the click in the event attribute latLng.

The event handler is the createMarker function you created above.

To create the event handler, copy the following code to the end of the initialize() function you created before:

google.maps.event.addListener(map, 'click', function(event) {
    createMarker(map, event.latLng, "Click: "+event.latLng);
});

Test the functionality by reloading the web page and finding the coordinates of for example Zenit, your current location, and your house.

You now have a basic map application. Pretty nice, right?

Exploring Data from Open Street Map

Open Street Map (OSM) is an open source alternative to Google Maps created by volunteers, where many people, including members of Lysator, have contributed. Open Street Map contains data about for example nodes, roads and buildings. A node is a point which is of interest, usually as part of a road or a building.

The goal for this milestone is to download and explore the data in the Open Street Map project for a suitable area of Linköping.

The Linköping part of the Open Street Map project

Familiarize yourself with the Linköping part of the Open Street Map project

Linköping working group

The URL http://wiki.openstreetmap.org/wiki/WikiProject_Sweden/Linköping is the homepage of the Linköping part of the OSM project. Follow the link and investigate how this group structures their work.

A map of Linköping

The following URL http://www.openstreetmap.org/index.html?lat=58.40&lon=15.61&zoom=12 leads to a visual representation of the OSM data for the Linköping area, i.e. a map! Spend enough time exploring the map to be able to form an informed decision regarding whether the OSM data seems to be of high quality or not. In particular, it might be good to compare this map to the corresponding map area in Google Maps (hint: change the center of the map and the zoom level in your web application to the same values as above and reload your application).

Gathering map data

Download a suitable portion of the OSM data for Linköping.

Fetch OSM data from the web

Use your web browser to go to http://www.openstreetmap.org/index.html?lat=58.40&lon=15.61&zoom=12 and click on "Export" in the menu on top of the page.

Choose an area

Choose minlat="58.3773000", minlon="15.5207000", maxlat="58.4236000",
maxlon="15.6248000", and "OpenStreetMap XML-data".

Export the data

Press "Export". You will now receive a file containing roughly 11 MB of map data around which you will build your map application. Be sure to always keep an untouched version of this file backed-up somewhere and always work on a copy of this file. Note: If the export button wont let you download the data, just use one of the provided mirrors.

A first look at the OSM data

In this exercise you will take a first look at the OSM data.

Actually look at the data

Open the OSM data file you have just downloaded in a text-editor of your choice.

XML

The data is in XML format. XML is a way to present structured data so that is is readable both by humans and machines. Read the Wikipedia page about XML to learn the basics about how this format works.

OSM XML

OSM has its own particular set of XML tags and rules for how to use them. The web page http://wiki.openstreetmap.org/wiki/OSM_XML contains specifications of the basic tags as well as links to their intended usage. Study this page. In particular, it is important that you learn how the data primitives nodes, ways, and relations are used to build the geographical information contained in a map.

Which information does a node contain?

Find out what information a node contains.

Which information does a way contain?

Find out what information a way contains.

Which information does a relation contain?

Find out what information a relation contains.

How do you represent a road using OSM XML data?

Find out how to represent a road using OSM XML data.

How do you represent a building using OSM XML data?

Find out how to represent a building using OSM XML data.

Using Python tools to parse and investigate OSM data

We now want you to start processing the OSM data by executing programs you have written yourself. Parsing the rather extensive OSM XML format is not an easy task. You will therefore use a ready made parser for at least the introductory phase. We recommend that you use OSM py parser. Open the file, chose save as and where you want to save it. Later on this will be referred to as both osm_parser and parser in the text.

The parser uses xml.Etree.ElementTree from the python standard library. With it you can easily iterate over elements in an XML-file. If you are interested in how it works here is a link.

A small example is provided in the task below to help you to understand how the parser is used.

How many nodes does your Linköping map data have?

Find out how many nodes your Linköping map data contains by writing a program that counts them and how much time it takes.

# Parser example
# Usage python parser_ex.py 

import sys
from datetime import datetime

from mapvis.parser import get_default_parser

# The first argument after the python module on the commandline
filename = sys.argv[1]

# Parse the supplied OSM file
start = datetime.now()

parser = get_default_parser(filename)

nodes = 0
for node in parser.iter_nodes():
    nodes += 1

end = datetime.now()

print("The data contains", nodes, "nodes")
print("Parsing the date took", (end - start).total_seconds(), "seconds")

Learn more about the parser

Write Python programs to answer the following questions. To answer these questions you have to look inside the osm_parser.py file

1. How many edges are there in your OSM data

Your own investigations

Try to come up with at least 3 questions of your own about the map data and answer them by using the osm_parser.

An introduction to object orientation (almost)

# This is the class definition
class Term:

    # At this indentation level we define the "methods" of a class
    def __init__(self, value):
        self.value = value

    # Every method of a class needs to have at least 1
    # parameter to it. This is refering to the object itself.
    # It is good style to call this parameter 'self'
    def print_me(self):
        print "My value is:", self.value

    # We can continue to define more methods here
# but once we get to the top level we will not
# define methods for the class anymore
def unused_function():
    print "do nothing"

term1 = Term(4711)
term2 = Term(42)

print term1.value
print term2.value
print "****************"
term1.print_me()
term2.print_me()

class Term:
    
    def __init__(self, value):
        # We call self.value a data member
        # and we can access it either through self.value
        # inside methods of the class...
        self.value = value

    def print_me(self):
        print "My value is:", self.value

term1 = Term(10)
term2 = Term(20)
term1.print_me()
term2.print_me()

# ...or we can access them like object1.value
# from outside the class. This changes
# only term1 and not term2. 
# term1 and term2 are of the same class, but different objects
term1.value = 42
print "****************"
term1.print_me()
term2.print_me()

def add(term_a, term_b): # The function add returns a new Term
    val = term_a.value + term_b.value
    return Term(val)

class Term:
    
    def __init__(self, value):
        self.value = value

    def print_me(self):
        print "My value is:", self.value

    def add(self, other): # The method add modifies an existing term
        self.value += other.value

term1 = Term(10)
term2 = Term(100)
term1.print_me()
term2.print_me()

print "****************"
term3 = add(term1, term2) # 10 + 100 = 110
term2.add(term1) # 100 + 10 = 110
term1.print_me()
term2.print_me()
term3.print_me()

import time

class PrettyPrinter:

    def __init__(self, file):
        self.border_char = "*"
        self.file = file

    def change_border(self, new_char):
        self.border_char = new_char

    def print_message(self, msg):
        # Add a line break manually
        self.file.write(self.border_char * (len(msg) + 4) + "\n")
        self.file.write(self.border_char + " " + msg + 
                        " " + self.border_char + "\n")
        self.file.write(self.border_char * (len(msg) + 4) + "\n")
        
def simulate_work_being_done():
    time.sleep(1)
    
if __name__ == "__main__":
    f = open("myfile.txt", "w")

    printer = PrettyPrinter(f)
    printer.print_message("Doing some work...")
    simulate_work_being_done()
    printer.change_border("#")
    printer.print_message("Now all the work is done, exiting")

    f.close()

Displaying Open Street Map Data

Now you will put together all the pieces you have learned so far by extending the web application to display locations from Open Street Map on the map.

The goal of this milestone is to create a simple data structure for storing locations (nodes), populate the data structure with data from the Open Street Map project, and display all the nodes on the map.

Create a data structure to store locations

At the moment, all we want to do is to store all nodes with their longitudes and latitudes in memory. To do this, we represent nodes with a simple Python class holding the node id and its associated longitude and latitude:

# A simple node class
class Node:
    def __init__(self, id, lat, lng):
        self.id = id
        self.lat = lat
        self.lng = lng

Create a file called store.py and insert the code above there.

The data structure to store all the nodes is simply a dictionary using the node id as key and an array bounds to keep track of the boundaries of the nodes.

class NodeSet:
    def __init__(self):
        self.nodes = dict()

        # actual min and max latitude and longitude of coordinates
        self.bounds = dict()
        self.bounds["min_lat"] = 90
        self.bounds["max_lat"] = -90
        self.bounds["min_lng"] = 180
        self.bounds["max_lng"] = -180

    def add(self, id, lat, lng):
        self.nodes[id] = Node(id, lat, lng)
        self.bounds["min_lat"] = min(self.bounds["min_lat"], lat)
        self.bounds["min_lng"] = min(self.bounds["min_lng"], lng)
        self.bounds["max_lat"] = max(self.bounds["max_lat"], lat)
        self.bounds["max_lng"] = max(self.bounds["max_lng"], lng)

    def remove(self, id):
        del self.nodes[id]

    def get_nodes(self):
        return self.nodes

    def print_node_set(self):
        for k, n in self.nodes.items():
            print("id:" + str(k) + "\tlat: " + str(n.lat) +
                  "\tlng:" + str(n.lng))

Using the osm_parser to parse our map data we get the following Python code:

from mapvis.parser import get_default_parser
from mapvis.store import NodeSet

def extract_osm_nodes(f_name):
    # Parse the supplied OSM file
    print("Loading data...")
    parser = get_default_parser(f_name)
    node_set = NodeSet()

    for node in parser.iter_nodes():
        node_set.add(node['id'], node['lat'], node['lon'])

    return node_set

Use the extract_osm_nodes function

Write Python code that uses the extract_osm_nodes function to read your OSM data, store it in the NodeSet class and then print out all nodes that are stored in memory.

Only use nodes in a particular rectangular area

In the map application we will need to draw all nodes in the rectangular area currently visible in the map window. This operation may have to be done multiple times, which is why we need a class holding only the nodes inside this particular rectangle. The following Python snippet creates an object holding only the nodes fitting that description:

def select_nodes_in_rectangle(nodes, min_lat, max_lat, min_lng, max_lng):
    # actual min and max latitude and longitude of coordinates
    nodes_in_rectangle = NodeSet()
    for k, node in nodes.get_nodes().items():
        if(min_lat < node.lat and node.lat < max_lat and 
           min_lng < node.lng and node.lng < max_lng):
            nodes_in_rectangle.add(k, node.lat, node.lng)

    return nodes_in_rectangle

Use the select_nodes_from_rectangle function

Write Python code to get hold of, and print out, only the nodes within the rectangular area given by

minlat = 58.3984, maxlat = 58.3990, minlng = 15.5733, maxlng = 15.576

Write unit tests for the select_nodes_from_rectangle function

When you develop software it is essential to test that it does what it is supposed to do. Especially when you develop data structures and algorithms, creating good test cases is both easy and could save a lot of time. To test a single unit of a program, such as a function or a class, is called unit testing. In this exercise you will implement unit tests for the select_nodes_from_rectangle function.

Learn more about unit testing

Read the Wikipedia article on unit testing.

Create a simple unit test Using Python's unittest package

One of many advantages of Python is that it has a built-in unit testing framework called unittest. Read more about it here.

Here is an initial unit test for the select_nodes_in_rectangle function.

import random
import unittest

from mapvis.store import Node, NodeSet
from mapvis.store import extract_osm_nodes
from mapvis.store import select_nodes_in_rectangle

def node_inside(node, min_lat, max_lat, min_lng, max_lng):
    return (min_lat <= node.lat and node.lat <= max_lat and 
            min_lng <= node.lng and node.lng <= max_lng)

class TestSelectNodes(unittest.TestCase):
    def test_empty_nodes(self):
        nodes = NodeSet()
        selected_nodes = select_nodes_in_rectangle(nodes, -10, 10, -10, 10)
        self.assertEqual(nodes.nodes, selected_nodes.nodes)

    def test_empty_clip_nodes(self):
        nodes = NodeSet()
        nodes.add(1, -10, -10)
        nodes.add(2, -5, -5)

        selected_nodes = select_nodes_in_rectangle(nodes, 0, 10, 0, 10)
        self.assertFalse(selected_nodes.nodes)

    # def test_some_nodes_inside(self):

    # def test_all_nodes_inside(self):

    def test_random(self):
        # Create 100 random nodes
        nodes = NodeSet()
        for i in range(100):
            nodes.add(i, random.randint(-180, 180), 
                      random.randint(-90, 90))

        # Randomly choose the min and max latitude and longitude
        min_lat = random.randint(-90, 90)
        min_lng = random.randint(-180, 180)
        max_lat = min_lat + random.randint(0, 90-min_lat)
        max_lng = min_lng + random.randint(0, 180-min_lng)
        
        # Extract all nodes within the randomly generated rectangle
        selected_nodes = select_nodes_in_rectangle(nodes, min_lat, max_lat, 
                                                   min_lng, max_lng)

        # Make sure that all nodes that should be inside are inside
        for n in nodes.nodes.values():
            if n.id in selected_nodes.nodes.keys():
                self.assertTrue(node_inside(n, min_lat, max_lat, 
                                            min_lng, max_lng))
            else:
                self.assertFalse(node_inside(n, min_lat, max_lat, 
                                             min_lng, max_lng))

if __name__ == '__main__':
    unittest.main()

The code assumes that select_nodes_from_rectangle is in the file store.py, change this if necessary.

Run the unit test by executing the Python script (python3 test_select_nodes_from_rectangle.py). Make sure that your existing codes passes the three test cases.

Implement the test_all_nodes_inside test case

In the code above the test case test_all_nodes_inside is not implemented. To implement it, add the following code:

def test_all_nodes_inside(self):
    nodes = NodeSet()
    nodes.add(1, -10, -10)
    nodes.add(2, -5, -5)
    selected_nodes = select_nodes_in_rectangle(nodes, -10, 10, -10, 10)

    self.assertTrue(nodes.nodes.keys() == selected_nodes.nodes.keys())

Run the updated unit test and you should get a similar error message as shown below. Why does it fail? What is wrong, the implementation of select_nodes_in_rectangle or the test case? Fix the problem and run the unit tests to make sure your code works.

Implement the test_some_nodes_inside test case

Using what you have learned so far, implement the test case test_some_nodes_inside and make sure all unit tests are passed by your code.

Add unit tests for the Node class

Now that you know how to create unit tests create one for the Node class. There should for example be tests to make sure that the latitudes and longitudes are always within their bounds. Create both hand made test cases as well as randomly generated test cases. You can read more about latitudes and longitudes here.

Extend the map application to display all locations

To display nodes from OSM as markers on the map you need to select an area, extract those nodes you would like to display, and call createMarker for each of those.

This is done in two steps, extend the view and then extend the template.

Extend the view to include a set of markers

The following code parses the file linkoping_map.osm in the same directory as the view code, extracts all nodes in a rectangle corresponding to the area between the E-house and the physics building, and adds the list of nodes to the context used to render the map.

def mapapp(request):
    node_set = extract_osm_nodes("liu.osm")
    node_set = select_nodes_in_rectangle(node_set,
                                         58.3984, 58.3990,
                                         15.5733, 15.576)
    c = Context({'GMAPS_API_KEY': '+++YOUR_GMAPS_API_KEY+++',
                 'COORDS': node_set.get_nodes().values()},)

Extend the template to display a set of markers

In the previous task you created a list of node objects and associated them with the identifier COORDS in the context. To display each of these nodes as a marker you can use the excellent Django template functionality. Basically, you can use simplified Python code to loop over a list and extract the attributes of each object. The following Django template code generates a JavaScript function to display all the nodes associated with COORDS as markers. Include the code last in the JavaScript section of the mapapp.html template.

function displayMarkers(map) {
    {% for coord in COORDS %}
        createMarker(map, new google.maps.LatLng({{coord.lat}},
                                                 {{coord.lng}}),
                                                 ""+{{coord.id}});
    {% endfor %}
}

To display the markers you also need to call the function displayMarkers(map) in the initialize() function, preferably at the end.

Congratulations, you have now learned how to create a web application displaying a map, how to extract data from the Open Street map project, store it in a data structure and display it in your web application. Equipped with this, you will now create more advanced map-based web applications.

The first step is to extend your web application to assist a user to find her way between two locations. This is the basis for direction and route finding applications such as those provided by Google and Apple.

The image below is showing how the finished product could look like, of course yours are going to be prettier.

The goal of this part of the project is to develop a web application that assists a user to get from a location A to a location B. To achieve this, the application should allow a user to select two locations on a map, compute the shortest path between these locations and display the path on the map. To compute the shortest path you also need to create a data structure storing information about which locations are connected and the distances between them as well as populate it with real map data.

This part is divided into four milestones. When you have completed them you will have a good foundation to extend the project later on.

Store The Road Data

You have already extracted the nodes from the OSM data, but to be able to find the shortest path you also have to find out what roads there are. The OSM data also contains road data and the purpose of this milestone is to extract this information.

Store an edge

class Edge:
    def __init__(self, f, t, w=None):
        # Create an edge with weight w from Node f to Node t,
        # f and t are node ids and w is a number
        self.f = f
        self.t = t
        self.w = w

    def update_weight(self, w):
        if self.w is None:
            self.w = w
        else:
            # Don't replace a shorter road with a longer one
            # in the case of two or more roads between the same nodes
            self.w = min(w, self.w)

Get the data from the osm file

def extract_osm_edges(f_name):
    # Parse the supplied OSM file
    parser = get_default_parser(f_name)

    edge_set = None

    # Fill in the missing code
    # pssst OSMParser has a function called iter_ways()
    # print what that function returns

    return edge_set

Store all the edges

Shortest path

Create a mathematical graph

• the mathematical concept of a graph
• typical data structures used to represent graphs.

• adjacency lists, or
• an adjacency matrix.

Implement it in Python

Implement your chosen data structure in Python and make sure you have appropriate test cases.

Populate the data structure with data from Open Street Map. To do this you will have to decide how to calculate the geographical distance between two nodes that are part of a road. Since the Earth is not flat, the distance between two points on the map cannot simply be calculated as the two dimensional Euclidean distance. One way is to use the haversine formula, as in the following Python code snippet:

from math import sqrt, radians, sin, cos, asin

def length_haversine(p1, p2):
    # calculate the distance between two points using the Haversine
    # formula which incorporates the earth's curvature, see
    # http://en.wikipedia.org/wiki/Haversine_formula.
    lat1 = p1.lat
    lng1 = p1.lng
    lat2 = p2.lat
    lng2 = p2.lng
    lat1, lng1, lat2, lng2 = map(radians, [lat1, lng1, lat2, lng2])
    dlat = lat2 - lat1
    dlng = lng2 - lng1
    a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlng / 2) ** 2
    c = 2 * asin(sqrt(a))
    # return the distance in m
    return 6372797.560856 * c

Implement the shortest path algorithm

Implement a provably optimal algorithm to compute the shortest path between two locations using the graph data structure together with appropriate test cases (you do not have to prove that it is optimal). You should write your own code implementing and testing an existing algorithm, There are many algorithms for finding the shortest path between two nodes in an edge weighted graph. For this project we suggest you start out by implementing Dijkstra's algorithm.

Display the shortest distance

Add start and end coordinates

1. Create an HTML form with at least four fields, start latitude, start longitude, destination latitude and destination longitude. Read about HTML forms here.
2. Create an on click event handler that fills in the fields in the form when a user clicks on the map. Since the user needs to select two coordinates you have to find a way to do that (one approach is to have a very simple state machine with two states, one for entering the start coordinate and one for entering the destination coordinate). In the introductory part you created an on click event handler so the new thing is to populate a form with that data. One page discussing this is javascript-coder.com.
3. Process the content of the form in the view. So when you press the "Go" button, you are directed to the same page. The content of the form is sent by POST and is available in Django as request.POST.
   
   Below is some code for an object that handles POST requests. Note: all the values are defined in the initialization, when the object is first defined i.e. nothing happens with the values in the object until the "Go" button is pressed

   #---------------------------------------------------------------
   # POST_parser.py
   # Object that parses and stores content from request.POST
   # in Django.
   #---------------------------------------------------------------
   # Usage:
   #   post = POST_parser(request)
   #---------------------------------------------------------------
   
   
   def get_float(request, id):
       value = request.POST.get(id)
       # Check that it's possible to convert input to float.
       try:
           return float(value)
       except (TypeError, ValueError):
           return None
   
   
   def get_str(request, id):
       return request.POST.get(id)
   
   
   class POST_parser:
       def __init__(self, request):
           # You can choose what variables you want to
           # get from POST and what to call them.
           self.lat1 = get_float(request, 'lat1')
           self.lng1 = get_float(request, 'lng1')
           self.lat2 = get_float(request, 'lat2')
           self.lng2 = get_float(request, 'lng2')
   

   If you want any other value from a form, simply create a new variable.
   
   Example: self.foo = get_float(request, 'id')

   try: ... except: ... !?

   What does the try: ... except: ... statement above do? Its purpose is to test if something is possible to do, in this case convert a string to float. If it isn't possible, an exception is thrown. If you don't handle the exception the program will crash, which is pretty bad.

   So how does it work? The program tries (try:) something, if it succeeds, good! else handle the exception (except:) e.g. print("Err: Conversion is not possible").

4. To prevent cross site request forgery (CSRF) Django requires you to take some measures that are described here. Make sure that you follow these instructions.

User input

Since a user might click anywhere on the map, you have to implement an algorithm that finds the node in the map database closest to a given coordinate. An initial approximation can be to find the node which has the closest distance to the selected coordinate. Luckily, you have already implemented function that computes the distance between two coordinates represented as a pair of latitude and longitude. A second approximation could be to find the N closest nodes and make a somewhat smart selection among these. A third approximation is to find the closest point on the edges between the nodes (and implicitly add a node there). This is very useful if there are long road segments and the selected location is right in the middle of that segment.

As always, you should also create appropriate test cases.

Some more small extensions

• Extend the map application to display the start and destination with for example markers.
• Extend the application to show the computed distance somewhere.

Display the shortest path

Get the shortest path

Visualize the shortest path

function createPolyline(map, path) {
  var polyline = new google.maps.Polyline({
    path: path,
    map: map
  });
}
function displayRoads(map) {
  var points = new google.maps.MVCArray();
  points.push(new google.maps.LatLng(58.3970323, 15.5738155));
  points.push(new google.maps.LatLng(58.3976588, 15.5738047));
  createPolyline(map, points);
}

Extending Your Application Further

After you have completed all the tasks in the previous 5 chapters, you have accomplished a lot. You have created and tested a graph data structure, populated it with data from the Open Street Map project, implemented and tested a shortest path algorithm, created a web application where a user can select multiple locations (and map these locations into nodes in the graph), displayed single and multiple paths in the web application, and more.

What you have done so far provides you with both a set of components for more advanced map-based applications as well as an understanding of some of the basic issues involved in map-based applications. Now you will extend your application further or develop new applications starting from the code you already have. This is a very open ended project with many possibilities to create exciting map-based applications. Below are some example suggestions that you can chose from and extend as you like. You are also welcome to suggest your own improvements.

Smaller improvements to the shortest path application:

The application you have made so far is a bare minimum of a path finding application, below are a few things will make your application more user friendly and usable.

• Add speed to the edges and let the user ask for the fastest way rather than the shortest. Can you provide better choices by minimizing the number of crossings that the user needs to pass?
• Improve the efficiency of the application by for example adding a bounding box to the roads to filter out as many of them as possible before drawing them on the map. If you do this, then it is a good idea to measure how long it takes to create the page so that you see that you are making progress.
• Add a search box so that a user can enter an address which is looked up using the Google Geocoding API.
• Compare the shortest paths you find with the ones provided by the Google Directions API.
• Add support for buildings. This would involve at least parsing the buildings from the OSM data, storing them in your application and displaying them on the map. You could also add further information so that when the mouse is hovering over a building you display some interesting piece of information about it.

Speed improvements to the shortest path application:

As stated in section 5, using a matrix is pretty inefficient for sparse graphs. You can do some improvements to speed up the algorithm.

If you are not already using an adjacency list instead of a matrix, then change it. An adjacency list is a list where each element is representing a node and the elements in the list are the neighbors of this node. A dictionary becomes very handy since you can use the node id as key to a list containing all neighbors to that node.

Just a simple graph.	The graph is actually representing the seven bridges of Königsberg.
A B C D A 0 1 1 2 B 1 0 inf 3 C 1 inf 0 3 D 2 3 3 0	A (B, 1) (C, 1) (D, 2) B (A, 1) (D, 3) C (A, 1) (D, 3) D (A, 2) (B, 3) (C, 3)
Matrix representation of the graph	List representation of the graph

The upper image to the left is showing a simple graph. The weight of the edges are the distances between the nodes, approximately 1, 2 and 3 units. Actually the graph is an abstraction of the bridges in Königsberg shown in the picture to the right. Below are two graphs. The one to the left is the matrix representation of the graph and the one to the right is the list representation, where every node has a list containing its neighbors as pairs (neighbor, weight).

Implement Dijkstra using a heap, which makes look-up of the min-element take constant "O(1)" instead of linear time "O(n)". An article about Dijkstra using a heap. Only consider nodes that contain a crossing. Since if a node only has one edge in to it and one from it you only have one path to choose from.

All pairs shortest path

Floyd-Warshall algorithm is an algorithm to compute every shortest path between each pair of nodes. The algorithm is really easy to implement.

Read about the algorithm and answer these questions:

Now do the following:

1. What is the time complexity?
2. Estimate a maximum number of nodes the algorithm can handle in a reasonable amount of time

1. Extend the map application to allow a user to select a set of coordinates.
2. Implement an all-pairs shortest path algorithm using the previously developed graph data structure including the API and the unit tests.
3. Extend the map application to display all the paths.

You can store the precalculated paths in a database, to make the application really fast. If you want to do that, check out the extension project "Using a database" below.

Using a database

Almost all web applications in the World Wide Web uses databases. By using a database, it is possible to precalculate a lot of things by storing information from previous searches, making the searching much more efficient. Another advantage is that you as the admin of the website can look at statistics about what the users do, exactly like Google and Facebook.

Currently all the data is stored in memory and if you reload the page then all the data is loaded again. Extend the application to store all the data in a database instead. This makes the data persistent and potentially improves the efficiency of the application. This is also a good exercise since all modern web applications are database-driven. Try to move as much functionality into the database as possible, for example by replacing NodeSet with a database query.

Create an application which lets users record their current or planned future location. This can be used to see where your friends were last seen and potentially where to look for them. Maybe you can connect the central schedule database to your application to show where you should be depending on what courses you take?

Extend the application by collecting information from the user. Initially it could be to only ask for the current position of the user. Maybe you are even able to get that information from the GPS on the users device?

If you have done the "all pairs shortest path" project you can use it to calculate the shortest path and store the precalculated paths in the data base.

Build a beer pipeline!

You have been given the task of building a beer pipeline by connecting plastic tubes to provide all your friends with beer directly from HG. Since you are thirsty you want to minimize the total amount of plastic tubes that you have to connect before finishing the project.

Extend the map application to allow a user to select a set of end points and then find the edges along which the pipeline should be built so that the total length of the pipeline is minimized and display the result on the map. You can make this problem easier or harder depending on how much freedom you consider to be allowed when constructing the pipeline. The simpler version is to only build the pipeline along existing roads. To make the problem harder, and the total length of the pipeline shorter, you can allow new nodes to be added. If you allow new nodes then you can start by ignoring buildings and then add these later. The more accurate you want the result to be, the more complicated it becomes.

Help a geocacher

Your friend, an enthusiastic geocacher, has heard that you are building awesome map-based applications. Since he is a bit lazy he has asked you to extend your application to allow him to select a set of geocaches and then automatically find the shortest route from his apartment visiting all the caches and then back to the apartment.

In any case you can either focus on developing the necessary algorithms, the web application or some combination of them. Remember to also implement the appropriate testing to increase the quality of your code and hopefully decrease the development time. If you decide to work more on the web application rather than the underlying algorithms you may use existing code libraries such as Google's APIs or graph libraries (for example networkx, igraph).