Take this Tree and Pack it

Noticing this a little late, but have a peak at these posts from Chris Hodgson about how the R-Tree fails for variable density GIS data, and his approach to a packing process. Unfortunately, packing is a post-facto process, and it’s not clear to me how we would do it with the GiST infrastructure that undergirds the PostGIS database. But it’s nice to see a good R-Tree and a reminder of just how ugly they can get under the covers.

FOSS4G Reminder

OK, this is the last time I’m going to remind you: FOSS4G 2010 is coming up fast. September 6-9 in Barcelona, Spain. The presentation call was massive (360 submissions for 120 slots) as was the workshop call. So register soon and make your hotel reservations while you can! That is all.

On Cable Modems

I had cable guys in my house turning on basic cable, and they noticed that my cable modem was old. When I say “old”, I mean “I think I got it when we moved into the house almost 10 years ago”. So they said, “here, have a new one”. My maximum download speed quadrupled overnight. If you’ve got an old cable modem, figure an excuse to get a new one.

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.id, 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.id, 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!