[0031] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。
[0032] 本申请是基于发明人对以下问题的认识和发现做出的：
[0033] 城市可达区域是指在现有的城市交通场景中自给定查询点出发在特定时间段内车辆能够到达的区域。由于现有的方法通常是在城市路网中选举边界路段来确定可达区域边界，因此边界路段的选择是影响可达区域计算准确性的重要因素之一。针对现有的基于在城市道路中构建路网以图论方法选择边界路段存在应用场景局限且可达区域计算准确性不高和基于城市交通轨迹中最大路段轨迹数量选择边界路段时存在没有合理且有效地引入查询点空间距离作为约束的问题。本发明实施例提出了一种基于扇区的城市可达区域计算中的边界路段选择方法及装置。
[0034] 下面参照附图描述根据本发明实施例提出的城市可达区域计算中的边界路段选择方法及装置，首先将参照附图描述根据本发明实施例提出的城市可达区域计算中的边界路段选择方法。
[0035] 图1是本发明一个实施例的城市可达区域计算中的边界路段选择方法的流程图。
[0036] 如图1所示，该城市可达区域计算中的边界路段选择方法，在选择城市可达区域边界路段时，引入了扇区大小角度的空间约束和查询点均值距离的空间距离约束，其中，方法包括以下步骤：
[0037] 步骤S1：将具有时间信息的城市交通轨迹数据集与路段集进行匹配，并在以查询点为原点的坐标系中，构建路段角度集。
[0038] 可以理解的是，如图2所示，本发明实施例首先执行轨迹集P与路段集R的匹配，并在以查询点Q为原点的坐标系中构建路段角度集DEGR。
[0039] 需要说明的是，构建以查询点Q为原点的基于地理信息的坐标系时，以地理经度信息构建坐标系lon轴，lon∈[‑∞,+∞]；以地理信息纬度构建坐标系lat轴，lat∈[‑∞,+∞]。(2)在以查询点Q为原点的基于地理信息的坐标系中，令坐标coords＝{lon,lat}和查询点Q连线与lon轴的角度为 当坐标coords存在lon＞0&lat＞0关系时，则该坐标和查询点Q连线与lon轴的角度取值为Angle(coords,Q)；当坐标coords存在lon<0&lat＞0或lon<0&lat<0关系时，则该坐标和查询点Q连线与lon轴的角度取值为Angle(coords,Q)＝Angle(coords,Q)+π；当坐标coords存在lon＞0&lat<0关系时，则该坐标和查询点Q连线与lon轴的角度取值为Angle(coords,Q)＝Angle(coords,Q)+2π；
所有角度取值范围为[0,2π]。
[0040] 进一步地，在本发明的一个实施例中，步骤S1包括：步骤S1.1：执行轨迹点P与路段集R匹配，且在轨迹点集P中筛选出位于路段rj上的轨迹点，构成路段轨迹点集RPj；步骤S1.2：构建路段角度degrj＝(droj,drdj,DRPj)；对路段集R中的所有路段执行步骤S1.1和步骤S1.1，遍历完成后结束。
[0041] 其中，(1)轨迹点pi：轨迹点是指车辆在城市空间行驶途径查询点Q并且满足计算约束条件的有序点集形成的具有特定位置地理经纬度信息和轨迹数量的位置点，记为pi＝(loni,lati,numi)。其中loni表示该位置的地理经度转换成平面坐标系lon坐标；lati表示该位置的地理纬度换成平面坐标系lat坐标；numi表示轨迹的数量。P＝{p1,p2,…,pn}表示轨迹点集。
[0042] (2)路段rj：路段rj是指由起点、终点、路段轨迹点集和路段轨迹数构成且不包含交叉路口的道路片段，记为rj＝(roj,rdj,RPj,rnumj)。其中，roj＝{rolonj,rolatj}表示路段rj的起点坐标集，rolonj表示起点lon坐标，rolatj表示起点lat坐标；rdj＝{rdlonj,rdlatj}表示路段rj的终点坐标集，rdlonj表示终点lon坐标，rdlatj表示终点lat坐标；表示路段rj上的轨迹点集；rnumj表示路段轨迹数。R＝{r1,r2,…,rn}
表示路段集。
[0043] 需要说明的是，路段rj两端点和查询点Q的连线与lon轴正方向的构成角度中较大者的端点为起点orj，较小者的端点为终点drj。
[0044] (3)路段角度degrj：路段rj的起点、终点及各个路段轨迹点分别与查询点Q的连线与lon轴正方向的夹角构成子路段角度，记为degrj＝(droj,drdj,DRPj)。其中，droj表示路段起点角度；drdj表示路段终点角度； 表示路段轨迹点角度集。DEGR＝{degr1,degr2,…,degrn}表示路段角度集。
[0045] 具体而言，如图3所示，构建路段角度集具体包括：
[0046] 步骤S1.1：执行轨迹点P与路段集R匹配，即对路段集R中任一路段rj，在轨迹点集P中筛选出位于路段rj上的轨迹点，构成路段轨迹点集RPj。具体地，对任意路段rj，遍历轨迹点集P，当轨迹点pi位于路段rj上时，则记pi为路段轨迹点 并加入路段轨迹点集RPj中，当路段轨迹点集RPj构建完成后，计算路段轨迹数
[0047] 步骤S1.2：进一步构建路段角度degrj＝(droj,drdj,DRPj)。具体地，依据规则2，计算路段起点角droj＝Angle(roj,Q)，计算路段终点角drdj＝Angle(doj,Q)；依次计算路段轨迹点角 并加入到路段轨迹点角度集DRPj中。上述计算完成后将路段角度degrj加入到路段角度集DEGR中。
[0048] 步骤S1.3：对路段集R中的所有路段执行步骤S1.1：和S1.2，遍历完成后结束步骤S1。
[0049] 步骤S2：在依据路段角度集与扇区存在的角度关系筛选位于扇区内的子路段集，构建扇区内子路段集。
[0050] 可以理解的是，如图2所示，建路段角度集DEGR之后，接着遍历扇区集A和路段角度集DEGR，对任意扇区aα，判断其与路段角度集DEGR中任意路段角度degrj存在的角度关系，依据角度关系构建扇区aα内的子路段集Sα。
[0051] 其中，扇区aα：在以城市可达区域查询点Q为原点的基于地理信息的坐标系中，构建圆心为查询点Q，半径无限长的圆。扇区aα则是该圆中圆心角为∠Δθ的一部分，记为aα＝(degminα,degmaxα)。其中，degmaxα表示扇区边线与lon轴构成的大角；degminα表示扇区边线与lon轴构成的小角；∠Δθ＝|degmaxα‑degminα|。A＝{a1,a2,…,an}表示扇区集。
[0052] 进一步地，在本发明的一个实施例中，步骤S2包括：步骤S2.1：遍历扇区集A，对任意扇区aα，初始化扇区aα内子路段集Sα为空集；步骤S2.2：遍历路段角度集DEGR，对任意路段角度degrj判断其与扇区aα的大角degmaxα及小角degminα的角度关系，其中，当存在drdj≥degmaxa或droj≤degmina角度关系时，跳出路段角度degrj判断，或者当存在degmina≤drdj≤droj≤degmaxa角度关系时，将路段rj记为 加入Sα中，反之则执行步骤S2.3，遍历DEGR完成后执行步骤S2.4；步骤S2.3：在路段rj中筛选位于扇区aα内的子路段 步骤S2.4：当路段集R中所有路段角度判断完成后，结束步骤。
[0053] 其 中 ，(1 ) 子 路 段 路 段 r j 位 于 扇区 aα内 的 子 路 段 记 为其中， 表示子路段 的起点的坐标集， 表示起点lon坐标， 表示起点lat坐标； 表示子路段
的终点坐标集， 表示起点lon坐标， 表示起点lat坐标；
表示子路段轨迹点集； 表示子路段轨迹数； 表示
子路段起点 子路段终点 及子路段轨迹点集 与查询点Q均值距离。扇区aα内子路段集记为
[0054] (2)子路段轨迹点角度 子路段轨迹点集 各个轨迹点分别与查询点Q的连线与lon轴正方向的夹角称为子路段轨迹点角度，记为 子路段轨迹点角度集记为[0055] 需要说明的是，本发明实施例所涉及符号上标用于表示元素与集合之间的所属关系，所涉下标用于表示元素在集内的顺序关系。如子路段的子路段轨迹点集 中，对任意
子路段轨迹点 其中上标j和α分别表示该子路段轨迹点属于扇区α内的子路段集Sα中第j位子路段 下标q∈[1,m]表示该子路段轨迹点在子路段轨迹点集 中列第q位。
[0056] 具体而言，如图4所示，构建扇区内子路段集具体包括：
[0057] 步骤S2.1：遍历扇区集A，对任意扇区aα，初始化扇区aα内子路段集Sα为空集。
[0058] 步骤S2.2：遍历路段角度集DEGR,对任意路段角度degrj判断其与扇区aα的大角degmaxα及小角degminα的角度关系,当存在drdj≥degmaxa或droj≤degmina角度关系时，跳出路段角度degrj判断；当存在degmina≤drdj≤droj≤degmaxa角度关系时，将路段rj记为加入Sα中，反之则进行步骤S2.3。遍历DEGR完成后执行步骤S2.4。
[0059] 步骤S2.3：在路段rj中筛选位于扇区aα内的子路段 具体地，即当存在drdj≤degmaxa≤droj角度关系时，遍历路段轨迹点角度集DRPj，对任意路段轨迹点角度的轨迹点 记为 加入 将路段轨迹点角度 记为 加入子路段轨迹点角度集 中；构建子路段轨迹点角度集 完成后，在 中选择最大值将子路段轨迹点 对应lon、lat坐标值赋予子路段起点 的坐
标值，即 将路段rj的终点rdj对应lon、lat坐标值赋予子路段
终点 的坐标值，即 计算
和
当存在drdj≤degmina
≤droj角度关系时，遍历路段轨迹点角度集DRPj，对任意路段轨迹点角度 的轨迹点 记为 加入 将路段轨迹点角度 记为 加入子路段轨迹点角度集
中；构建子路段轨迹点角度集 完成后，在 中选择最小值 将子路段轨
迹点 对应lon、lat坐标值赋予子路段终点 的坐标值，即
将路段rj的起点roj对应lon、lat坐标值赋予子路段起点
的坐标值，即 计算
计算
[0060]
[0061] 步骤S2.4：当路段集R中所有路段角度判断完成后，结束步骤S2。
[0062] 下面将通过具体示例对扇区内子路段构建过程进行举例说明，具体如下：
[0063] 如图5所示，以构建扇区aβ内子路段集Sβ为例，其中路段集R＝{r1,r2,r3,r4,r5,r6,r7,r8}，子路段集 aβ＝(degminβ,degmaxβ)。
[0064] 首先遍历路段角度集DEGR，由于路段角度degr1存在degmaxβ≤drd1角度关系，因此跳出路段角度degr1的判断。同样的，由于路段角度degr8存在dro8≤degminβ角度关系因此跳出路段角度degr8的判断判断。
[0065] 对于路段r2和r3，由于路段角度degr2存在degminβ≤drd2≤dro2≤degmaxβ角度关系，因此将r2记为 加入Sβ中。同样的，由于路段角度degr3存在degminβ≤drd3≤dro3≤degmaxβ角度关系，将r3记为 加入Sβ中。
[0066] 对于路段r4、r6和r7。构建子路段 时，由于路段角度degr4存在drd4≤degminβ≤dro4角度关系。因此，遍历路段轨迹点角度集DRP4，由于存在 和角度关系，因此将路段轨迹点 和 分别记为子路段轨迹点 和
并加入子路段轨迹点集 中；将路段轨迹点角度 和 分别记为子路段轨迹点角度和 并加入子路段轨迹点角度集 中；将路段r4的起点ro4对应lon、lat坐标
值赋予子路段起点 坐标值，即 在
中选出最小值 将子路段轨迹点 的lon、lat坐标值赋予子路段终点
坐标值，即 子路段 构建完成，将子
路段 加入Sβ中。
[0067] 构建子路段 时，由于存在drd6≤degminβ≤dro6角度关系，接着遍历路段轨迹点角度集DRP6，且存在 和 角度关系，因此将路段轨迹点 和分别记为子路段轨迹点 和 并加入子路段轨迹点集 中，将路段轨迹点角度
和 分别记为子路段轨迹点角度 和 并加入子路段轨迹点角度集
中；将路段r6的起点ro6对应lon、lat坐标值赋予子路段起点 即
在 中选出最小值 将子路段轨迹点 的lon、
lat坐标值赋予子路段终点 坐标值，即
子路段 构建完成，将子路段 加入Sβ中。
[0068] 构建子路段 时，由于路段角度degr7存在drd7≤degminβ≤dro7角度关系，接着遍历路段轨迹点角度集DRP7，且存在 角度关系，因此将路段轨迹点 记为子路段轨迹点 并加入子路段轨迹点集 中，将路段轨迹点角度 记为子路段轨迹点角度 并加入子路段轨迹点角度集 中；将路段r7的起点ro7对应lon、lat坐标值赋予子路段起点 坐标值，即 在 中选
出最小值 将子路段轨迹点 的lon、lat坐标值赋予子路段终点
坐标值，即 子路段 构建完成，将子
路段 加入Sβ中。
[0069] 构建子路段 时，由于路段角度degr5存在drd5≤degmaxβ≤dro5角度关系。因此，遍历路段轨迹点角度集DRP5，由于存在 和 角度关系，因此将路段轨迹点 和 分别记为 和 并加入 中，将路段轨迹点角度 和 分
别记为 和 并加入子路段轨迹点角度集 中；在 中选出最大值 将
子路段轨迹点 的lon、lat坐标值赋予子路段起点 坐标值，即
将路段r5的终点do5对应lon、lat坐标值赋予子路段终点
坐标值，即 子路段 构建完成，将子
路段 加入Sβ中。最终得到扇区aβ内子路集
[0070] 步骤S3：在每个扇区内的子路段集中依据路段轨迹数选出多条候选边界路段组成候选边界路段集，在候选边界路段集中选出均值距离最大值的候选路段作为边界路段，构建边界路段集。
[0071] 可以理解的是，如图2所示，最后在每个扇区内的子路段集中依据路段轨迹数选择k条候选路段组成候选路段集，在候选路段集中依据与查询点Q的均值距离选择距离最大者作为该扇区的边界路段加入边界路段集中。进一步求出边界路段集。
[0072] 其中，边界路段集(BR)：执行边界路段集选择方法，由扇区集A＝{a1,a2,…,an}中全部扇区aα内子路段集Sα选出构成可达区域边界的路段集，表示为BR＝{br1,br2,…,brn}。
[0073] 进一步地，在本发明的一个实施例中，步骤S3包括：步骤S3.1：遍历扇区集A，将候选边界路段集CR设置为空集；步骤S3.2：选择候选边界路段集CR＝{cr1,cr2,…,crk}中子路段均值距离 最大值的候选边界路段crm加入边界路段BR中；步骤S3.3：当扇区集A遍历完成后，结束步骤。
[0074] 具体而言，如图6所示，构建边界路段集具体包括：
[0075] 步骤S3.1：遍历扇区集A，将候选边界路段集CR设置为空集。对扇区aα内子路段集Sα依据子路段轨迹数进行降序排列，选择序列中前k条子路段作为候选边界路段集CR＝{cr1,cr2,…,crk}。
[0076] 步骤S3.2：选择候选边界路段集CR＝{cr1,cr2,…,crk}中子路段均值距离最大值的候选边界路段crm加入边界路段BR中。
[0077] 步骤S3.3：当扇区集A遍历完成后结束步骤S3。
[0078] 下面将通过具体示例对边界路段集构建过程进行举例说明，具体如下：
[0079] 如图7所示，以在扇区aβ内子路段集Sβ内选出边界路段为例。其中，[0080] 子路段集：
[0081] 子路段：
[0082]
[0083]
[0084]
[0085]
[0086]
[0087] 首先，设置候选边界路段集CR为空集。接着对扇区aβ内子路段集Sβ依据子路段轨迹数降序排列，其排列后的如图7左部子路段Sβ排序表所示。当设置k＝3时，则将子路段和 加入候选边界路段集 如图7左部虚线框所示。由于子路段 的均值距离 最大，如图中虚线框内实线框所示。因此将子路段 记为边界路段br4加
入边界路段集BR中，扇区aβ的边界路段已选择完成。
[0088] 根据本发明实施例提出的城市可达区域计算中的边界路段选择方法，考虑到了轨迹数在城市可达区域计算时的应用，即将富有时间信息的城市交通轨迹数据集与路段集进行匹配，并在以查询点为原点的坐标系中构建路段角度集的计算过程，提高了可达区域的实效性；引入了扇区大小角度的空间约束，即在依据路段角度集与扇区存在的角度关系筛选位于扇区内的子路段集的计算过程；引入了查询点均值距离的空间距离约束，即在每个扇区内的子路段集中依据路段轨迹数选出k条候选边界路段组成候选边界路段集，在候选边界路段集中选出均值距离最大值的候选路段作为边界路段并构建边界路段集的计算过程；扇区大小角度的空间约束和查询点均值距离的空间距离约束有效地提升了可达区域计算准确性。
[0089] 其次参照附图描述根据本发明实施例提出的城市可达区域计算中的边界路段选择装置。
[0090] 图8是本发明一个实施例的城市可达区域计算中的边界路段选择装置的结构示意图。
[0091] 如图8所示，该城市可达区域计算中的边界路段选择装置10包括：路段角度集构建模块100、扇区内子路段集构建模块200和边界路段集构建模块300。
[0092] 其中，路段角度集构建模块100用于将具有时间信息的城市交通轨迹数据集与路段集进行匹配，并在以查询点为原点的坐标系中，构建路段角度集；扇区内子路段集构建模块200用于在依据路段角度集与扇区存在的角度关系筛选位于扇区内的子路段集，构建扇区内子路段集；边界路段集构建模块300用于在每个扇区内的子路段集中依据路段轨迹数选出多条候选边界路段组成候选边界路段集，在候选边界路段集中选出均值距离最大值的候选路段作为边界路段，构建边界路段集。本发明实施例的装置10有效提高了可达区域的实效性，并在选择城市可达区域边界路段时，引入了扇区大小角度的空间约束和查询点均值距离的空间距离约束，从而有效提高了可达区域计算准确性，简单易实现。
[0093] 进一步地，在本发明的一个实施例中，路段角度集构建模块100包括：匹配单元、构建单元和执行单元。
[0094] 其中，匹配单元，用于执行轨迹点P与路段集R匹配，且在轨迹点集P中筛选出位于路段rj上的轨迹点，构成路段轨迹点集RPj；构建单元，用于构建路段角度degrj＝(droj,drdj,DRPj)；执行单元，用于对路段集R中的所有路段执行匹配单元和构建单元，遍历完成后结束。
[0095] 进一步地，在本发明的一个实施例中，扇区内子路段集构建模块200包括：初始化单元、判断单元和第一结束单元。
[0096] 其中，初始化单元，用于遍历扇区集A，对任意扇区aα，初始化扇区aα内子路段集Sα为空集；判断单元，遍历路段角度集DEGR，对任意路段角度degrj判断其与扇区aα的大角degmaxα及小角degminα的角度关系，其中，当存在drdj≥degmaxa或droj≤degmina角度关系时，跳出路段角度degrj判断，或者当存在degmina≤drdj≤droj≤degmaxa角度关系时，将路段rj记为 加入Sα中，反之则执行筛选单元，遍历DEGR完成后执行第一结束单元；筛选单元，用于在路段rj中筛选位于扇区aα内的子路段 第一结束单元，用于当路段集R中所有路段角度判断完成后，结束步骤。
[0097] 进一步地，在本发明的一个实施例中，边界路段集构建模块300包括：设置单元、选择单元和第二结束单元。
[0098] 其中，设置单元，用于遍历扇区集A，将候选边界路段集CR设置为空集；选择单元，用于选择候选边界路段集CR＝{cr1,cr2,…,crk}中子路段均值距离 最大值的候选边界路段crm加入边界路段BR中；第二结束单元，用于当扇区集A遍历完成后，结束步骤。
[0099] 需要说明的是，前述对城市可达区域计算中的边界路段选择方法实施例的解释说明也适用于该实施例的城市可达区域计算中的边界路段选择装置，此处不再赘述。
[0100] 根据本发明实施例提出的城市可达区域计算中的边界路段选择装置，考虑到了轨迹数在城市可达区域计算时的应用，即将富有时间信息的城市交通轨迹数据集与路段集进行匹配，并在以查询点为原点的坐标系中构建路段角度集的计算过程，提高了可达区域的实效性；引入了扇区大小角度的空间约束，即在依据路段角度集与扇区存在的角度关系筛选位于扇区内的子路段集的计算过程；引入了查询点均值距离的空间距离约束，即在每个扇区内的子路段集中依据路段轨迹数选出k条候选边界路段组成候选边界路段集，在候选边界路段集中选出均值距离最大值的候选路段作为边界路段并构建边界路段集的计算过程；扇区大小角度的空间约束和查询点均值距离的空间距离约束有效地提升了可达区域计算准确性。
[0101] 此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。
[0102] 在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。
[0103] 在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。
[0104] 尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。
