3

I would like to know if it is possible to make a graph with pgrouting 1.05 on polygons. What I mean is that I have to make a graph on a database without roads but with polygon geometry. I would like to make a graph on this geometry.

Thanks for your help and I'm sorry for my english

6

Okay, I looked further into the idea of Steve above. I'll try to demontrate his idea in a QGIS/PostGIS/pgrouting environment. You will get results such as this:

enter image description here

First, let's assume you have a geodata table with your shelves/obstacles looking like this (I made them up for this purpose):

enter image description here

Make sure your shelf data is in a projected coordinate system with meters as units (I used a Mercator CRS(SRID=3785). If it's in lat/lng you have to reproject your data.

Then, open up your database connection and import your shelves geodata (either use a QGIS plugin like SPIT or the command line tool shp2pgsql). Now, create a point grid. Use the function from here: How to create regular point grid inside a polygon in Postgis? :

CREATE OR REPLACE FUNCTION makegrid(geometry, integer)
RETURNS geometry AS
'SELECT ST_Collect(ST_SetSRID(ST_POINT(x,y),ST_SRID($1))) FROM 
generate_series(floor(st_xmin($1))::int, ceiling(st_xmax($1)-st_xmin($1))::int, $2) as x
,generate_series(floor(st_ymin($1))::int, ceiling(st_ymax($1)-st_ymin($1))::int,$2) as y 
where st_intersects($1,ST_SetSRID(ST_POINT(x,y),ST_SRID($1)))'
LANGUAGE sql;

Following SQL gives you a table containing a point grid with spacing of one meter between each point:

CREATE SEQUENCE seq;
CREATE TABLE grid AS 
SELECT nextval('seq') AS gid, (ST_Dump(makegrid(ST_Transform(ST_SetSRID(ST_Extent(the_geom),3785),3785),1))).geom AS the_geom FROM shelves;

This grid only covers the extent of your shelves file:

enter image description here

Now remove every grid point which is intersected by/contained by a shelf (you could also do this directly in the grid query above) and create an updated table:

CREATE TABLE open_space_grid AS 
SELECT 
  grid.*
FROM 
grid left join
  shelves ON
  ST_Intersects(grid.the_geom,shelves.the_geom)
WHERE shelves.gid is null;

this should give you this:

enter image description here

Now you have to connect the points to form a network. This query connects each point pair with a distance of one meter, forming a grid network.

CREATE TABLE edges AS
SELECT nextval('seq') AS gid, the_geom 
FROM (
    select ST_SetSRID(ST_MakeLine(a.the_geom, b.the_geom),3785) AS the_geom 
    FROM open_space_grid AS a,open_space_grid AS b) AS tmp WHERE ST_Length(ST_Transform(ST_SetSRID(tmp.the_geom,3785),3785)) = 1;

Then throw out all duplicates:

DELETE FROM edges 
WHERE gid IN (
    SELECT e1.gid 
    FROM edges e1, edges e2
    WHERE st_equals(e1.the_geom, e2.the_geom)
    AND e1.gid < e2.gid
);

Now we are here:

enter image description here

Now create the routable network (Everything here taken from http://underdark.wordpress.com/2011/02/07/a-beginners-guide-to-pgrouting/)

CREATE OR REPLACE VIEW net_ext AS
   SELECT *, ST_StartPoint(ST_SetSRID(the_geom,3785)) as startpoint, ST_EndPoint(ST_SetSRID(the_geom,3785)) as endpoint
   FROM edges;

CREATE TABLE node AS 
   SELECT row_number() OVER (ORDER BY foo.p)::integer AS id, 
          foo.p AS the_geom
   FROM (         
      SELECT DISTINCT net_ext.startpoint AS p FROM net_ext
      UNION 
      SELECT DISTINCT net_ext.endpoint AS p FROM net_ext
   ) foo
   GROUP BY foo.p;

CREATE TABLE network AS
   SELECT a.*, b.id as start_id, c.id as end_id, ST_Length(ST_MakeLine(a.startpoint, a.endpoint)) as length
   FROM net_ext AS a
      JOIN node AS b ON a.startpoint = b.the_geom
      JOIN node AS c ON a.endpoint = c.the_geom;

Now try it out (e.g. execute the query below in QGIS via pgQuery). Input your start and end node id's (in my case, those are 1 and 590):

SELECT * 
   FROM network
   JOIN
   (SELECT * FROM shortest_path('
      SELECT gid AS id, 
          start_id::int4 AS source, 
          end_id::int4 AS target, 
          length AS cost
      FROM network',
      1,
      590,
      false,
      false)) AS route
   ON
   network.gid = route.edge_id;
3
  • Thanks a lot for your help. It's very very kind of you :)
    – raphael
    May 10 '12 at 12:20
  • Sure, no problem. It was a rather interesting task and I was curious how it could be solved ;)
    – chriserik
    May 10 '12 at 12:41
  • Excellent one though I found a problem in deleting the duplicates. "e1.gid < e2.gid" is fully deleting certain grid nodes from the edges table in a pattern. Solution might be to have at-least one row for each grid node but I am not sure how to write the query. Any help would be appreciated.
    – kaja
    Sep 2 '15 at 15:53
3

From your comment in an earlier answer it sounds like the polygons you have are not the available routes, but the boundaries of areas where travel is not possible. In the space between the shelves you could create a grid (or "mesh") with lines and use that as your routing network.

Here is an example of how you might create that grid: How to create regular point grid inside a polygon in Postgis?

2
  • I don't see how to do that? :s
    – raphael
    May 9 '12 at 14:36
  • Can you be more specific? What don't you see how to do? Creating a grid between your polygons?
    – Steve Horn
    May 9 '12 at 17:41
2

Just to clarify - your roads are polygons? I'm afraid you have to convert them to lines. It's the nature of a routable network to only have edges (lines) and nodes (points). As for how to convert polygons to lines, look here: Simplifying polygons to linestring?

2
  • My roads are not polygons. Actually, I'm working on a project and I have to create a route in a building between some shelves. In my database I only have the shelves with a polygon geometry and I don't really know how to do. Thanks a lot for your answer
    – raphael
    May 9 '12 at 12:24
  • Maybe you could calculate the centroids of your shelves and connect them based on a nearest-neighbour solution. Then you would have a routable network. Of course, this would not take obstacles into account.
    – chriserik
    May 9 '12 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.