Upstream/Downstream: Discovering and Displaying Watershed Topology!
CC Attribution - ShareAlike 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this
Phillips, Mark
Where does the rain go once it hits the ground? Some of it soaks into the ground, and some of it evaporates. The rest flows into creeks, streams, lakes, and rivers, eventually making its way to an ocean. The route that this water takes is described by thousands of regions called watersheds. Visualizing how these regions connect to each other involves finding and reformatting some public data, a bit of fun graph algorithm coding, and some challenging graphics performance issues associated with the display of 100,000 polygons in your browser! Come see a demonstration of an interactive open source web application that you can use to see everything that is upstream or downstream from any location!
 Okay, I'm going to talk about a geography problem that I started thinking about recently. And the problem is this, given any particular spot on the ground, like this yellow dot, if it rains there, where does the water go? So in particular, what is downstream from that spot? And then also conversely, what's upstream from that spot? So all the places where if it rains there, the water is going to go flow past that yellow dot. So I started thinking about this recently, and I'm not a geologist or a hydrologist, actually a mathematician, but I looked into it and found out that you can get a dataset from the US Geological Survey that describes this. And so I wrote kind of a fun graphics application to visualize the results. So let me, I'm going to switch real quick and give a demo of the application and then talk a little bit about what went into creating it. So let's see. Yeah, so here's the program. This is online at this address. I'm running this locally at the moment. But you can check it out if you want. So what's happening is as I move the cursor around, the program is drawing in blue everything that's downstream from where the mouse is. And it's drawing in red everything that's upstream. And the map's interactive, so you can pan and zoom around like in any web map that you'd expect. And it's interesting to look at some particular areas here. Like let's zoom in on New Orleans and highlight the Mississippi River near downtown. And then zoom out and you can see all the area that drains to New Orleans. And another area that's cool to focus on is Chicago. If you zoom in, look how close the Mississippi watershed gets to downtown Chicago. In fact, it actually overlaps, I mean, how close it gets to Lake Michigan. It actually overlaps a little bit there, but that didn't used to be the case. Some canals were put in in the 1800s to connect the Des Plaines River, which is this river right here with Lake Michigan, and that's what allowed ships to transfer between the Mississippi River and the Great Lakes. And that gave rise to Chicago as an important transportation hub in the 1800s. Another area that's kind of fun to focus on is you go out here to Montana. And so this is the starting with the Mississippi way over here and then coming up the Missouri River to see how far you can get over to the west before jumping across the continental divide to get to the Columbia River watershed to go to the west coast. And that's, in fact, exactly what Lewis and Clark were trying to do in their famous expedition 200 years ago or so. Another area that's fun to focus on is Nevada and part of Utah. Look at this. It has the property that in a lot of cases the downstream flow never makes it to an ocean. This is what's called a great basin, and it's known for being particularly dry and having this hydrologic property. There are a few streams and creeks there, but they just peter out. All the rain that falls either evaporates or soaks in the ground or flows into lakes. They have no outlet like Salt Lake, and I think that's why it's salt. So anyway, so let me say a little bit about what I learned about surface water hydrology in order to create this program. Let's see. So like I said, the data comes from the US Geological Survey. There's a database called the Watershed Boundary Data Set, and it works like this. It divides the country up into regions. It's a nested hierarchy of regions, and I'm going to zoom in to the smallest level, the one that's the greatest level of detail, and look at this one particular example. So I'm going to focus on that particular region, and then switch temporarily to a 3D view that I made with Google Earth so that we can see a little bit more about the shape of these regions. So as the camera moves around here, you can see that the boundaries of these regions more or less follow local ridge lines. These regions are about five or 10 miles across at this level, and the boundaries are very carefully chosen so that all the water that leaves each of those regions does so at one point. And in just a second, that polygon's going to turn red. Yeah, so the red polygon, you might be able to make out there's a stream in the middle of that that flows up, this one flows north, and enters the yellow polygon at that one point. So back in the map, there's that red polygon, and it flows into the yellow one at that one point, and this other red one also flows into the yellow one, and the yellow one flows into that blue one, and that blue one flows into that blue one, and then so on. This gives a relationship between these polygons. It's a mini to one relationship. So every polygon has one that's downstream from it, and possibly several that it is downstream from. And so that means that you can think of these polygons as acting like nodes in a graph, and there's edges, directed edges between them that describes the flow. And so that turns the whole map, basically, into a gigantic, directed, acyclic graph, which means that the original problem of figuring out what's upstream or downstream just translates into graph traversal, which is kind of a well-known problem and a lot of fun to code. So once I realized that, I said, yay, I know how to do this, but it turns out there were some challenges with the data. First of all, the dataset, you download this from the USGS, it's two gigabytes. It's way too big to do anything with interactively, and I wanted to make kind of a fun web app like I showed you. And so I had to figure out something about that. And part of the problem, you can see, if I zoom in on just one polygon, part of the problem is that there's so many vertices in the boundary, thousands or hundreds at least. And so that can be remedied because this is a common thing in GIS, and there's a lot of good open-source GIS software that will simplify a polygon and replace it with another one by dropping vertices in a way that retains most of the original shape. So you can cut down the size of the dataset. But remember, there's a bunch of these polygons. There's about 100,000, and they're all right next to each other, they share borders. And if you simplify them all separately, you end up with regions like this where there's little gaps and overlaps. And so the reason for that is that in the original dataset, each polygon is stored separately. And so what I ended up doing is to translate the data into a format that stores the shared border once rather than separately with each polygon. And there's a format called TopoJSON that was invented by the author of D3JS that does exactly that. And so by converting the data to TopoJSON and then simplifying, I got a good, clean set of polygons that fit together well and got the size of the data down to about 40 megabytes. And then I decided to use LeafletJS, Mapping Library to make the map. This is a great library, I like it a lot. But there's an issue in that the way it draws polygons by default is it uses SVG, which creates a node in the DOM for every polygon. And this is the Mississippi watershed here, and it's got about 30,000 polygons in it. And so the first time I ran this, the browser just crashed. And so I had to figure out a different way to do that. So DOM manipulation is slow, that didn't work. Turns out that you can use Leaflet with HTML5 Canvas rendering also, though. And so by switching to Canvas, I actually got it to work and it worked reasonably well, but it was still a little bit slow. And so I made one more optimization, and that was to notice that when the program is drawing these big red upstream areas, they actually consist of a bunch of little polygons. But I didn't really care about drawing the individual polygons. All I really cared about was drawing the one red blob. And so by doing a little bit of computation in advance to merge all the polygons in each of these red blobs into one and just store the perimeter, it cut down the rendering time from being linear in the number of polygons to square root, which for big regions made a huge difference. And so that's what allows the program to be as snappy as it is and made me really happy. So I also made a mobile version just for fun that uses some slightly different optimizations, but most of the same ideas. So it's online, and if you want to check it out and talk to me about it, I'd be thrilled. There's my contact info. So that's it. Thanks. Thank you.
 Okay, I'm going to talk about a geography problem that I started thinking about recently.  And the problem is this, given any particular spot on the ground, like this yellow dot, if  it rains there, where does the water go?  So in particular, what is downstream from that spot?  And then also conversely, what's upstream from that spot?  So all the places where if it rains there, the water is going to go flow past that yellow  dot.  So I started thinking about this recently, and I'm not a geologist or a hydrologist,  actually a mathematician, but I looked into it and found out that you can get a dataset  from the US Geological Survey that describes this.  And so I wrote kind of a fun graphics application to visualize the results.  So let me, I'm going to switch real quick and give a demo of the application and then  talk a little bit about what went into creating it.  So let's see.  Yeah, so here's the program.  This is online at this address.  I'm running this locally at the moment.  But you can check it out if you want.  So what's happening is as I move the cursor around, the program is drawing in blue everything  that's downstream from where the mouse is.  And it's drawing in red everything that's upstream.  And the map's interactive, so you can pan and zoom around like in any web map that you'd  expect.  And it's interesting to look at some particular areas here.  Like let's zoom in on New Orleans and highlight the Mississippi River near downtown.  And then zoom out and you can see all the area that drains to New Orleans.  And another area that's cool to focus on is Chicago.  If you zoom in, look how close the Mississippi watershed gets to downtown Chicago.  In fact, it actually overlaps, I mean, how close it gets to Lake Michigan.  It actually overlaps a little bit there, but that didn't used to be the case.  Some canals were put in in the 1800s to connect the Des Plaines River, which is this river  right here with Lake Michigan, and that's what allowed ships to transfer between the  Mississippi River and the Great Lakes.  And that gave rise to Chicago as an important transportation hub in the 1800s.  Another area that's kind of fun to focus on is you go out here to Montana.  And so this is the starting with the Mississippi way over here and then coming up the Missouri  River to see how far you can get over to the west before jumping across the continental  divide to get to the Columbia River watershed to go to the west coast.  And that's, in fact, exactly what Lewis and Clark were trying to do in their famous expedition  200 years ago or so.  Another area that's fun to focus on is Nevada and part of Utah.  Look at this.  It has the property that in a lot of cases the downstream flow never makes it to an ocean.  This is what's called a great basin, and it's known for being particularly dry and having  this hydrologic property.  There are a few streams and creeks there, but they just peter out.  All the rain that falls either evaporates or soaks in the ground or flows into lakes.  They have no outlet like Salt Lake, and I think that's why it's salt.  So anyway, so let me say a little bit about what I learned about surface water hydrology  in order to create this program.  Let's see.  So like I said, the data comes from the US Geological Survey.  There's a database called the Watershed Boundary Data Set, and it works like this.  It divides the country up into regions.  It's a nested hierarchy of regions, and I'm going to zoom in to the smallest level, the  one that's the greatest level of detail, and look at this one particular example.  So I'm going to focus on that particular region, and then switch temporarily to a 3D view that  I made with Google Earth so that we can see a little bit more about the shape of these  regions.  So as the camera moves around here, you can see that the boundaries of these regions more  or less follow local ridge lines.  These regions are about five or 10 miles across at this level, and the boundaries are very  carefully chosen so that all the water that leaves each of those regions does so at one  point.  And in just a second, that polygon's going to turn red.  Yeah, so the red polygon, you might be able to make out there's a stream in the middle  of that that flows up, this one flows north, and enters the yellow polygon at that one  point.  So back in the map, there's that red polygon, and it flows into the yellow one at that one  point, and this other red one also flows into the yellow one, and the yellow one flows into  that blue one, and that blue one flows into that blue one, and then so on.  This gives a relationship between these polygons.  It's a mini to one relationship.  So every polygon has one that's downstream from it, and possibly several that it is downstream  from.  And so that means that you can think of these polygons as acting like nodes in a graph,  and there's edges, directed edges between them that describes the flow.  And so that turns the whole map, basically, into a gigantic, directed, acyclic graph,  which means that the original problem of figuring out what's upstream or downstream just translates  into graph traversal, which is kind of a well-known problem and a lot of fun to code.  So once I realized that, I said, yay, I know how to do this, but it turns out there were  some challenges with the data.  First of all, the dataset, you download this from the USGS, it's two gigabytes.  It's way too big to do anything with interactively, and I wanted to make kind of a fun web app  like I showed you.  And so I had to figure out something about that.  And part of the problem, you can see, if I zoom in on just one polygon, part of the problem  is that there's so many vertices in the boundary, thousands or hundreds at least.  And so that can be remedied because this is a common thing in GIS, and there's a lot of  good open-source GIS software that will simplify a polygon and replace it with another one  by dropping vertices in a way that retains most of the original shape.  So you can cut down the size of the dataset.  But remember, there's a bunch of these polygons.  There's about 100,000, and they're all right next to each other, they share borders.  And if you simplify them all separately, you end up with regions like this where there's  little gaps and overlaps.  And so the reason for that is that in the original dataset, each polygon is stored separately.  And so what I ended up doing is to translate the data into a format that stores the shared  border once rather than separately with each polygon.  And there's a format called TopoJSON that was invented by the author of D3JS that does  exactly that.  And so by converting the data to TopoJSON and then simplifying, I got a good, clean  set of polygons that fit together well and got the size of the data down to about 40  megabytes.  And then I decided to use LeafletJS, Mapping Library to make the map.  This is a great library, I like it a lot.  But there's an issue in that the way it draws polygons by default is it uses SVG, which  creates a node in the DOM for every polygon.  And this is the Mississippi watershed here, and it's got about 30,000 polygons in it.  And so the first time I ran this, the browser just crashed.  And so I had to figure out a different way to do that.  So DOM manipulation is slow, that didn't work.  Turns out that you can use Leaflet with HTML5 Canvas rendering also, though.  And so by switching to Canvas, I actually got it to work and it worked reasonably well,  but it was still a little bit slow.  And so I made one more optimization, and that was to notice that when the program is drawing  these big red upstream areas, they actually consist of a bunch of little polygons.  But I didn't really care about drawing the individual polygons.  All I really cared about was drawing the one red blob.  And so by doing a little bit of computation in advance to merge all the polygons in each  of these red blobs into one and just store the perimeter, it cut down the rendering time  from being linear in the number of polygons to square root, which for big regions made  a huge difference.  And so that's what allows the program to be as snappy as it is and made me really happy.  So I also made a mobile version just for fun that uses some slightly different optimizations,  but most of the same ideas.  So it's online, and if you want to check it out and talk to me about it, I'd be thrilled.  There's my contact info.  So that's it.  Thanks.  Thank you.
__Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_0_71.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_72_119.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_120_287.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_288_383.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_384_3239.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_3240_3683.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_3684_4055.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_4056_4103.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_4104_6239.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_6240_6455.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_6456_6971.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_6972_14855.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_14856_14927.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_14928_15023.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_15024_15251.png __Con_2016_-_Upstream_Downstream__Discovering_and_Displaying_Watershed_Topology__By_Mark_Phillips_7E_15252_15299.png