pgRouting 模块实践 ================== 简介 ---- pgRouting 扩展了 PostGIS/PostgreSQL 地理空间数据库以提供地理空间路由和其他网络分析功能。 该库包含以下功能: - 最短路径算法 - 双向算法 - Dijkstra算法的多种应用 - 距离计算 预备知识 -------- 在开始之前,我们会先介绍一下预备的知识,如果你已经对图和图的相关算法有了充足的了解,可以略过此部分。 **图的定义** 图是由一些\ ``点(vertices)``\ 和\ ``边(edges)``\ 组成的。可以分为: - 无向图 - 无向简单图 - 有向图 - 有向简单图 有些图的理论中还会包含权重这个概念。可以简单的理解为两点之间的距离。 在 pgRouting 中有几种方式可以表示图: - 包含权重的: ``(id, source, target, cost)`` - 包含双向权重的 ``(id, source, target, cost, reverse_cost)`` 其中: +------------------+--------------------------------------------------+ | 标签 | 含义 | +==================+==================================================+ | ``id`` | 边的标识符,要求是数据库中的一个数据 | +------------------+--------------------------------------------------+ | ``source`` | 边起点的标识符 | +------------------+--------------------------------------------------+ | ``target`` | 边终点的标识符 | +------------------+--------------------------------------------------+ | ``cost`` | 从起点到终点的权重(当 cost | | | 是负数时,表示这条边并不存在于图中,同时 cost | | | 在一个查询中必须存在) | +------------------+--------------------------------------------------+ | ``reverse_cost`` | 从终点到起点的权重(当 reverse_cost | | | 为负数时,表示这条边并不存在于图中) | +------------------+--------------------------------------------------+ **图示例** - 有向图(cost) .. code:: sql SELECT * FROM (VALUES (1, 1, 2, 5), (2, 1, 3, -3)) AS t(id, source, target, cost); id | source | target | cost ----+--------+--------+------ 1 | 1 | 2 | 5 2 | 1 | 3 | -3 |image8| 其中 id 为 2 在 cost 为负数,所以在图中没有这个边。 - 无向图(cost) .. code:: sql SELECT * FROM (VALUES (1, 1, 2, 5), (2, 1, 3, -3)) AS t(id, source, target, cost); id | source | target | cost ----+--------+--------+------ 1 | 1 | 2 | 5 2 | 1 | 3 | -3 |image1| 与上面的图相比结点 1 和 节点 2 之间的连线时没有指向的。 **有向图(cost, reverse_cost)** .. code:: sql SELECT * FROM (VALUES (1, 1, 2, 5, 2), (2, 1, 3, -3, 4), (3, 2, 3, 7, -1)) AS t(id, source, target, cost, reverse_cost); id | source | target | cost | reverse_cost ----+--------+--------+------+-------------- 1 | 1 | 2 | 5 | 2 2 | 1 | 3 | -3 | 4 3 | 2 | 3 | 7 | -1 在上面的示例中,id 为 2(1->3) 和 3(3->2) 的两条边就是不存在的,因为\ ``cost`` 和 ``reverse_cost`` 是负数。 |image2| **无向图(cost, reverse_cost)** .. code:: sql SELECT * FROM (VALUES (1, 1, 2, 5, 2), (2, 1, 3, -3, 4), (3, 2, 3, 7, -1)) AS t(id, source, target, cost, reverse_cost); id | source | target | cost | reverse_cost ----+--------+--------+------+-------------- 1 | 1 | 2 | 5 | 2 2 | 1 | 3 | -3 | 4 3 | 2 | 3 | 7 | -1 (3 rows) 在上面的示例中,id 为 2(1--3) 和 3(3--2) 的边是不存在的,因为 ``cost`` 或 ``revrese_cost`` 为负数。 |image3| **不使用 geometry 的图** 人际关系,基因,文件依赖等问题都可以通过 pgRouting 来解决,这些问题一般都不需要 geometry 数据。现在我们使用 Wiki 上的一个示例来进行说明: |image4| 其中: - 找到从结点 1 到结点 5 的最短路径 - 是一个无向图 - 有 6 个结点 - 有 9 条边 1. 创建一个 pgroutetest 数据库 ,并创建扩展 .. code:: sql CREATE DATABASE pgroutetest; -- 连接到 pgroutetest 数据库 \c pgroutetest CREATE EXTENSION pgRouting CASCADE; 2. 创建表,字段如下: .. code:: sql CREATE TABLE wiki ( id SERIAL, source INTEGER, target INTEGER, cost INTEGER ); 3. 插入数据 .. code:: sql INSERT INTO wiki (source, target, cost) VALUES (1, 2, 7), (1, 3, 9), (1, 6, 14), (2, 3, 10), (2, 4, 15), (3, 6, 2), (3, 4, 11), (4, 5, 6), (5, 6, 9); 4. 寻找最短路径 为了解决这个问题我们使用了 Dijkstra 算法。 .. code:: sql SELECT * FROM pgr_dijkstra( 'SELECT id, source, target, cost FROM wiki', 1, 5, false); seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost -----+----------+-----------+---------+------+------+------+---------- 1 | 1 | 1 | 5 | 1 | 2 | 9 | 0 2 | 2 | 1 | 5 | 3 | 6 | 2 | 9 3 | 3 | 1 | 5 | 6 | 9 | 9 | 11 4 | 4 | 1 | 5 | 5 | -1 | 0 | 20 即最短路径为 1->3->6->5 5. 查看边的信息 .. code:: sql SELECT id, in_edges, out_edges FROM pgr_extractVertices('SELECT id, source, target FROM wiki'); id | in_edges | out_edges ----+----------+----------- 3 | {2,4} | {6,7} 5 | {8} | {9} 4 | {5,7} | {8} 2 | {1} | {4,5} 1 | | {1,2,3} 6 | {3,6,9} | **使用 Geometry 的图** 1. 创建一个数据库 .. code:: sql createdb sampledata psql sampledata -c "CREATE EXTENSION pgrouting CASCADE" 2. 导入数据 这里我们手动导入数据,当然,你可以使用其他工具来导入数据,例如: - shp2pgsql - ogr2ogr - osm2pgsql - osm2pgrouting 下图是一个整体的图说明: |image7| 3. 边 在数据库的设计中有一些字段会包含一个 ``reverse_`` 的前缀来表示相反的方向。 ==================== ========================== 字段 说明 ==================== ========================== ``id`` 唯一标识符 ``source`` 起始顶点标符 ``target`` 结束顶点标识符 ``cost`` 从起点到终点的成本(权重) ``capacity`` 从起点到终点的流量 ``reverse_cost`` 从终点到起点的成本(权重) ``reverse_capacity`` 从终点到起点的流量 ``x1`` 起始点 x 坐标 ``y1`` 起始点 y 坐标 ``x2`` 终止点 x 坐标 ``y2`` 终止点 y 坐标 ``geom`` 边的 geometry 数据 ==================== ========================== 创建边的表: .. code:: sql CREATE TABLE edges ( id BIGSERIAL PRIMARY KEY, source BIGINT, target BIGINT, cost FLOAT, reverse_cost FLOAT, capacity BIGINT, reverse_capacity BIGINT, x1 FLOAT, y1 FLOAT, x2 FLOAT, y2 FLOAT, geom geometry ); 插入数据: .. code:: sql INSERT INTO edges (cost, reverse_cost, capacity, reverse_capacity, geom) VALUES (1, 1, 80, 130, ST_MakeLine(ST_POINT(2, 0), ST_POINT(2, 1))), (-1, 1, -1, 100, ST_MakeLine(ST_POINT(2, 1), ST_POINT(3, 1))), (-1, 1, -1, 130, ST_MakeLine(ST_POINT(3, 1), ST_POINT(4, 1))), (1, 1, 100, 50, ST_MakeLine(ST_POINT(2, 1), ST_POINT(2, 2))), (1, -1, 130, -1, ST_MakeLine(ST_POINT(3, 1), ST_POINT(3, 2))), (1, 1, 50, 100, ST_MakeLine(ST_POINT(0, 2), ST_POINT(1, 2))), (1, 1, 50, 130, ST_MakeLine(ST_POINT(1, 2), ST_POINT(2, 2))), (1, 1, 100, 130, ST_MakeLine(ST_POINT(2, 2), ST_POINT(3, 2))), (1, 1, 130, 80, ST_MakeLine(ST_POINT(3, 2), ST_POINT(4, 2))), (1, 1, 130, 50, ST_MakeLine(ST_POINT(2, 2), ST_POINT(2, 3))), (1, -1, 130, -1, ST_MakeLine(ST_POINT(3, 2), ST_POINT(3, 3))), (1, -1, 100, -1, ST_MakeLine(ST_POINT(2, 3), ST_POINT(3, 3))), (1, -1, 100, -1, ST_MakeLine(ST_POINT(3, 3), ST_POINT(4, 3))), (1, 1, 80, 130, ST_MakeLine(ST_POINT(2, 3), ST_POINT(2, 4))), (1, 1, 80, 50, ST_MakeLine(ST_POINT(4, 2), ST_POINT(4, 3))), (1, 1, 80, 80, ST_MakeLine(ST_POINT(4, 1), ST_POINT(4, 2))), (1, 1, 130, 100, ST_MakeLine(ST_POINT(0.5, 3.5), ST_POINT(1.999999999999, 3.5))), (1, 1, 50, 130, ST_MakeLine(ST_POINT(3.5, 2.3), ST_POINT(3.5, 4))); 在 QGIS 中我们就可以看到插入的数据了 |image5| 1. 顶点 现在我们已经有了边的数据,我们就可以使用 ``pgr_extractVertices`` 函数将顶点信息保存在一个数据表中 .. code:: sql SELECT * INTO vertices FROM pgr_extractVertices('SELECT id, geom FROM edges ORDER BY id'); 现在,我们查看一下顶点的数据: .. code:: sql SELECT * FROM vertices; id | in_edges | out_edges | x | y | geom ----+----------+-----------+----------------+-----+-------------------------------------------- 1 | | {6} | 0 | 2 | 010100000000000000000000000000000000000040 2 | | {17} | 0.5 | 3.5 | 0101000000000000000000E03F0000000000000C40 3 | {6} | {7} | 1 | 2 | 0101000000000000000000F03F0000000000000040 4 | {17} | | 1.999999999999 | 3.5 | 010100000068EEFFFFFFFFFF3F0000000000000C40 5 | | {1} | 2 | 0 | 010100000000000000000000400000000000000000 6 | {1} | {2,4} | 2 | 1 | 01010000000000000000000040000000000000F03F 7 | {4,7} | {8,10} | 2 | 2 | 010100000000000000000000400000000000000040 8 | {10} | {12,14} | 2 | 3 | 010100000000000000000000400000000000000840 9 | {14} | | 2 | 4 | 010100000000000000000000400000000000001040 10 | {2} | {3,5} | 3 | 1 | 01010000000000000000000840000000000000F03F 11 | {5,8} | {9,11} | 3 | 2 | 010100000000000000000008400000000000000040 12 | {11,12} | {13} | 3 | 3 | 010100000000000000000008400000000000000840 13 | | {18} | 3.5 | 2.3 | 01010000000000000000000C406666666666660240 14 | {18} | | 3.5 | 4 | 01010000000000000000000C400000000000001040 15 | {3} | {16} | 4 | 1 | 01010000000000000000001040000000000000F03F 16 | {9,16} | {15} | 4 | 2 | 010100000000000000000010400000000000000040 17 | {13,15} | | 4 | 3 | 010100000000000000000010400000000000000840 (17 rows) 在数据我们可以看到 id 为 3 的顶点有进入为 6 的边,出去为 7 的边。 2. 拓扑 现在我们就可以设置边表中起始点和终止点的 id。 .. code:: sql /* -- 设置起点信息 */ UPDATE edges AS e SET source = v.id, x1 = x, y1 = y FROM vertices AS v WHERE ST_StartPoint(e.geom) = v.geom; /* -- 设置终点信息 */ UPDATE edges AS e SET target = v.id, x2 = x, y2 = y FROM vertices AS v WHERE ST_EndPoint(e.geom) = v.geom; 查看一下拓扑数据: .. code:: sql SELECT id, source, target FROM edges ORDER BY id; id | source | target ----+--------+-------- 1 | 5 | 6 2 | 6 | 10 3 | 10 | 15 4 | 6 | 7 5 | 10 | 11 6 | 1 | 3 7 | 3 | 7 8 | 7 | 11 9 | 11 | 16 10 | 7 | 8 11 | 11 | 12 12 | 8 | 12 13 | 12 | 17 14 | 8 | 9 15 | 16 | 17 16 | 15 | 16 17 | 2 | 4 18 | 13 | 14 | 我们可以在 QGIS 中查看当前的点和边: | |image6| 这里我们可以看到 id 为 1 的边的起始点为 5,终止点为 6。 API 说明 -------- API 具体说明可参考\ `官方文档 `__。 本文档参考pgRouting官方文档。 .. |image1| image:: /../_static/images/pgrouting/undirected_graph.png .. |image2| image:: /../_static/images/pgrouting/directed__cr_graph.png .. |image3| image:: /../_static/images/pgrouting/undirected__cr_graph.png .. |image4| image:: /../_static/images/pgrouting/pgrouting-wiki-shortpath.drawio.png .. |image5| image:: /../_static/images/pgrouting/edges.png .. |image6| image:: /../_static/images/pgrouting/vertices_edges.png .. |image7| image:: /../_static/images/pgrouting/pgrouting-summary.drawio.png .. |image8| image:: /../_static/images/pgrouting/directed_graph.png