# Clustering Moving Object Trajectories: Integration in CROSS-CPP Analytic Toolbox
## 3 Preliminaries  
Prior to presenting the approach to cluster trajectories, some preliminary definitions are introduced. A trajectory is the path followed by a moving object. Formally, a trajectory \(s\) is defined as a chronological sequence of multi-dimensional locations, which is denoted by \(s=P1,P2,...,P_{n}\), with \(n\) being the number of points. Each point \(P_{n}\) is represented as \(Location_{j}\)-tuple at time \(T_{j}\)[9]. The concept of distance among trajectories refers to the criteria to measure the similarity of trajectories. In this paper, the similarity focuses on the geometric patterns of trajectories. Two trajectories are identical if they have the same length and are defined by the same positions independently of the time. This kind of similarity is well-suited for analysis of routes in cities and countries, such as commuting routes from homes to work places, hot-spot areas and holiday road trips. The geodesic distance is the shortest distance between two points located on the surface of the Earth, and there are several models to compute this distance:  
* Harvesine, or half of the verseine, which is the central angle (\(\Theta\)) between two points in an sphere: \[\Theta=\frac{d}{r}\] (1) where \(d\) is the distance between two points along a great circle of the sphere and \(r\) is the radius of the sphere. The Havesine (\(hav(\Theta)\)) is computed directly from the latitude and longitude of the two points: \[hav(\Theta)=hav(\varphi_{2}-\varphi_{1})+\cos\varphi_{1}\cos\varphi_{2}\,hav( \lambda_{2}-\lambda_{1})\] (2) where \(\varphi_{2}\), \(\varphi_{1}\) are the latitude of point 1 and 2. \(\lambda_{2},\lambda_{1}\) is the longitude of points 1 and 2. The havesine function computes half a verseine of the angle \(\theta\): \[hav(\theta)=\sin^{2}\frac{\theta}{2}\] (3) Then the distance between the two points: \[d=r\,archav(hav(\Theta))=2r\,\arcsin(\sqrt{hav(\Theta)})\] (4) \[d=2r\,\arcsin(\sqrt{hav(\varphi_{2}-\varphi_{1})+\cos\varphi_{1}\cos\varphi_{2 }\,hav(\lambda_{2}-\lambda_{1}))}\]
* Great circle distance [15]: In geometry, the great circle is defined as the intersection between a plane and a sphere that passes through the center of the sphere. This formula was manually implemented, and it is defined as follows: \[d=R\arccos\left(\sin\varphi_{2}*\sin\varphi_{1}+\cos\varphi_{2}*\cos\varphi_{1 }*\cos\left(\lambda_{2}-\lambda_{1}\right)\right)\] (5) where the \(d\) is the distance, \(R\) is the Earth radius, a constant with \(R=6371\) km, and the same notation as before for the latitude (\(\varphi\)) and longitude (\(\lambda\)) of each point. * Euclidean: by neglecting the curvature of the Earth, the euclidean distance between the two points is defined: \[d=\sqrt{(\varphi_{2}-\varphi_{1})^{2}+(\lambda_{2}-\lambda_{1})^{2}}\] (6)
* Geodesic WS84 [15]: in this case, the model of the Earth is an ellipsoid; in particular, the WS84 is the most globally accurate model. The used implementation is that included in the GeoPy library. All the metrics defined above are suitable to calculate distances between two points. To compute distance among trajectories, different approaches have been proposed [9; 19; 20]. These approaches distinguish between trajectories defined by the same number of points or dissimilar. In the case of trajectories defined by the same number of points and lineal time complexity, there are two distances that have been used in moving objects data:the euclidean and the Hausdorff [21]. In this paper, we explored the use of Minimum Direct-Flip (MDF) [13], see Equation (7). \[ \begin{split} d_{direct}(s,t)=d(s,t)=\frac{1}{K}\sum|s_{i}-t_{i}|, \\ d_{flipped}(s,t)=d(s,t^{F})=d(s^{F},t)\\ MDF(s,t)=min(d_{direct}(s,t),d_{flipped}(s,t))\end{split}  \tag{7}\]  
where \(|s_{i}-t_{i}|\) denotes the Euclidean distances between two points, \(s\) is a trajectory and \(t\) is the mean of the Euclidean distance. Figure 1 provides an insight of the working of the metric. Quickbundles (QB) [13] is a clustering algorithm with linear time performance with respect to the number of trajectories.