PostgreSQL 路径规划插件 pgruoting 介绍-阿里云开发者社区

开发者社区> 阿里云数据库> 正文
登录阅读全文

PostgreSQL 路径规划插件 pgruoting 介绍

简介:
    我们都知道PostgreSQL利用PostGIS插件,善于处理LBS相关的业务.
    PostGIS是对象关系型数据库系统PostgreSQL的一个扩展,PostGIS提供如下空间信息服务功能:空间对象、空间索引、空间操作函数和空间操作符。同时,PostGIS遵循OpenGIS的规范。

 PostGIS的优势
一: 支持所有的空间数据类型,这些类型包括:点(POINT)、线(LINESTRING)、多边形(POLYGON)、多点(MULTIPOINT)、多线(MULTILINESTRING)、多多边形(MULTIPOLYGON)和集合对象集(GEOMETRYCOLLECTION)等。PostGIS支持所有的对象表达方法,比如WKT和WKB 

二: 支持基于这些数据类型的计算
1 数据存取和构造方法
2 供简单的空间分析函数
3 提供了一系列的二元谓词(如Contains、Within、Overlaps和Touches)用于检测空间对象之间的空间关系,同时返回布尔值来表征对象之间符合这个关系
4 提供了空间操作符(如Union和Difference)用于空间数据操作

本文带来的PostgreSQL新的插件pgruoting是基于PostGIS的.
pgruoting 提供一套函数,用于满足用户在LSB服务中典型的路径规划方面的需求.
RDS PG 12月版本也会支持这个插件.
下面详细介绍改插件的典型用法.

A. 该插件依赖PostGIS,创建它需要先创建 pgruoting.
create extension postgis;
create extension pgrouting; 

B. 创建示例表和示例数据

CREATE TABLE edge_table ( id serial,
dir character varying,
source integer,
target integer,
cost double precision, reverse_cost double precision, x1 double precision,
y1 double precision, x2 double precision, y2 double precision, the_geom geometry
); 

INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,0, 2,1);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES (-1, 1, 2,1, 3,1);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES (-1, 1, 3,1, 4,1);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,1, 2,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1,-1, 3,1, 3,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 0,2, 1,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 1,2, 2,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,2, 3,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 3,2, 4,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,2, 2,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1,-1, 3,2, 3,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1,-1, 2,3, 3,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1,-1, 3,3, 4,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,3, 2,4);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 4,2, 4,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 4,1, 4,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 0.5,3.5, 1.999999999999,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 3.5,2.3, 3.5,4);

9523dcb3d3d4a1b69fea95dcdaab9ab7718cda1a

这里的(x1,y1),(x2,y2)分别对应两个点,也就是一条线段
我们把连个点连接起来,作为一条线,假想为道路,我们最后得到的最短路径,就是由连续的线段组成.

UPDATE edge_table SET the_geom = st_makeline(st_point(x1,y1),st_point(x2,y2)),
dir = CASE WHEN (cost>0 and reverse_cost>0) THEN ’B’ -- both ways
WHEN (cost>0 and reverse_cost<0) THEN ’FT’ -- direction of the L 
WHEN (cost<0 and reverse_cost>0) THEN ’TF’ -- reverse direction 
ELSE ’’ END;

使用下列函数,格式化拓扑数据(source和target列),为我们的之后的路径规划做铺垫.
SELECT pgr_createTopology(’edge_table’,0.001); 

执行之后,会产生一个表 edge_table_vertices_pgr.他也在edge_table表的source和target列中表现.他们是一组点的组合.

dc082b9523cceb636a9a6e66871b3531c92749d4

接下来,我们用pgr_dijkstra函数计算出, edge_table_vertices_pgr中点1 到 11间的最短距离.

改函数的实现核心是Dijkstra 算法,它又叫迪科斯彻算法(Dijkstra),算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离.
Dijkstra 算法可以用来找到两个城市之间的最短路径。

实现相关信息请参考
1 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
2 http://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn


我们来计算下1到9间的最短距离
SELECT seq, id1 AS node, id2 AS edge, cost FROM
pgr_dijkstra(' 
SELECT  id AS id,
source::integer, 
target::integer, 
cost::double precision AS cost
FROM edge_table', 
1, 11, false, false);

得到结果
 seq | node | edge | cost 
-----+------+------+------
   0 |    1 |    1 |    1
   1 |    2 |    4 |    1
   2 |    5 |    8 |    1
   3 |    6 |    9 |    1
   4 |   11 |   -1 |    0
(5 rows)

意思是,按照seq的顺序,先后经过节点1,2,4,5 最后到达11.

我们把按照顺序把1,2,5,6,11 的列the_geom连接起来,也就是是我们最短路径.
可以参考SQL

create table line(id serial,the_geom geometry);
insert into line (the_geom) select ST_MakeLine(ARRAY (select the_geom
from (SELECT seq, id1 AS node FROM pgr_dijkstra(
'SELECT  id AS id,
 source::integer, 
target::integer, 
cost::double precision AS cost 
FROM edge_table', 1, 11, false, false))path, edge_table_vertices_pgr p
where path.node = p.id order by seq));

我们把数据用图形展示出来,图中彩色线段就是最短路线的走向.

802191527758e8ff994a4dc092182e9f24e58c98



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
阿里云数据库
使用钉钉扫一扫加入圈子
+ 订阅

帮用户承担一切数据库风险,给您何止是安心!

官方博客
链接