计算机应用 ›› 2014, Vol. 34 ›› Issue (8): 2409-2414.DOI: 10.11772/j.issn.1001-9081.2014.08.2409

• 行业与领域应用 • 上一篇    下一篇

基于最小边界扇形的移动对象轨迹实时化简算法

王欣然,杨智应   

  1. 上海海事大学 信息工程学院,上海201306
  • 收稿日期:2014-02-28 修回日期:2014-04-17 出版日期:2014-08-01 发布日期:2014-08-10
  • 通讯作者: 王欣然
  • 作者简介:王欣然(1989-),男,河南沈丘人,硕士研究生,主要研究方向:移动对象数据库;杨智应(1964-),男,广西钟山人,教授,博士,主要研究方向:算法与复杂性、移动计算、分布式计算、软件工程。
  • 基金资助:

    上海海事大学研究生创新基金资助项目

Real-time trajectory simplification algorithm of moving objects based on minimum bounding sector

WANG Xinran,YANG Zhiying   

  1. College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China
  • Received:2014-02-28 Revised:2014-04-17 Online:2014-08-01 Published:2014-08-10
  • Contact: WANG Xinran

摘要:

为了对全球定位系统(GPS)设备采集到的移动对象原始轨迹数据进行简化,提高轨迹数据的使用效率,降低移动终端的通信代价和计算开销,提出了一种基于最小边界扇形(MBS)的移动对象轨迹实时化简算法。该算法不同于用一条折线来近似原始轨迹的方法,它利用扇形预测范围来估计、简化原始轨迹,在角度和距离两个层面上对简化误差进行控制。提出了新的误差度量方法——基于等极径的误差度量方法,并讨论了GPS定位误差对简化算法的影响。实验结果表明,所提算法的简化轨迹高效、稳定,所得到的简化轨迹与原始轨迹之间误差较小(不超过误差阈值的20%),对GPS定位误差有较好的容错能力。

Abstract:

To improve the efficiency of the application of trajectory data, reduce communication cost and computational overhead of mobile terminal, the raw trajectory data of moving objects which were collected by Global Positioning System (GPS) equipment must be simplified. A method based on Minimum Bounding Sector (MBS) for real-time trajectory simplification of moving objects was proposed. The algorithm is different from those which approximated the original trajectory with a polygonal line. It adopted sector to predict the moving range, which could estimate and simplify the original trajectory. In order to control simplification error efficiently, the identical polar radius error metric method was proposed based on the characteristics of sector angle and distance. In addition, the affect of GPS positioning error on the simplified algorithm was discussed. The experimental results show that, the simplified trajectory of the proposed algorithm is efficient and stable, it has smaller error (no more than 20% of the error threshold) in comparison with the original trajectory and has good fault tolerant ability on GPS positioning error.

中图分类号: