A Geometric Framework for Detection of Critical Points in a Trajectory Using Convex Hulls

Abstract

Large volumes of trajectory-based data require development of appropriate data manipulation mechanisms that will offer efficient computational solutions. In particular, identification of meaningful geometric points of such trajectories is still an open research issue. Detection of these critical points implies to identify self-intersecting, turning and curvature points so that specific geometric characteristics that are worth identifying could be denoted. This research introduces an approach called Trajectory Critical Point detection using Convex Hull (TCP-CH) to identify a minimum number of critical points. The results can be applied to large trajectory data sets in order to reduce storage costs and complexity for further data mining and analysis. The main principles of the TCP-CH algorithm include computing: convex areas, convex hull curvatures, turning points, and intersecting points. The experimental validation applied to Geolife trajectory dataset reveals that the proposed framework can identify most of intersecting points in reasonable computing time. Finally, comparison of the proposed algorithm with other methods, such as turning function shows that our approach performs relatively well when considering the overall detection quality and computing time.