本文主要是介绍Opening Window Time Ratio (OPW-TR) 的多线程实现 C/C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题目要求
Opening Window Time Ratio (OPW-TR) 的多线程实现C/C++
2.需求分析
近年来，GPS设备被广泛应用。根据Canalys（一个信息公司）报告, 在2006到2007一年间，GPS设备销售增加了116%。 2009年，据估计有2700万安装了GPS设备的手机被销售。截止2009年，有6.8亿的GPS用户。这是设备都能够产生、存储和传输轨迹数据。
随着基于位置的服务应用（Location basedservice, LBS）广泛使用轨迹数据，有如下3个主要问题：
（1）存储开销问题：假设轨迹数据在没有压缩的情况下，以每10s采集一次，一天仅仅4000个移动对象就会产生1Gb的数据。这样，对海量轨迹数据的存储和查询将是一个巨大的问题；
（2）传输开销问题：移动手机或是传输网络传送轨迹数据的代价是昂贵的，一般 5-7美元/M。假设跟踪4000车辆，一天的费用就是5000-7000美元，一年就是1,800,000 – 2,500,000美元。
（3）计算开销问题：随着轨迹数据规模的增加，很难快速地从轨迹数据中发现有用的模式。而减少轨迹数据的规模可以加速轨迹数据模式挖掘的速度。
这三个问题的出现使得数据压缩算法快速的发展，这里我们采用常规开放窗口算法对数据进行在线压缩
3.问题分析
l 采用开放式窗口算法标识一个潜在压缩数据段的开始点。
l 如果压缩效果好，然后尝试去压缩更长的数据段。
l 在线压缩过程从定义一段数据开始：起始点（第一个数据）到浮动点（第三个数据）。
l 如果这段数据中的每个点的误差都低于一个距离阈值，尝试移动浮动点一个点。
（1）当即将超出阈值时，两个策略中的一个被实施：
a.常规开放窗口(NormalOpening Window, NOPW): 导致阈值变化的数据点成为当前段的尾端点，成为下一个段的标签点。
b.前置开放窗口(BeforeOpening Window, BOPW):导致阈值变化的数据点的前一数据点当前段的尾端点，成为下一个段的标签点。
如果没有超越阈值，浮动一位（即窗口近一步开放），整个过程如此循环，只到所有数据被转换。
（2）常规开放窗口(NOPW)策略：阈值超过数据点是断开点,如图1所示， 在这条移动数据轨迹中总共有16个移动数据轨迹点，而我们通过NOPW算法对移动数据轨迹点进行压缩，存取其中的五个点（0，4，8，12，16）来近似的模拟出移动数据轨迹。如果压缩效果好，然后尝试去压缩更长的数据段。在线压缩过程从定义一段数据开始：起始点（第一个数据）到浮动点（第三个数据）。导致阈值变化的数据点成为当前段的尾端点，成为下一个段的标签点。如果没有超越阈值，浮动一位（即窗口近一步开放），整个过程如此循环，直到所有数据被转换。
图1
（3）前置开放窗口(BOPW)策略：在阈值超过数据点前一个数据点是断开点。OPW算法能够在有噪音的较短数据序列中进行压缩，其时间复杂度为O(n2)，如图2所示。
图2
Opening Window Time Ratio (OPW-TR) 是一个对OPW的扩展。OPW-TR利用SED(synchronized euclidean distance) 代替spatial error。相对OPW， OPW-TR把时间维度考虑进去。类似OPW， OPW-TR的时间复杂度也是O(n2)
（4）集中压缩方法比较如下表所示：
4.模块设计
首先定义移动数据轨迹点的结构体
struct point
{
float x; //轨迹点的横坐标
float y; //轨迹点的纵坐标
int t; //轨迹点所处的时刻t
};
然后分为两个模块（输入模块和压缩模块）来实现移动数据轨迹压缩
（1） 输入模块
通过设置一个循来依次输入压缩轨迹经过的轨迹点
point p[16];
printf("请输入压缩轨迹经过几个点\n");
int n; //压缩轨迹经过的点
scanf_s("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入第%d个轨迹点横坐标\n",i);
scanf_s("%f",&p[i].x);
printf("请输入第%d个轨迹点纵坐标\n",i);
scanf_s("%f",&p[i].y);
printf("请输入第%d个轨迹点时刻\n",i);
scanf_s("%d",&p[i].t);
}
（2） 压缩模块
分为两层循环，大循环保证这条数据轨迹上的压缩数据轨迹段的移动，判断压缩的数据轨迹段是否压缩完成，是否要开始压缩新的数据轨迹段。小循环保证其中的一段数据轨迹上数据轨迹点的移动，当数据轨迹段上所有的点都不超过阈值，则移动尾端点到下一个点，重新开始压缩新的数据轨迹段，当其中有点超过阈值，则将它压缩存储进来并作为下个数据压缩轨迹段的起始点，当所有的数据轨迹点经过这两层循环后，就能把压缩的数据点存储起来。如图3所示。
图3
for(;qishi<=13;) //大循环直到检测到最后一个数据段终止
{
if((p[zhongzhi+1].x)-p[qishi].x!=0)
{
k=(p[zhongzhi+1].y-p[qishi].y)/(p[zhongzhi+1].x-p[qishi].x);
}
else
{
k=10000; //起始点和终止点横坐标相同，设斜率为无穷大
}
b=p[qishi].y-k*p[qishi].x;
float d; //d为点到直线的距离
for(;qishi<=zhongzhi;qishi++) //循环检测起始点到终止点这段数据中每个点和阈值的关系
{
int t=qishi; //保留一个原始的起始值
d=(k*p[qishi].x-p[qishi].y+b)/(sqrt(k*k+1)); //点到直线距离公式
if(d>m) //如果点到直线的距离超过阈值，则将它设为断开点，并存储在q数组里
{
q[count].x=p[qishi].x;
q[count].y=p[qishi].y;
q[count].t=p[qishi].t;
count++;
zhongzhi=qishi+2; //新的数据段
break; //跳出循环，开始检测下一个数据段
}
else if(qishi==zhongzhi) //检测到整个数据段的点到直线距离都小于阈值
{
zhongzhi=zhongzhi+1; //将终止点往后移动一位
qishi=t; //将起始点回复成原来位置
}
}
}
5.运行结果
压缩轨迹数据点
（0，0，0）
（1，1，1）
（2，1，2）
（3，2，3）
（4，1，4）
（5，6，5）
（6，7，6）
（7，8，7)
（8 ,6, 8）
（9，1，9）
（10，2，10）
（11，6，11）
（12，10，12）
（13，7，13）
（14，6，14）
（15，1，15）
源代码及测试数据下载网址：http://download.csdn.net/detail/bryank/9532411
这篇关于Opening Window Time Ratio (OPW-TR) 的多线程实现 C/C++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
