Hey everyone, who's having a good time at EuroPython? Uh, I'm Vinayak. Uh, and today I'll talk to you about my project to run every street in Paris.

Um, so this is the general outline. I'll talk about my motivation to do something like this.

Um, we'll look at GIS and related concepts. Um, how we can get data from OpenStreetMap. Uh, how we can store it in PostgreSQL with PostGIS. Um, and finally, map our runs to uh, the uh, street network to visualize our progress.

Um, hopefully that that'll give you like an overview uh uh about how to build a system like this to run every street in your city or uh maybe to tackle similar problems uh to this one.

Um, I'm a software engineer based in Paris. Uh, I've built a bunch of open source tools like Camelot, Present, Flour, which some of you might have used.

Uh, most notably Camelot, uh, which is like a Python library to extract tables from PDFs, uh, used at places like NASA, Stripe, Figma.

Uh, you can check them out at the link up top, vinayak.

io/code. Uh, I'm also part of the Recurse Center, which is a programming retreat in New York City, uh, where you spend six or 12 weeks uh programming at the edge of your abilities.

It just requires investment of your time and nothing else. So, uh, if you're in a position to do it, I'd really recommend being part of a batch.

Uh, if you have any questions about RC, you can catch me after the talk.

So getting back to the main subject, how did I start thinking about running every street in Paris? A couple of years ago, I stumbled upon the PACTOM project by Tom Murphy where he ran the length of every street in Pittsburgh, which is 2,400 kilometers in total.

He finished the project in 2022, covering close to 6,000 kilometers in 269 runs across two decades.

It took him a long time because he was working with the constraint of starting or ending the run at his apartment, at his home, basically.

So I started looking for other people doing the same and found Rickey Gates, who ran every single street in San Francisco. He, on the other end, finished the project in just 45 days, perhaps because he wasn't operating under the same constraint as Tom.

So I started thinking if I could run every street in Paris.

I moved here in 2021 and love how walkable the city is.

I've been doing the same running loops and it had gotten a bit monotonous over time, and I thought it would be a fun challenge to run every street in the city.

So Tom Murphy and Rickey Gates had a bit of a manual approach.

So I also thought it would be fun to automatically track my progress as I run, as it could be a fun side project and a way to learn about GIS, which is another thing I always wanted to do.

So I came up with this initial approach: fetch the street network from OpenStreetMap.

Compute the minimum number of 10k routes that could cover every street in the city.

Run them automatically, match my runs to the street network, and then visualize my progress.

OSM, for those of you who are not familiar, is a free and open map database updated and maintained by communities all around the world.

It was very easy to fetch the street network for Paris from OSM with a library called OSMnx, which we'll look at later.

But calculating the minimum number of 10K parts that can cover every street in Paris turned out to be a bit challenging.

I discovered that what I was trying to do was essentially a variation of the Chinese postman problem, where we need to come up with the shortest route that can cover every street in a road network.

At this point, I was spending a lot of time wrestling with the data I got from OSM and not a lot of time running.

I thought that initially I can just draw these routes manually, build out the rest of the system to match my runs and visualize the progress, and then eventually get back to computing routes automatically.

And now, I've built something where whenever I upload my run on Strava, it sends a webhook to my server, which updates the description of my Strava run.

And as you can see, I've covered almost 30% of Paris at this point.

I've also built a way to visualize my progress.

So, this is where I'm at right now. I've covered almost 30% of streets, and maybe I can give you a short demo.

If I can figure out a way to, uh, okay, so, um, it basically shows all the streets I've run, uh, which are marked as green, and all the streets that I haven't run.

Uh, I can draw—it's hard to draw looking at it that way, but, uh, I can basically, uh, look at the streets that I haven't run on, uh, start drawing a route, uh, put it on my watch, uh, and then keep, start running.

Um, and so if I go back, uh, to the presentation, uh, if you want, you can, uh, check out my progress too by going to, uh, this public link.

I put in like a QR code which should make it easy for you to access it.

Um, where you'll see the same zoomable map of all the streets I've covered. Um, so before going into the implementation, uh, let's take a step back and talk about GIS, uh, because what I've essentially built is a geographic information system.

Um, GIS is a framework for gathering, managing, and analyzing spatial data. Uh, these systems are used everywhere from urban planning to logistics, et cetera, et cetera, just, uh, like a lot of applications.

When working with spatial data, we need to understand coordinate systems.

Um, there's mainly two types: uh, geographic coordinate, uh, coordinate systems, which use latitude and longitude, like, uh, WGS84, uh, which is World Geodetic System 84, uh, which is what our GPS uses.

Um, and then we have projected coordinate systems that flatten the Earth onto a 2D plane, uh, like the Mercator projection, which you might remember from school.

Each has trade-offs. Uh, geographic systems, uh, are great for GPS, but projected systems are better when you need to calculate distances and areas more effectively.

Um, there are two main ways to represent spatial data.

Uh, vector data represents features as points, lines, and polygons. Think of it as drawing uh with geometric shapes uh like you would do with an SVG uh on the web browser.

On the other hand, raster data is like a grid of pixels, uh basically like images. Um, vector data is perfect for discrete things like roads, buildings, or city boundaries, uh whereas raster data works great for elevation maps, temperature, or satellite imagery.

Uh for my street running project, I'm mostly working with vector data. So let's break down the basic building blocks of vector data.

Uh points represent single locations. For example, uh the location of this conference center or uh like the location where I started my run.

Um, line strings are paths or routes, uh perfect for representing streets, uh or running, uh or like the complete run basically. Uh, and polygons represent areas like parks, buildings, or even an entire city.

Um, these are the fundamental geometries. Uh, and uh we can combine them into more complex shapes like a multipoint or a multi-line string, but we won't cover that in this talk.

Um, now let's talk about GPX. Uh, so when we record a run using a GPS watch or a phone, uh the data gets saved in this file format called GPX, which uh stands for GPS Exchange Format, and it's basically an XML that stores the coordinates of your run.

So I guess if you look here, we have the lat long, we have the elevation, the timestamp at which it was recorded.

Um, and this is the raw data that I get from my runs that I need to process and match against the street network to finally visualize the progress.

And most fitness apps like Strava, Garmin Connect, or Apple Fitness can export data in this format, basically export your runs in this format.

So where do we store all the spatial data? That's where Postgres and PostGIS come in. Postgres is this incredibly powerful database which has been around forever, basically.

And PostGIS is an extension that turns Postgres into a fully-fledged spatial database.

You can enable it in Postgres by just running `CREATE EXTENSION postgis`. And it adds these data types that we just talked about so that we can store points, lines, and polygons directly into Postgres.

Plus, it gives us hundreds of spatial functions like calculating distances, finding intersections between two line strings or two geometries, checking if a point is inside a polygon, etc. There's just a bunch of them.

So I guess with those building blocks in mind, we can start looking at some code. So if I go here, I mentioned OSMNx at the start.

So this is the library we can use to get the street network for any city out as a graph data structure. So we import it with `import osmnx as ox`.

We can then use the `graph_from_place` function, put in the city name. And since we want to run every street, we put the network type to `walk`.

The thing that we'll get back is going to be a NetworkX graph, which I can show you now.

So as you can see, I have this helper function, and it's displaying the full graph for Paris.

And if I zoom in, you'll see that it's very dense because there's a bunch of streets to walk on.

Uh, but also that every street has two edges, which is a bit overkill for what we are trying to do. Uh, and it's also it also just makes it a bit harder to process this graph data structure.

Ideally, we'd want to have just one edge per street so that it's easier to process the whole thing.

Um, so what we can also try is um, uh, specifying the network type as 'drive,' which should hopefully prune our graph.

Uh, and when we look at that one, it removed a bunch of edges here, uh, and uh, in those parks because cars can't go in there.

And so if I now zoom in, uh, we can see that every street is a single edge, which is a bit easier to work with.

Um, but if I go to like, uh, maybe another uh, area, for example, this one, it's uh, you can see that there's um, some streets that we haven't uh, gotten uh, because cars can't go there.

But I can still run there. So like, uh, we still need a way to like get those streets somehow.

Um, so I was researching like, um, how to do that and like, uh, other people who might have uh, done things like this and came across uh, this repo by Matej Kereki, where uh, he's defined uh, this really complex uh, custom filter because you can filter OSM data with like, um, like different types of filters, and here we are basically excluding uh, toll roads um, private roads, all of those things.

And if we use this filter uh by just passing in custom filter like that, um, we'll get a much better graph.

And if I go back to uh the area I was showing, uh you can see that uh we have the streets that we uh previously didn't get.

Um, so yeah, it's a better graph to work with. Um, we then convert that graph into a Geo DataFrame.

Uh we can do that using the graph to GDS function. We don't really care about the nodes, uh just the edges.

So we uh set nodes to false, uh edges to true. And this will give us streets, um, which is a GeoDataFrame that looks like that.

Uh we'll have an OSM ID for every street, um, uh the uh highway type, uh the name of the street, uh the length, and most importantly, the geometry, which is a line string which is connecting two uh points that uh I just showed you.

So I guess as with any data project, there's a bunch of data cleaning to be done.

Um, there's a bunch of NaNs uh in the street names and uh some of the street names are also lists.

Uh so uh we need a way to fix that. Um, and what I wrote is this simple ensure string function, which uh converts the list uh names into like just one single uh name, which is a string.

For example, if there's 10 NaN streets, uh I name them like unnamed street one, two, three, and so forth. Uh so that uh we just have different uh streets to work with and not just like a single name.

And so if we apply uh both of those transformations, we'll see that all the NaNs and lists are gone and the data looks a bit clean.

Um, but then there's this thing where the streets that we get back from OpenStreetMap, they can sort of lie in the data frame as different segments of the same street.

And so we need a way to combine them because if there's a really long street, you can sometimes have three segments of the same street.

But what we care about for our matching is just one street. And to do that group by, we can use this dissolve function from GeoPandas, where we group by name.

And what it basically does is combines all of the different geometries by name into a single geometry so that at the end we only get one street.

So if you do that, you can see that all of the duplicate streets are gone and all of their geometries are combined.

Now we can start inserting this data into Postgres. So here I'm just creating a session into a Postgres instance running on my local machine.

I've already created a database called Paris. Um, this is the streets table that I want to create.

I've defined an ID column, which is going to be the primary key of this table. It's going to be an auto-increment field.

For now, I'm just storing the name of the street and the geometry, which we need to specify as a multi-line string.

We can also store like the OSM ID and all of those other things. But I guess for the purpose of this talk, I'm just going to go with these two columns.

So then we can iterate on all of the unique streets that we found and start inserting them into a table.

And in the end, when we query the table, we can see that we found around like 5,400 streets.

So now we are ready to do map matching. So if I go here, let me just grab some water real quick.

So I did the short run and downloaded the GPX file for that run. And the way we parse that GPX file is using a library called GPXPY.

It gives us a GPX object with track, segments, and points.

Running every street in Paris with Python and PostGIS — Vinayak Mehta

The official YouTube Channel of the EuroPython conferences. Current edition: EuroPython 2023.

EuroPython is the official European conference for the Python programming language.

Copyright © 2004-2023, EuroPython Speakers, EuroPython Society, Sweden and the Local Organisers of the EuroPython conferences. "EuroPython" is a trademark of the EuroPython Society.


Running every street in Paris with Python and PostGIS — Vinayak Mehta

Scripts