[pgrouting-users] pgrouting Dijkstra: non-vertex data routing

Hello everyone,

I have some data samples, they are some traffic accident locations (have shape files) I really want to use the dijkstra function of pgrouting to look into their shortest distances between each other. However, I noticed that dijkstra requires all the points need to be the vertices of a topology. But obviously my data points are not the vertices of the road network. Is there any way to integrate my data points to the road network and make them vertices too? What is the good approach to route non-vertex data like this? Thank you.

Yang Zhang

Hi Yang Zhang,

The links below might be helpful for your question.

http://gis.stackexchange.com/questions/104286/pgrouting-calculating-route-from-point-to-point

http://gis.stackexchange.com/questions/54314/segment-lines-according-to-point-using-pgrouting

···

Best regards,

Bomp

Dr.Sittichai Choosumrong

Lecturer,
Geography and Geographic Information Science (GISci)
Department of Natural Resources and Environment,
Faculty of Agriculture, Natural Resources and Environment,

Naresuan University, Thailand 65000

Office: +66 55 962753

Mobile: +66 91-767-2963
email: sittichaic@nu.ac.th

■□■□■□■□■□■□■□■□■

Hello Yang Zhang

There are some good resources on anitagraser.com and this post shows how to associate a point (in this case airports) to the nearest network node and then solve the routing problem: http://anitagraser.com/2011/02/12/drive-time-isochrones/

The first bit of SQL will do what you want, I think.

ALTER TABLE airport

ADD COLUMN nearest_node integer;

CREATE TABLE temp AS

SELECT a.gid, b.id, min(a.dist)

FROM

(SELECT airport.gid,

min(distance(airport.the_geom, node.the_geom)) AS dist

FROM airport, node

GROUP BY airport.gid) AS a,

(SELECT airport.gid, node.id,

distance(airport.the_geom, node.the_geom) AS dist

FROM airport, node) AS b

WHERE a.dist = b. dist

AND a.gid = b.gid

GROUP BY a.gid, b.id;

UPDATE airport

SET nearest_node =

(SELECT id

FROM temp

WHERE temp.gid = airport.gid);

Hope that helps

Ross

Ross McDonald | GIS Data Coordinator | Resources Department, IT Division | Angus Council, Angus House, Orchardbank Business Park, Forfar, DD8 1AT

T: 01307 476419 | F: 01307 476401 | E: mcdonaldr@angus.gov.uk

···

Hello everyone,

I have some data samples, they are some traffic accident locations (have shape files) I really want to use the dijkstra function of pgrouting to look into their shortest distances between each other. However, I noticed that dijkstra requires all the points need to be the vertices of a topology. But obviously my data points are not the vertices of the road network. Is there any way to integrate my data points to the road network and make them vertices too? What is the good approach to route non-vertex data like this? Thank you.

Yang Zhang

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

There are some good resources on anitagraser.com and this post
shows how to associate a point (in this case airports) to the
nearest network node and then solve the routing problem:
http://anitagraser.com/2011/02/12/drive-time-isochrones/

Be aware that the blog post is relatively old and uses an outdated
version of pgRouting.

Also the function mentioned there does not limit the search area by
BBOX, so for large tables it might be slow(er).
It's better to use KNN to find nearest nodes, and you can find an
example in the workshop:
http://workshop.pgrouting.org/chapters/wrapper.html#route-between-lat-lon-points-and-return-ordered-geometry-with-heading

SELECT id::integer FROM ways_vertices_pgr
    ORDER BY the_geom <-> ST_GeometryFromText(POINT(x y),4326) LIMIT 1;

Another option is to use TRSP function, because it does not require to
start from a node but can start from "within" an edge:
http://docs.pgrouting.org/2.0/en/src/trsp/doc/index.html#trsp

Best regards,
Daniel

- --
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.info
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQEcBAEBCAAGBQJVsLvlAAoJEHjh5kk/zBG0hqkIAIHHkPt5E4XLuW9dASzdNlgH
N6GifNmVsA81hDT9k+wiNS85061rEfcryWKofsNqFJzoBPxEqr3w/N/zmYkKzF9f
mnfDEWNMeutULvMrA8jps8uGQ6iav+f7vLWO4jMDRskSfqUrFERnV1sZ7OHEV4Tt
4+8ICsv1hbJqF7Kk1R/VpYjGkbWTuf8b+uFvANMoL+Te6vaggGtngoB81kITPbO2
pdPt0F5XHFhNdjKxMfBoqsVqCfV1/8cTEI4wx+3EF0sdpjOmpEpm3OtTTPjD5+Dt
lzbWxlYM7yd2tOLY2QVBO6v+8jbHwpcg1/Pz3OWsFWVntef8T4NPm9jLNafUmwE=
=zApP
-----END PGP SIGNATURE-----