Open Data Internship – Week 12 – A retrospective

As I come to the end of my time here I am finding that I am looking back on what I have done. So here I have collected my actions into one place for the purpose of giving next year’s intern an idea of what they should do and where to start. So…

What Have I done?

To start with, I read all the blogs written by last year’s intern.

After doing that I started looking into SPARQL, and eventually put together this query for finding all building without images.

It works by getting all buildings, then optionally finding associated image, label and geodata. Then removing all data points, which do have an image.

Then went out into the world armed with a clipboard, list and camera to take photos of missing buildings. It is best to do this in good weather so planning is vital. I would advise the next person to set this up very early in their internship. Then when the weather is good, go out and gather the data.

The next thing I did was make a map showing building internals. This was my main project for the course of my internship, the aim of which was to make an app, which people could use to navigate around building 37. The source code for this is available here primarily in the map.js file. This file uses leaflet js and leaflet-indoor to draw a map using the university’s curated map tiles, then drawing polygons representing the rooms on the map, with leaflet indoor handling the rooms being on different levels.

I drew these rooms is QGIS, by tracing floor plans given to use for the purpose of this project. These were stored as geojson polygons, with some information about the room, typically type of room (office, way, stairs, lift); level; and a label giving the room number.

The next part of this project was to allow a user to navigate the map. To do this I decided to take a graph based approach. This meant that a user would navigate between nodes via edges. This means that A user would start at one node, which would be connected to another node by one or more edges. A user could then move from one node to another via an edge. The nodes would be placed in rooms as destinations and in corridors and doors to allow for model of travel balancing complexity of the situation and simplification for computational reasons. I started to do this with a breadth first search (BFS), but this quickly become too unwieldy to use as the computational complexity of a BFS is branching factor *depth, which happens to total the number of nodes in the graph, as such the complexity is O(n). So I decided to move to an A* search, using the following heuristic:

Distance travelled along edges + distance directly To End + (0.35 * levels changed). This means that I would sort all nodes on the graph I had travelled to by this value and expand the node that had the smallest value first. Now whilst the complexity of this should still be branching factor *depth, a perfect heuristic gives a branching factor of 1, as you assume you will always take the best route, as for depth this is slightly harder to justify. However, our map is finite and currently to one building, with hopes of eventually the whole campus, the depth would be finite and not directly tied to the number of nodes in the map, so that will be constant a constant value too. Based on these two points the complexity of the new navigation method is O(1).

The first time I drew the nodes to navigate; I drew them in QGIS, and manually added the edges. However, I eventually built a webpage that would allow me to add nodes and draw the edges automatically. This is available here in the edit.html and edit.js files.

I spent a sizable amount of august making a json editor in python, available here. I was mildly proud of this as a vast majority of the functionality is dynamically generated from a schema for the data. However, due to a lack of foresight and testing it was decided that this was not the best way to add/edit map data, so I made the edit.js code instead.

The other thing I did during my time here was to look through the work done by the previous intern. This comprised of looking through an app they had written for data gathering purposes and some data they gathered which had not made it onto the open data site. Once I found the data that had not been added, I worked out what it was for and got it added to the website.