withPoints - 类别

当点添加到图中时。

Warning

下一版本的拟议功能。

  • 它们并未正式出现在当前版本中。

  • 它们可能会正式成为下一个版本的一部分：

    • 这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL

    • 名字可能不会改变。（但仍然有可能改变）

    • 签名可能不会改变。（但仍然有可能改变）

    • 功能可能不会改变。（但仍然有可能改变）

    • pgTap 测试已经完成。 但可能需要更多。

    • 文档可能需要完善。

介绍

with points 类别通过根据 Points SQL 查询的要求在边上添加点来动态修改图形。

该类别中的函数能够在位于原始图之外的任意点之间进行处理。

此类功能被认为用于路由车辆，但也可能适用于其他一些不涉及车辆的应用程序。

当给定一个点标识符 pid，它被映射到具有标识符 edge_id 的边上，并且有一个从源到目标沿边的分数 fraction，以及关于点位于边的哪一侧的其他信息 side，那么可以在固定网络上从任意点进行处理。

所有这些函数都考虑了尽可能多的“现实世界”特征：

  • 图的种类：

    • 有向 图

    • 无向 图

  • 到达点：

    • 强制到达该点所在航段的一侧。

    • 位于该段的两侧。

  • 具有以下条件的国家：

    • 右侧 驾驶

    • 左侧 驾驶

  • 一些要点是：

    • 永久：例如，存储在表中的客户端点集 数据库。

      • 图已修改为将这些点永久用作顶点。

      • 数据库上有一个描述点的表格

    • 时间：例如通过 Web 应用程序给出的点

  • 点的编号用负号处理。

    • 这种符号变化是为了避免当存在与点标识符具有相同标识符的顶点时发生混淆。

    • 原始点标识符应为正数。

    • 向负数的转变是在内部完成的。

    • 解释输出的节点上的符号信息

      • 正号是原始图的顶点

      • 负号是 Points SQL 的一个点

参数

列

类型

描述

Edges SQL

TEXT

Edges SQL 如下所述

Points SQL

TEXT

Points SQL 如下所述

Combinations SQL

TEXT

Combinations SQL 如下所述

start vid

BIGINT

路径起始顶点的标识符。 负值用于点的标识符。

start vids

ARRAY[BIGINT]

起始顶点的标识符数组。 负值用于点的标识符。

end vid

BIGINT

路径结束顶点的标识符。 负值用于点的标识符。

end vids

ARRAY[BIGINT]

结束顶点的标识符数组。 负值用于点的标识符。

可选参数

参数

类型

默认

描述

driving_side

CHAR

r

在 [r, l] 中的值表示驾驶方向是：

  • r 代表右驾驶侧

  • l 表示左驾驶侧

  • 任何其他值将被视为 r

details

BOOLEAN

false

  • 如果为 true ，结果将包括路径中的点。

  • 如果为 false ，结果将不包括路径中的点。

内部查询

Edges SQL

列

类型

默认

描述

id

ANY-INTEGER

边的标识符。

source

ANY-INTEGER

边的第一个端点顶点的标识符。

target

ANY-INTEGER

边的第二个端点顶点的标识符。

cost

ANY-NUMERICAL

边(source, target)的权重

reverse_cost

ANY-NUMERICAL

-1

边(target, source)的权重

  • 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Points SQL

参数

类型

默认

描述

pid

ANY-INTEGER

value

点的标识符。

  • 使用正值，因为内部将转换为负值

  • 如果列存在，则它不能为 NULL。

  • 如果列不存在，将自动给出连续的负 值 。

edge_id

ANY-INTEGER

距离该点“最近”的边的标识符。

fraction

ANY-NUMERICAL

<0,1> 中的值指示距边缘第一个端点的相对位置。

side

CHAR

b

[b, r, l, NULL] 中的值指示该点是否为：

  • r 在右边，

  • l 在左边，

  • b, NULL 在两边

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

分量 SQL

参数

类型

描述

source

ANY-INTEGER

出发顶点的标识符。

target

ANY-INTEGER

到达顶点的标识符。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

高级文档

关于积分

对于本节，将使用以下城市（参见 示例数据）一些有趣的点（例如餐馆、超市、邮局等）作为示例。

_images/Fig1-originalData.png

  • 图是 有向 的

  • 红色箭头显示边表上的边 (source, target)

  • 蓝色箭头显示边表上的边 (target, source)

  • 每个点位置显示它与边 (source, target) 的关系

    • 在右侧为第 2 点和第 4 点。

    • 左侧为第 1、3 和 5 点。

    • 在两侧为第 6 点。

数据库上的表示遵循 Points SQL 描述，对于本示例：

SELECT pid, edge_id, fraction, side FROM pointsOfInterest;
 pid | edge_id | fraction | side
-----+---------+----------+------
   1 |       1 |      0.4 | l
   2 |      15 |      0.4 | r
   3 |      12 |      0.6 | l
   4 |       6 |      0.3 | r
   5 |       5 |      0.8 | l
   6 |       4 |      0.7 | b
(6 rows)

驾驶侧

在下面的图片中：

  • 平方顶点是临时顶点，

  • 根据驾驶侧添加临时顶点，

  • 直观地显示不同驾驶侧数据解释方式的差异。

右驾驶侧

_images/rightDrivingSide.png

  • 点 1 位于边 (6, 5)

  • 点 2 位于边缘 (16, 17)

  • 点 3 位于边缘 (8, 12)

  • 点 4 位于边 (1, 3)

  • 点 5 位于边缘 (10, 11)

  • 点 6 位于边 (6, 7) 和 (7, 6)

左驾驶侧

_images/leftDrivingSide.png

  • 点 1 位于边 (5, 6)

  • 点 2 位于边 (17, 16)

  • 点 3 位于边缘 (8, 12)

  • 点 4 位于边 (3, 1)

  • 点 5 位于边缘 (10, 11)

  • 点 6 位于边 (6, 7) 和 (7, 6)

驾驶侧并不重要

  • 就像双方都要考虑所有点 b

  • 无向 图上的首选用法

  • 在 TRSP - 函数族 上，此选项无效

_images/noMatterDrivingSide.png

  • 点 1 位于边 (5, 6) 和 (6, 5)

  • 点 2 位于边 (17, 16) 和 16, 17

  • 点 3 位于边缘 (8, 12)

  • 点 4 位于边 (3, 1) 和 (1, 3)

  • 点 5 位于边缘 (10, 11)

  • 点 6 位于边 (6, 7) 和 (7, 6)

创建临时顶点

本节将演示如何在图内部创建临时顶点。

问题

对于边:

SELECT id, source, target, cost, reverse_cost
FROM edges WHERE id = 15;
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
 15 |     16 |     17 |    1 |            1
(1 row)

插入点：

SELECT pid, edge_id, fraction, side
FROM pointsOfInterest WHERE pid = 2;
 pid | edge_id | fraction | side
-----+---------+----------+------
   2 |      15 |      0.4 | r
(1 row)

在右侧行驶网络

右驾驶侧

_images/rightDrivingSide.png

  • 只能通过顶点 16 才能到达点 -2。

  • 不影响边 (17, 16)，因此边被保留。

  • 它只影响边 (16, 17)，因此边被移除。

  • 创建两条新边：

    • 边 (16, -2) 的成本为``0.4`` （原始成本*分数 == \(1 * 0.4\)）

    • 边 (-2, 17) 的成本为``0.6`` （剩余成本）

  • 附加边的总成本等于原始成本。

  • 如果同一条边上有更多点，则递归地重复该过程。

在左侧驾驶网络上

左驾驶侧

_images/leftDrivingSide.png

  • 只能通过顶点 17 才能到达点 -2。

  • 不影响边 (16, 17) ，因此保留边。

  • 它只影响边 (17, 16) ，因此边被移除。

  • 创建两条新边：

    • 使用原始边 (16, 17) ，因为分数是原始边的分数：

      • 边 (16, -2) 的成本为``0.4`` （原始成本*分数 == \(1 * 0.4\)）

      • 边 (-2, 17) 的成本为``0.6`` （剩余成本）

      • 如果同一条边上有更多点，则递归地重复该过程。

    • 翻转边并将它们添加到图中：

      • 边 (17, -2) 变为 (-2, 16)，成本为``0.4`` ，并添加到图中。

      • 边 (-2, 16) 变为 (17, -2)，成本为 0.6 ，并添加到图中。

  • 附加边的总成本等于原始成本。

当驾驶侧无关紧要时

_images/noMatterDrivingSide.png

  • 可以通过顶点 16 或 17 到达点 -2。

  • 影响边 (16, 17) 和 (17, 16) ，因此边被移除。

  • 创建四个新边：

    • 使用原始边 (16, 17) ，因为分数是原始边的分数：

      • 边 (16, -2) 的成本为``0.4`` （原始成本*分数 == \(1 * 0.4\)）

      • 边 (-2, 17) 的成本为``0.6`` （剩余成本）

      • 如果同一条边上有更多点，则递归地重复该过程。

    • 翻转边并将所有边添加到图中：

      • 边 (16, -2) 被添加到图中。

      • 边 (-2, 17) 被添加到图中。

      • 边 (16, -2) 变为 (-2, 16) ，成本为 0.4，并添加到图中。

      • 边 (-2, 17) 变为``(17, -2)``，成本为 0.6 ，并添加到图中。

另请参阅

索引和表格