(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211126607.5 (22)申请日 2022.09.16 (71)申请人 广东工业大 学 地址 510062 广东省广州市越秀区东 风东 路729号 (72)发明人 卢洁楚　傅惠　姚奕鹏　陈扬航　 (74)专利代理 机构 广东广信君达律师事务所 44329 专利代理师 廖朗皓 (51)Int.Cl. G06F 30/20(2020.01) G06Q 10/04(2012.01) (54)发明名称 一种用于行人仿真客流组织的可行路径搜 索方法 (57)摘要 本发明公开了一种用于行人仿真客流组织 的可行路径搜索方法， 包括： 获取行人仿真的矢 量化地图数据集， 将数据集中线段所在的二维坐 标区域划分为多个子区域， 依据数据集中每条线 段所处位置将线段归类到相应的子区域； 其中， 所述线段表 示地图中障碍物的外轮廓线； 建立可 行线段集合， 用于存储路径搜索过程中的可行线 段； 设定行人仿真的路径起点和终点位置， 建立 起点和终点的起讫线， 进入路径搜索的父循环流 程； 当变量拐点内、 外角都存在以变量拐点为端 点的线段， 则进入路径搜索的子循环流程； 筛选 出可行线段集合中首坐标端点为行人仿真的路 径起点、 末坐标端点为终点的可行线段并简化可 行线段， 简化后的所有可行线段即为从起点到终 点的可行路径集 合。 权利要求书4页 说明书9页 附图4页 CN 115238525 A 2022.10.25 CN 115238525 A 1.一种用于行 人仿真客 流组织的可 行路径搜索方法， 其特 征在于， 包括： 获取行人仿真的矢量化地图数据集， 将数据集中线段所在的二维坐标区域划分为多个 子区域， 依据数据集中每条线段所处位置将线段归类到相应的子区域； 其中， 所述线段表 示 地图中障碍物的外轮廓线； 建立可行线段集 合， 用于存 储路径搜索过程中的可 行线段； 设定行人仿真的路径起点和终点位置， 建立起点和终点的起讫线， 进入路径搜索的父 循环流程； 在该流程中， 通过判断所述起讫线所在子区域， 根据子区域中线段集合是否与所 述起讫线相交， 确定可行线段并添加到所述可行线段集合中； 其中， 当存在相交情况时， 首 先确定与起讫线相交且与起点直线距离最短的线段， 令该线段 的两个端点作为变量拐点， 构造起点 ‑变量拐点 ‑终点的折线集合， 通过判断折线集合内折线的变量拐点内、 外角是否 都存在以变量拐点 为端点的线段来确定是否存在可 行线段； 当变量拐点内、 外角都存在以变量拐点为端点的线段， 则进入路径搜索的子循环流程； 在该流程中， 根据变量拐点所在子区域的线段集合确定以变量拐点作为其一个端点的所有 线段的另一端点， 组合成端点集合； 构 造起点‑变量拐点 ‑端点集合中的端点的折线集合； 通 过判断折线集合内折线的变量拐点内、 外角是否都存在以变量拐点为端点的线段来确定是 否存在可 行线段； 筛选出可行线段集合中首坐标端点为行人仿真的路径起点、 末坐标端点为终点的可行 线段并简化可 行线段， 简化后的所有可 行线段即为从起 点到终点的可 行路径集 合。 2.根据权利要求1所述的用于行人仿真客流组织的可行路径搜索方法， 其特征在于， 所 述将数据集中线段所在的二 维坐标区域划分为多个子区域， 依据数据集中每条线段所 处位 置将线段归类到相应的子区域， 包括： 遍历数据集 中各条线段端点， 将端点的x坐标值的最小值记为 、 最大值记为 ， 将端点的y坐标值的最小值记为 、 最大值记为 ， 由以上四个最值构成线段所在的 二维坐标区域 ， 将 划分为 个子区域， 每 个子区域记为 ； 遍历数据集 ， 令 ， 判断线段 上是否存在点 落在子区域 内， 即 ， 则将线段 归类到子区域 的线段集合 中； 若线段 上存在 多个点落在多个不同的子区域， 则线段 同时归类到多个子区域的线段集 合中。 3.根据权利要求1所述的用于行人仿真客流组织的可行路径搜索方法， 其特征在于， 所 述建立可 行线段集 合， 用于存 储路径搜索过程中的可 行线段， 包括： 若当前需要添加的可行线段为 ， 而集合R中已有的可行线段记为 ； 若 已在集合R 中则结束， 否则将 添加到集合 ， 同时遍历集合R， 若 的末坐标端点与 的首坐标端点 重合， 则将 与 的末坐标端点组合， 组成新的可 行线段添加到集 合R， 否则结束。 4.根据权利要求1所述的用于行人仿真客流组织的可行路径搜索方法， 其特征在于， 所 述通过判断所述起讫线所在子区域， 根据子区域中线段集合是否与所述起讫线相交， 确定权　利　要　求　书 1/4 页 2 CN 115238525 A 2可行线段并添加到所述可 行线段集 合中， 包括： 步骤3.1， 将路径搜索的起点O坐标值赋值给变量 o， 终点D坐标值赋值给变量 d， 以变量o 为起点、变量d为终点， 两点相连构造起讫线 Lod， 判断起讫线 Lod所在的子区域， 提取出起讫 线Lod所在的子区域对应的线段集 合； 步骤3.2， 遍历步骤3.1提取出的若个线段集合内的线段， 判断线段是否与起讫线 Lod相 交； 当不存在相交时， 认为起讫线 Lod是可行线段， 该可行线段需要添加到 集合R中， 父循环程 序结束。 5.根据权利要求1所述的用于行人仿真客流组织的可行路径搜索方法， 其特征在于， 所 述当存在相交情况时， 首先确定与起讫线相交且与起点直线距离最短的线段， 令该线段 的 两个端点作为变量拐点， 构造起点 ‑变量拐点 ‑终点的折线集合， 通过判断折线集合内折线 的变量拐点内、 外角是否都存在以变量拐点 为端点的线段来确定是否存在可 行线段， 包括： 步骤3.3， 在提取出的若个线段集合中， 寻找与起讫线 Lod相交且与起点 o直线距离最短 的线段Li， 若存在多条线段 Li则任取其一； 线段 Li的两个端点记为 ， 此时令变量拐点 ， 分别以o为起点、 为拐点、d为终点依序相连形成折线 ， 组 成折线集 合 ； 步骤3.4， 依次判断步骤3.3中折线集合内折线 的变量拐点 内、 外角是否都存在以变 量拐点 为端点的线段： 以折线中线段 为基准线， 线段 为分界线， 设定基准线 绕拐点 顺时针方向 旋转到分界线 所形成的角度区间 为内角， 而角度区间 设定为外角； 其中 为基准线与分界线的顺时针夹角； 提取出变量拐点 所在子区域对应的线段集合， 在该集合中寻找线段， 若存在以拐点 为端点的线段， 则逐一计算基准线 线段的顺时针夹角， 组成夹角集合 ； 令夹角值 ， 若 ， 则将 添加到内角集合 ； 若 ， 则将 添加到外角集合 ； 逐一添加完成后， 判断 、 是否为空集： 若内、 外角都存在以拐点 为端点的线段， 即内、 外角集合都不为空集， 即 且 ， 则跳转到路径搜索的子循环流程； 否则， 此时变量起点 o更新为拐点 ， 变量终点 d 依旧为初始终点D， 继续父循环程序， 回到步骤3.1； 当内、 外角不都存在以拐点 为端点的线段时， 认为基准线 是可行线段， 该可行线权　利　要　求　书 2/4 页 3 CN 115238525 A 3