Calling all Technoweenies...

Did you know that OpenGeo is hiring a software engineer? It’s true. Let’s build something beautiful together.

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:

Network

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
UNION ALL
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 id
FROM walk_network

Which returns:

 id
---
  6
  3
  1
(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
LANGUAGE sql
AS '
WITH RECURSIVE walk_network(id, segment) AS (
SELECT id, segment FROM network WHERE id = $1
UNION ALL
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
'
IMMUTABLE;

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

SELECT ST_AsText(Downstream(12));
            st_astext
---------------------------------
 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