Network Walking in PostGIS

One of the new features in PostgreSQL 8.4 was the “WITH RECURSIVE” clause available for queries. It allows you to define a subquery based on a recursive term — fancy language for a function that calls itself. One of the favorite uses of recursion is walking a network. Geospatial applications use networks all the time: electrical grids, stream systems, and storm sewers are all directed networks (they have unidirectional flow).

Here’s an example of network walking using a simple collection of segments. As is common in many GIS applications, the segment are implicitly connected — their end points are coincident with the start points of other segments.

CREATE TABLE network ( 
  segment geometry, 
  id integer primary key 

INSERT INTO network VALUES ('LINESTRING(1 1, 0 0)', 1);
INSERT INTO network VALUES ('LINESTRING(2 1, 1 1)', 2);
INSERT INTO network VALUES ('LINESTRING(1 2, 1 1)', 3);
INSERT INTO network VALUES ('LINESTRING(3 1, 2 1)', 4);
INSERT INTO network VALUES ('LINESTRING(3 2, 2 1)', 5);
INSERT INTO network VALUES ('LINESTRING(2 3, 1 2)', 6);
INSERT INTO network VALUES ('LINESTRING(1 3, 1 2)', 7);
INSERT INTO network VALUES ('LINESTRING(4 2, 3 2)', 8);
INSERT INTO network VALUES ('LINESTRING(3 4, 2 3)', 9);
INSERT INTO network VALUES ('LINESTRING(2 4, 2 3)', 10);
INSERT INTO network VALUES ('LINESTRING(1 4, 1 3)', 11);
INSERT INTO network VALUES ('LINESTRING(4 3, 4 2)', 12);
INSERT INTO network VALUES ('LINESTRING(4 4, 3 4)', 13);

CREATE INDEX network_gix ON network USING GIST (segment);

Visually, the network looks like this:


To walk our network, use a WITH clause that starts with one segment, then repeatedly adds the next downstream segment to the collection. In our case, the “next downstream segment” is defined as a segment whose start point is close to the end point of the current segment. We’ll walk down from segment 6.

WITH RECURSIVE walk_network(id, segment) AS (
  SELECT id, segment 
    FROM network 
    WHERE id = 6
  SELECT, n.segment
    FROM network n, walk_network w
    WHERE ST_DWithin(
FROM walk_network

Which returns:

(3 rows)

From 6 to 3 to 1, correct! Once we have our walker producing the results we want, we can wrap more PostGIS and PostgreSQL functions around the walker to produce a finished product. Here’s a function that takes in an edge identifier and outputs a linestring based on the downstream path.

CREATE OR REPLACE FUNCTION downstream(integer)
RETURNS geometry
AS '
WITH RECURSIVE walk_network(id, segment) AS (
    SELECT id, segment FROM network WHERE id = $1
    SELECT, n.segment
    FROM network n, walk_network w
    WHERE ST_DWithin(ST_EndPoint(w.segment),ST_StartPoint(n.segment),0.01)
SELECT ST_MakeLine(ST_EndPoint(segment))
FROM walk_network

And here’s the function in action, generating the downstream path from segment 12.

SELECT ST_AsText(Downstream(12));
 LINESTRING(4 2,3 2,2 1,1 1,0 0)
(1 row)

Check the generated path against our network picture – looks good!

Path 12

SXSW Geo in a Nutshell

From Mapping and Geolocation: Turnkey Approaches You Need to Know [MP3] at 19:55.

I think that, at least for us here [at SXSW] this week, Foursquare and Gowalla have been at the center of the universe for a little while.

And I think that [is because] it is something to do with the fact that it’s been a problem we’ve been trying to solve forever. You know you’ve been thinking “wouldn’t it be great if I knew where my friends are so I could find them and we could hang out more” for years and so now this is finally here.

So not only is it an easy way to do something, and solves a problem that we we’ve been trying to fix forever, it’s the first time that location is kind of useful beyond maps. Everyone understands that you need location in maps, because you have to get from point A to point B … I want to know where I am so I can broadcast it, because it’s cool that I go to cool conferences (um, isn’t it?), and I want my friends to know where I am, and I want to be able to find where they are.

I’m over the hill and I’m not even 40. Now get the hell off my lawn!

How to Survive Foo Camp (Introvert Edition)

I just read the 2010 edition of Scott Berkun’s regular Foo Camp review. It’s very good, and makes me want to amplify a couple points for future, introverted attendees.

First, the social dynamics are much as he describes, although I would certainly not argue as he does that pretense is “eliminated”. It is somewhat attenuated. The attending population can be segmented in lots of ways, but here’s mine:

Foo Regulars Foo Newbies
Extroverts Introverts

Extroverts should have a grand time, lots of people to talk to. Regular attending introverts can lean on existing acquaintances when burnt out. But if you, like me, are an introvert, and you aren’t part of the “in group” of repeat attendees, you may find yourself feeling socially isolated and very very tired, in the midst of a happy group of very energetic people. You might begin to resent them.

Foo is what it is, though. It is an opportunity to connect with some people you’d otherwise never meet, so all you can do is arm yourself before-hand with some tools and expectations to avoid having a negative experience.

Social Fatigue

First of all, bad news, the Cocktail Party dynamic is going to be a major mode of interaction. “So, what do you do?” You’re going to have to answer that (and ask that) a lot, and people will filter you based on your answer. It’s best to have an answer that is interesting to a wide swathe of people outside your field. The population of askers will be intellectually sophisticated (Michael Arrington excluded) so the answers that generally work can be surprising.

For me the general truth “I work for OpenGeo doing spatial database programming” was not effective at all. But a specific instance “I’m working on spherical geometry algorithms for location data” worked pretty well. (Unfortunately I was too dazed to really parse that fact until after I left.) Anyhow, on review, the second explanation has lots of potential follow-ups from “why?” for people who understand “location data” to “what’s that?” for people who don’t. The first explanation is too mushy.

Back to the bad news. Because a lot of your interactions are going to be draining first encounters, you’re going to run out of gas pretty fast. Find a seat by the fire, get a quiet corner, and don’t feel guilty about not talking. You’re tired. You can’t. Go to bed early, it’s OK – the alternative is just going to make you feel worse.

Note to Parents: Your early-to-bed-early-to-rise conditioning comes in handy sometimes. You can get up early, get a coffee, and join the other parents for a quiet, introvert friendly, discussion around the fire pit while all the 20-something future masters of the universe are sleeping off their hangovers.

The “Formal” Program

Sessions are easy. There’s structure, you can talk or not. For a first time attendee, I think this piece of wisdom on the Foo wiki (“Find people whose work you have no supposed interest in and go to their talks” – Chris DiBona) is absolutely wrong.

You can bring the most value to the group, and meet the people who are going to be of most direct value to you in the future by going to sessions that are directly interesting to you, that fall in your area of expertise, that you have passion for. If you’re going to Foo over and over again like Chris, then you have the luxury of sampling. I (foolishly) took the advice and missed going to database sessions with folks like Brian Aker, who says something worth writing down (if you’re a database geek) about every 30 seconds. Bad, bad decision on my part.

Blowhards: There will be blowhards. Statistically speaking, the larger the session, the more likely there will be a blowhard in your session. Scott Berkun’s 2009 post mentions them, and I like his idea of the “anonymous gong” to help the blowhard achieve self-awareness.

Bring a Pen and Paper

Laptops and iPads are heavy and take time to start up and get into data entry mode. Paper is light and fast. There will be names and ideas you want to remember. Precisely when the nuggets fall from the sky is unpredictable, but you probably won’t be sitting down with your device at the ready.


Own your inferiority complex. Yes, you’re inferior. Suck it up. Unfortunately, this is “do as I say, not as I do” advice, because I wasn’t very good at it.

I didn’t tell Kathy Sierra that her 2009 Business of Software talk is currently conditioning all my thinking about building the OpenGeo Suite materials. I just glanced at her out of the corner of my eye.

I did, however, have a nice time talking with (well, listening to) Mitch Kapor. Feed them some rope, provide them a context to tell you what’s on their mind. A general request for advice on a general topic will usually do. I asked Kapor about economic development. I should have asked Sierra about our own product issues.

Invisible Celebrities: I actually talked to Chad Dickerson, but I never connected the dots until afterwards that he wrote the “CTO Corner” column in InfoWorld, back when it was a paper publication. That column was the only reason I kept receiving the magazine, it made me feel sane (I am not alone!) to be advocating open source, which was very much a minority position at the time. I would have liked to have told him that.

Meeting People You Want To Meet

If you look at the list and see a name you absolutely want to meet, track them down ahead of time, get their contact information and then contact them during the conference and arrange a time.

The venue is deceptively intimate, but 250 people is a lot of people. You may not randomly run into the person you are looking for. You probably will not. I was absolutely looking forward to talking with James Dixon about open source business models. I even staked out the main passage ways, during transition times. I did not see the man! (Here’s where having one of those “iPhone” things would have been handy.)

Surprising Social Norms: Either there is a Silicon Valley thing going on that I’m not acclimated to, or this behavior is a form of status advertisement for high status individuals, but a number of times I saw people pull out their smart phones and check messages while other people were talking to them. I had not encountered this before, though I suppose it is just a variation on the equally noxious answering-your-cell-phone-in-the-middle-of-a-conversation. (Both should be grounds for an immediate caning.)

Us and Them

People sometimes ask, “What can I do to be invited back?” and your best bet is to make a (positive) impression by engaging and presenting.
– Foo Camp Wiki

In general, it’s going to be hard to make a good impression if you have no psychological energy. And it’s difficult to plan for a session or an Ignite talk when you have no idea what the audience is going to find interesting.

However, having seen the audience, I can now (post-facto (arg!)) offer a generic recipe for an interesting topic: something that is foundational in your specialty field but mostly unknown in the larger world. In my case a talk about general principles of geography, like Tobler’s Law or the ecological fallacy or some topical examples of how to lie with maps would have gone over well at Ignite.

It’s worth noting, given the mix of regular repeat attendees versus new attendees, that the criteria are not strictly meritocratic – obviously you can also get invited back by being intrinsically “important” in some way to the O’Reilly organization. The “engaging and interesting” criterion is only applied to some.

In Conclusion

Like many of life’s memorable experiences (“there was this time I hiked to the top of a mountain in the rain…”), there is a strong possibility that, as an introvert in a highly social milieu without a group of friends to lean on, you might find Foo Camp difficult and unenjoyable in the moment. You might want to leave, a lot of the time. But if you stick with it, you’ll come out with some good memories and look back on it as an important experience. You’ll also meet some very friendly people who will make you feel welcome despite yourself. Give it a shot.

Shout-out: Thanks to the people who made me feel not like a stranger at Foo Camp, despite my acting like one. Selena Deckelmann, Cary Davis, Joe Hughes, Matt Cutts, Nat Torkington, Shel Kaphan, Toby Boudreaux, Andrew McLaughlin, Laurel Ruma, Emily Jacobi and many others.

Nerds Redux

I had a chance to re-present my FOSS4G 2009 keynote talk at the Rendezvous OSGeo a Quebec last week, and thanks to the good work of the FOSSLC team, there’s now a pretty clean online video of it.

PostGIS @ FOSS4G 2010

One of the things that tickled me about the presentations selected for FOSS4G 2010 was the number of talks in the list that specifically mention PostGIS:

  • Beyond PostGIS - New developments in Open Source Spatial Databases
  • Introducing PostGIS WKT Raster: Seamless raster/vector operations in a spatial database
  • Introduction of flood evacuation route search system?using QGIS,PostGIS,GRASS and PgRouting
  • Moving from Oracle/ArcGIS to PostGresql/PostGIS
  • PostGIS meets the third dimension
  • PostGIS WKT Raster. An Open Source alternative to Oracle GeoRaster
  • Running long and complex processes with PostGIS
  • The State of PostGIS
  • Tips for the PostGIS Power User

The last two are mine! And one is about not using PostGIS. But still, some interesting talks on the use and future of my favourite spatial database.