用于矢量轨迹压缩的余弦垂距判别方法、装置和设备

技术领域

本申请涉及矢量数据压缩技术领域，尤其涉及一种用于矢量轨迹压缩的余弦垂距判别方法、装置和设备。

背景技术

随着定位技术的发展和定位设备的普及，矢量数据呈爆炸性的增长，矢量数据压缩技术研究已成为优化存储、网路传输和可视化等领域的热点问题。矢量数据是指既有大小，又带有方向的一类数据集，通常用于表示地图图形或地理实体的位置和形状的数据。

目前，大数据背景下的海量数据应用在我们周围，大到对航天、航空、和卫星的轨迹实时跟踪，小到地点无人驾驶、公交车的站台显示和到站提醒、网约平台对网约车辆的实时定位、以及每个人每时每刻所形成的位置变化等等，都离不开矢量数据的获取与处理。矢量数据是源源不断的生产与输出，但用于存储数据的设备和计算机的处理能力始终是有限的，因此研究矢量数据压缩是极其必要的。

相关技术中，已出现众多成熟的压缩理论，如垂距限值法、角度限制法、最小面积删除法、面积偏差控制法、以及经典的道格拉斯-普克法(D-P算法)等。不过这些算法都存在各自的问题，比如垂距限值法和角度限制法均是基于一个设定的阈值进行判断，不能考虑路线可能遇到的特殊变化情况，也不能考虑路线的整体形态要素；面积偏差控制法需要进行大量的直线空间相交点方程求解等计算，导致处理时间很长；D-P算法的时间复杂度较高，当数据量很大时，处理时间很长，且只能处理离线数据，难以扩展到实时处理。

也就是说，目前的多种矢量轨迹压缩算法均存在各自的问题，导致实际应用的场景和效果受限。

发明内容

本申请提供一种用于矢量轨迹压缩的余弦垂距判别方法、装置和设备，以更好地实现矢量轨迹压缩。

本申请的上述目的是通过以下技术方案实现的：

第一方面，本申请实施例提供一种用于矢量轨迹压缩的余弦垂距判别方法，其包括：

获取原始矢量轨迹数据集pointsList，并构建循环体；所述循环体的长度为原始矢量轨迹数据的长度pointsList.size减2得到的差值pointsList.size-2；

每次循环按照索引i开始，按顺序取三个点构成三元组，三个点的下标分别是i、i+1和i+2，并以该三元组构建球面三角形；

利用球面余弦定理分别计算球面三角形的三条边d

在确定三个点属于密集点集路段时，删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；

在确定三个点属于稀疏点集路段时，基于计算得到的三条边d

在确定当前稀疏点集路段属于曲直路段时，比较底边上的高h与第一预设阈值d_max的大小；若h≤d_max，则删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；否则，保留第二个点，并以第二个点作为下次循环的起始点，循环继续；

在确定当前稀疏点集路段属于弯道路段时，比较底边上的高h与第二预设阈值d_min的大小；若h≤d_min，则删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；否则，保留第二个点，并以第二个点作为下次循环的起始点，循环继续；其中，d_max≠d_min；

直至循环结束后，得到压缩后的矢量轨迹数据集。

可选的，预设余弦值m的取值为m＝-0.75。

可选的，第一预设阈值d_max和第二预设阈值d_min满足：d_max＞d_min。

可选的，第一预设阈值d_max的取值为：d_max＝3，单位为米。

可选的，第二预设阈值d_min的取值为：d_max＝2，单位为米。

第二方面，本申请实施例还提供一种用于矢量轨迹压缩的余弦垂距判别装置，其包括：

循环体构建模块，用于获取原始矢量轨迹数据集pointsList，并构建循环体；所述循环体的长度为原始矢量轨迹数据的长度pointsList.size减2得到的差值pointsList.size-2；

三角形构建模块，用于每次循环按照索引i开始，顺序取三个点构成三元组，三个点的下标分别是i、i+1和i+2，并以该三元组构建球面三角形；

路段确定模块，用于利用球面余弦定理分别计算球面三角形的三条边d

压缩模块，用于在确定三个点属于密集点集路段时，删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；

以及，在确定三个点属于稀疏点集路段时，基于计算得到的三条边d

以及，在确定当前稀疏点集路段属于曲直路段时，比较底边上的高h与第一预设阈值d_max的大小；若h≤d_max，则删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；否则，保留第二个点，并以第二个点作为下次循环的起始点，循环继续；

以及，在确定当前稀疏点集路段属于弯道路段时，比较底边上的高h与第二预设阈值d_min的大小；若h≤d_min，则删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；否则，保留第二个点，并以第二个点作为下次循环的起始点，循环继续；其中，d_max≠d_min；

直至循环结束后，得到压缩后的矢量轨迹数据集。

可选的，预设余弦值m的取值为m＝-0.75。

可选的，第一预设阈值d_max和第二预设阈值d_min满足：d_max＞d_min。

可选的，第一预设阈值d_max和第二预设阈值d_min的取值分别为：d_max＝3，d_max＝2，单位均为米。

第三方面，本申请实施例还提供一种用于矢量轨迹压缩的余弦垂距判别方法，其包括：

存储器与所述存储器相连接的处理器；

所述存储器用于存储程序，所述程序至少用于实现如第一方面任一项所述的方法；

所述处理器用于调用并执行所述存储器存储的所述程序。

本申请的实施例提供的技术方案可以包括以下有益效果：

本申请的实施例提供的技术方案中，首先获取原始矢量轨迹数据集，并构建循环体，然后进行循环时顺序取三个点构成三元组，在对三元组处理时，引入多个判断条件，把每个三元组分成两种层面进行，在点层面先对三元组中间元素(也即第二个点)的前后邻边距离作为条件先识别三元组构成为密集点集或稀疏点集；在线层面通过余弦值作为判断条件将三元组按序连成的局部轨迹识别为曲直线和弯道线两种情况，最后再通过不同垂距阈值d_max和d_min进一步判断是否压缩各情况中的中间顶点元素。整个处理过程考虑多种情况，用多个判断值，相互协同工作，最终把每一个不符合条件的中间点元素进行压缩。相对于现有的处理方法，具有更好的压缩效果和更快的处理速度。

应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本申请。

附图说明

此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本申请的实施例，并与说明书一起用于解释本申请的原理。

图1为本申请实施例提供的一种用于矢量轨迹压缩的余弦垂距判别方法的流程示意图；

图2为本申请实施例提供的压缩前后的矢量轨迹的对比图；

图3为本申请实施例提供的一种用于矢量轨迹压缩的余弦垂距判别方法的具体实现过程示意图；

图4为本申请实施例提供的一种用于矢量轨迹压缩的余弦垂距判别装置的结构示意图；

图5为本申请实施例提供的一种用于矢量轨迹压缩的余弦垂距判别设备的结构示意图。

具体实施方式

这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本申请相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本申请的一些方面相一致的装置和方法的例子。

如背景技术部分指出的，目前的矢量轨迹压缩方法，均存在各自的问题，导致实际应用的场景和效果受限。为了解决这一问题，本申请提供一种用于矢量轨迹压缩的余弦垂距判别方法以及相关的装置和设备。以下通过实施例进行详细说明。

实施例

参照图1，图1为本申请实施例提供的一种用于矢量轨迹压缩的余弦垂距判别方法的流程示意图；如图1所示，该方法至少包括以下流程：

S101：获取原始矢量轨迹数据集pointsList，并构建循环体；所述循环体的长度为原始矢量轨迹数据的长度pointsList.size减2得到的差值pointsList.size-2；循环变量为i，则循环终止条件为i≥pointsList.size-2；

其中，运动物体在地球表面上按某种时间顺序，沿着任意方向移动，则该物体将在地球表面上形成轨迹，用Γ表示为Γ＝{p

S102：每次循环按照索引i开始，按顺序取三个点构成三元组，三个点的下标分别是i、i+1和i+2，并以该三元组构建球面三角形；

也即，在取点构建三元组时，应当按照时间顺序选取连续的三个点，第一个点记为i，第二个点记为i+1，第三个点记为i+2。

S103：利用球面余弦定理分别计算球面三角形的三条边d

其中，关于球面余弦定理，设球面上任意两点p

p

p

d

通过上述球面余弦定理的公式，即可计算得到第一个点到第二个点的距离d

之后，若d

S104：在确定三个点属于密集点集路段时，删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；

具体的，在确定三个点属于密集点集路段时，如果删除第二个点(也即三个点中的中间点)，对原轨迹的改变较小，换言之，如果将原轨迹表示的：从第一个点移动至第二个点再移动至第三个点，替换为：从第一个点直接移动至第三个点时，导致的轨迹变化相对不明显(参见图2(a)，其中箭头左侧为压缩前，右侧为压缩后，虚线为压缩后被删除的轨迹)，因此，本实施例中在确定三个点属于密集点集路段时，删除第二个点，实现对数据集的一次压缩；并在此之后继续循环，且下次循环时以第一个点继续承担下次循环的起始点，从而判断当前三元组的第三个点(当前三元组的第三个点，作为下一三元组的第二个点)是否能够被压缩；

S105：在确定三个点属于稀疏点集路段时，基于计算得到的三条边d

具体的，在确定三个点属于稀疏点集路段时，如果删除第二个点，可能会导致对原轨迹的改变较大(参见图2(b)，其中箭头左侧为压缩前，右侧为压缩后，虚线为压缩后被删除的轨迹)，因此，本实施例中在确定三个点属于稀疏点集路段时，进一步通过其他条件判断是否可以删除第二个点；

本实施例中通过第二个点对应角的余弦值cosθ和底边上的高h来判断，余弦值cosθ和底边上的高h是基于计算得到的三条边d

关于球面三角形面积，设球面上存在任意三点p

p＝(d

于是可以通过此面积求解该球面三角形任意边上的高，即：

关于余弦定理，也即求球面三角形任意夹角余弦值，设球面上存在任意三点p

b

可以推出，

∠p

通过上述公式，即可计算得到底边上的高h和第二个点对应角的余弦值cosθ。

之后，比较cosθ与预设余弦值m的大小(由于θ的取值范围为[0，180°]，因此cosθ的值在θ的取值范围内递减)，若cosθ≤m，则表示θ较大，因此确定当前稀疏点集路段属于曲直路段，通俗来说，也即轨迹的偏转角度较小，轨迹较“直”；否则确定当前稀疏点集路段属于弯道路段，通俗来说，也即轨迹的偏转角度较大，轨迹较“弯曲”。其中，预设余弦值m的取值优选为为m＝-0.75，转换为角度也即θ约为138.6°。

S106：在确定当前稀疏点集路段属于曲直路段时，比较底边上的高h与第一预设阈值d_max的大小；若h≤d_max，则删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；否则，保留第二个点，并以第二个点作为下次循环的起始点，循环继续；

具体的，在确定当前稀疏点集路段属于曲直路段，且h≤d_max时，也即底边所对的角θ较大(比如大于138.6°)且底边上的高h较小时，表明虽然三个点距离较远，但三个点近似在一条直线上，因此，在删除第二个点时，对原轨迹的改变同样较小(参见图2(c)，其中箭头左侧为压缩前，右侧为压缩后，虚线为压缩后被删除的轨迹)，因此，本实施例中删除第二个点，实现对数据集的一次压缩；并在此之后继续循环，且下次循环时以第一个点继续承担下次循环的起始点，从而判断当前三元组的第三个点(当前三元组的第三个点，作为下一三元组的第二个点)是否能够被压缩；否则，也即在h＞d_max时，也即底边上的高h较大时，表明三个点不近似在一条直线上，若删除第二个点，会导致对原轨迹的改变较大(参见图2(d)，其中箭头左侧为压缩前，右侧为压缩后，虚线为压缩后被删除的轨迹)，因此保留第二个点；并在此之后继续循环，且下次循环时以当前三元组的第二个点作为下次循环的起始点。

S107：在确定当前稀疏点集路段属于弯道路段时，比较底边上的高h与第二预设阈值d_min的大小；若h≤d_min，则删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；否则，保留第二个点，并以第二个点作为下次循环的起始点，循环继续；其中，d_max≠d_min；

具体的，在确定当前稀疏点集路段属于弯道路段时，也即底边所对的角θ较小时，若h≤d_min，则表明虽然轨迹较“弯曲”，但三个点近似在一条直线上，因此，在删除第二个点时，对原轨迹的改变同样较小(参见图2(e)，其中箭头左侧为压缩前，右侧为压缩后，虚线为压缩后被删除的轨迹)，因此，本实施例中删除第二个点，实现对数据集的一次压缩；并在此之后继续循环，且下次循环时以第一个点继续承担下次循环的起始点；否则，也即在h＞d_min时，若删除第二个点，对原轨迹的改变较大(参见图2(f)，其中箭头左侧为压缩前，右侧为压缩后，虚线为压缩后被删除的轨迹)，因此保留第二个点，并以第二个点作为下次循环的起始点。

此外，应当理解的是，在具体实现时，优选为第一预设阈值d_max和第二预设阈值d_min满足：d_max＞d_min，比如，一些实施例中，第一预设阈值d_max和第二预设阈值d_min的取值分别为：d_max＝3，d_max＝2，单位均为米。如此设置，由于在确定三个点为密集点集路段时进行压缩的要求，相对三个点为稀疏点集路段时的要求较低，因此设置为d_max＞d_min可以更好地应对路线可能遇到的特殊变化情况。

直至以上循环结束后，即可得到压缩后的矢量轨迹数据集，也即将原始矢量轨迹数据集中可压缩的所有点删除后，剩余的所有点元素就是压缩后新轨迹Γ’中的全部点元素。

本申请的实施例提供的技术方案可以包括以下有益效果：

本申请的实施例提供的技术方案中，首先获取原始矢量轨迹数据集，并构建循环体，然后进行循环时顺序取三个点构成三元组，在对三元组处理时，引入多个判断条件，把每个三元组分成两种层面进行，在点层面先对三元组中间元素(也即第二个点)的前后邻边距离作为条件先识别三元组构成为密集点集或稀疏点集；在线层面通过余弦值作为判断条件将三元组按序连成的局部轨迹识别为曲直线和弯道线两种情况，最后再通过不同垂距阈值d_max和d_min进一步判断是否压缩各情况中的中间顶点元素。整个处理过程考虑多种情况，用多个判断值，相互协同工作，最终把每一个不符合条件的中间点元素进行压缩。相对于现有的处理方法，具有更好的压缩效果和更快的处理速度。

为了使本申请的技术方案更容易理解，以下通过一个具体示例进行举例说明。

参照图3，图3为本申请实施例提供的一种用于矢量轨迹压缩的余弦垂距判别方法的具体实现过程示意图。

如图3所示，首先读取数据，包括出租车，卡车数据文档和青藏科考数据库中的数据得到矢量轨迹数据集；然后以pointsList.size-2构建循环表达式，循环变量i从0开始循环；循环时，不断判断是否满足i＜pointsList.size-2；

满足i＜pointsList.size-2时则压缩结束，得到压缩后的数据集；不满足i＜pointsList.size-2时，则按顺序取三个点构成三元组，并以该三元组构建球面三角形；计算三边球面距离(first，second，third)和中间顶点的余弦值cosθ；之后判断是否满足first≤d_max&&second≤d_max；

若满足first≤d_max&&second≤d_max，则将中间元素从数据集中移出，数据集长度pointsList.size和循环变量i均自减1，为下一次循环从当前i下标元素开始做准备；若不满足first≤d_max&&second≤d_max，先计算球面三角形面积，再计算中间点和底边上的高h；之后判断是否满足cosθ≤-0.75，若满足cosθ≤-0.75，则进一步判断是否h≤d_max，若h≤d_max，则将中间元素从数据集中移出，数据集长度pointsList.size和循环变量i均自减1，为下一次循环从当前i下标元素开始做准备；若h＞d_max，则保留中间元素并进入下一次循环；若不满足cosθ≤-0.75，则进一步判断是否h≤d_min，若h≤d_mmin，则将中间元素从数据集中移出，数据集长度pointsList.size和循环变量i均自减1，为下一次循环从当前i下标元素开始做准备；若h＞d_min，则保留中间元素并进入下一次循环。

此外，对应于上述实施例提供的用于矢量轨迹压缩的余弦垂距判别方法，本申请实施例还提供一种用于矢量轨迹压缩的余弦垂距判别装置。该装置为用于执行上述方法的设备中的基于硬件、软件或二者结合的功能模块。

参照图4，图4为本申请实施例提供的一种用于矢量轨迹压缩的余弦垂距判别装置的结构示意图。如图4所示，该装置至少包括：

循环体构建模块41，用于获取原始矢量轨迹数据集pointsList，并构建循环体；所述循环体的长度为原始矢量轨迹数据的长度pointsList.size减2得到的差值pointsList.size-2；

三角形构建模块42，用于每次循环按照索引i开始，顺序取三个点构成三元组，三个点的下标分别是i、i+1和i+2，并以该三元组构建球面三角形；

路段确定模块43，用于利用球面余弦定理分别计算球面三角形的三条边d

压缩模块44，用于在确定三个点属于密集点集路段时，删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；

以及，在确定三个点属于稀疏点集路段时，基于计算得到的三条边d

以及，在确定当前稀疏点集路段属于曲直路段时，比较底边上的高h与第一预设阈值d_max的大小；若h≤d_max，则删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；否则，保留第二个点，并以第二个点作为下次循环的起始点，循环继续；

以及，在确定当前稀疏点集路段属于弯道路段时，比较底边上的高h与第二预设阈值d_min的大小；若h≤d_min，则删除第二个点，并使原始矢量轨迹数据集的长度pointsList.size自减1，同时循环变量i自减1，并以第一个点继续承担下次循环的起始点，循环继续；否则，保留第二个点，并以第二个点作为下次循环的起始点，循环继续；其中，d_max≠d_min；直至循环结束后，得到压缩后的矢量轨迹数据集。

可选的，预设余弦值m的取值为m＝-0.75。

可选的，第一预设阈值d_max和第二预设阈值d_min满足：d_max＞d_min。

可选的，第一预设阈值d_max和第二预设阈值d_min的取值分别为：d_max＝3，d_max＝2，单位均为米。

其中，上述装置中各模块所执行的步骤的具体实现方法可以参照前述方法实施例，此处不再赘述。

此外，对应于上述实施例提供的用于矢量轨迹压缩的余弦垂距判别方法，本申请实施例还提供一种用于矢量轨迹压缩的余弦垂距判别设备。该设备为用于执行上述方法的智能设备，例如PC。

参照图5，图5为本申请实施例提供的一种用于矢量轨迹压缩的余弦垂距判别设备的结构示意图。如图3所示，该设备至少包括：

存储器31和与存储器31相连接的处理器32；

存储器31用于存储程序，所述程序至少用于实现上述方法实施例所述的用于矢量轨迹压缩的余弦垂距判别方法；

处理器32用于调用并执行存储器31存储的所述程序。

其中，所述程序所实现的方法的各步骤的具体实现方法可以参照前述方法实施例，此处不再赘述。

应用本申请的上述方案，整个处理过程考虑多种情况，用多个判断值，相互协同工作，最终把每一个不符合条件的中间点元素进行压缩。相对于现有的处理方法，具有更好的压缩效果和更快的处理速度。

可以理解的是，上述各实施例中相同或相似部分可以相互参考，在一些实施例中未详细说明的内容可以参见其他实施例中相同或相似的内容。

需要说明的是，在本申请的描述中，术语“第一”、“第二”等仅用于描述目的，而不能理解为指示或暗示相对重要性。此外，在本申请的描述中，除非另有说明，“多个”的含义是指至少两个。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本申请的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本申请的实施例所属技术领域的技术人员所理解。

应当理解，本申请的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(PGA)，现场可编程门阵列(FPGA)等。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，该程序在执行时，包括方法实施例的步骤之一或其组合。

此外，在本申请各个实施例中的各功能单元可以集成在一个处理模块中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。所述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机可读取存储介质中。

上述提到的存储介质可以是只读存储器，磁盘或光盘等。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本申请的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

尽管上面已经示出和描述了本申请的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本申请的限制，本领域的普通技术人员在本申请的范围内可以对上述实施例进行变化、修改、替换和变型。