Calling all Technoweenies...

16 Aug 2010

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

06 Aug 2010

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

27 Jul 2010

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

22 Jul 2010

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

21 Jul 2010

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
  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!