Faglig /
Tools/libraries used
- PostgreSQL w/ PostGIS and pgRouting extenstions
- uDig as graphical editor
- SRID = 32631 (WGS84, UTM zone 31N) [meter, starts at E=0)
- Doesn't actually need a projection - but useful with meters
SQLs
- Get nearest nodes from an arbitrary point. Need to run this on every update to a location (moving _and_ stationary) to store (cache) the nearest node in the database for easier manipulation of data.
- Constraints; Node and point must be in the same polygon (i.e. room)
- Lacks; Nearest node is calculated by euclidean distance (i.e. mathematical nearest). May fail under extreme conditions (wiggly/snake room) - however good enough!
Could be nice with a PL/PGSQL function - at least a good service interface is required!
- Function for finding nearest node to arbitrary (X,Y)-pair
CREATE OR REPLACE FUNCTION alexanno_find_nearest_node("X" double precision, "Y" double precision)
RETURNS integer AS
$BODY$SELECT node.id AS node_id
FROM node, area
WHERE ST_Within(GeomFromText('POINT('||CAST($1 AS text)||' '||CAST($2 AS text)||')', 32631), area.polygon) = 't'
ORDER BY distance(GeomFromText('POINT('||CAST($1 AS text)||' '||CAST($2 AS text)||')', 32631), node.point) ASC
LIMIT 1
$BODY$
LANGUAGE 'sql' VOLATILE
COST 100;
ALTER FUNCTION alexanno_find_nearest_node(double precision, double precision) OWNER TO postgres;
RETURNS integer AS
$BODY$SELECT node.id AS node_id
FROM node, area
WHERE ST_Within(GeomFromText('POINT('||CAST($1 AS text)||' '||CAST($2 AS text)||')', 32631), area.polygon) = 't'
ORDER BY distance(GeomFromText('POINT('||CAST($1 AS text)||' '||CAST($2 AS text)||')', 32631), node.point) ASC
LIMIT 1
$BODY$
LANGUAGE 'sql' VOLATILE
COST 100;
ALTER FUNCTION alexanno_find_nearest_node(double precision, double precision) OWNER TO postgres;
SELECT node.id AS node_id, area.id AS area_id,
distance(GeomFromText('POINT(0.2 3)', 32631), node.point) AS distance
FROM node, area WHERE ST_Within(GeomFromText('POINT(0.2 3)', 32631), area.polygon) = 't' ORDER BY distance ASC LIMIT 1
distance(GeomFromText('POINT(0.2 3)', 32631), node.point) AS distance
FROM node, area WHERE ST_Within(GeomFromText('POINT(0.2 3)', 32631), area.polygon) = 't' ORDER BY distance ASC LIMIT 1
Shortest path
- View that contains the shortest path between every node (to and from) in the database (could be very computational intensive! As it is n^2 rows in the view.)
- Is a bit lazy - it is probably a bit faster to run the shortest path calculation (from-to) several times. However. No one knows what tricks postgres has on View performance! (i.e. go for the lazy version and use the view!)
CREATE OR REPLACE VIEW shortest_path_all_all AS
SELECT source.id AS source, target.id AS target, ( SELECT sum(subq.cost) AS sum
FROM shortest_path('SELECT edge_id AS id, source::int4,
target::int4, cost::double precision FROM node_edge'::text, source.id, target.id, false, false) subq(vertex_id, edge_id, cost)) AS cost
FROM node source, node target;
--ALTER TABLE shortest_path_all_all OWNER TO postgres;
SELECT source.id AS source, target.id AS target, ( SELECT sum(subq.cost) AS sum
FROM shortest_path('SELECT edge_id AS id, source::int4,
target::int4, cost::double precision FROM node_edge'::text, source.id, target.id, false, false) subq(vertex_id, edge_id, cost)) AS cost
FROM node source, node target;
--ALTER TABLE shortest_path_all_all OWNER TO postgres;
- Find shortest path from source_node_id to target_node_id (source/target)
SELECT SUM(cost) FROM (SELECT * FROM shortest_path('SELECT edge_id AS id, source::int4,
target::int4, cost::double precision
FROM node_edge',5, 4, false, false)) AS subquery
target::int4, cost::double precision
FROM node_edge',5, 4, false, false)) AS subquery
- Find shortest path from one node to everyone else (for instance from users node to all RB's nodes; replace FROM node with appropriate table/constraints)
SELECT *, (SELECT SUM(cost) FROM shortest_path('SELECT edge_id AS id, source::int4,
target::int4, cost::double precision
FROM node_edge',5, node.id, false, false) AS subQ) AS subq2
FROM node
target::int4, cost::double precision
FROM node_edge',5, node.id, false, false) AS subQ) AS subq2
FROM node
- More generic - Could for instance be patients to a doctor
SELECT *, (SELECT SUM(cost) FROM shortest_path('SELECT edge_id AS id, source::int4,
target::int4, cost::double precision
FROM node_edge',(SELECT id FROM node AS n WHERE n.id = 4), node.id, false, false) AS subQ) AS subq2
FROM node
target::int4, cost::double precision
FROM node_edge',(SELECT id FROM node AS n WHERE n.id = 4), node.id, false, false) AS subQ) AS subq2
FROM node
Notepad
(SELECT SUM(cost) FROM (SELECT * FROM shortest_path('SELECT edge_id AS id, source::int4,
target::int4, cost::double precision
FROM node_edge',5, 4, false, false)) AS subquery)
SELECT
(SELECT node.id AS from_id
FROM node, area
WHERE ST_Within(GeomFromText('POINT(0.2 3)', 32631), area.polygon) = 't'
ORDER BY distance(GeomFromText('POINT(0.2 3)', 32631), node.point) ASC
LIMIT 1) AS from_id,
(SELECT node.id AS from_id
FROM node, area
WHERE ST_Within(GeomFromText('POINT(0.6 1)', 32631), area.polygon) = 't'
ORDER BY distance(GeomFromText('POINT(0.6 1)', 32631), node.point) ASC
LIMIT 1) AS to_id
Backlinks: