# Simplified Algorithm of Moving Object Trajectory Based on Interval Floating

Authors: Xuesong Chen; Zhiying Yang; Yingjie Liu
Journal: Mobile Information Systems
 (2022)

---

## Abstract

This paper proposes an online trajectory simplification algorithm based on interval floating. The accumulated angle deviation is used in the algorithm, and the bounded error theorem of interval floating is presented. First, the accumulated angle deviation starts from the nearest reserved point. Next, the sum of the angle deviations generated by the subsequent trajectory points is continuously calculated. When the simplified threshold is reached for the first time, it is will be judged whether the simplified threshold interval needs to be floated as well as the next reservation in the floating error interval. It is worth noting that the interval between two adjacent reserved points floats only once. The algorithm is tested on real trajectory data, and the experimental results show that the algorithm has an improved simplification rate with a certain simplification error.


---

## Body

## 1. Introduction

In the 21st century, with the advent of 4G and 5G mobile communication technologies, the higher popularity of the Internet has considerably promoted social progress. Besides, big data-related research becomes the hot spot globally. Also, mobile computing has been constantly evolving along with technologies such as mobile object databases and mobile communication network coverage. The location information of mobile terminal equipment keeps changing with time, and GPS and RFID are currently used as the main data collection equipment. Researchers employ the collected trajectory data to study the characteristics of moving objects and apply them in areas such as smart transportation and location-based services (LBS) [1, 2]. Location-based personalized service technology is a field that has been thriving in recent years. In terms of personalized recommendation, there are location recommendation [3], travel prediction [4], and user behavior analysis [5]. The basis of all LBS research is positioning, and a large amount of user location data needs to be obtained. However, many data in the stored massive trajectory data are of little research significance, which increases the difficulty of the subsequent scientific research analysis, causing huge capital and workload wasted in existing storage technology. In order to reduce the storage cost, more attention has been drawn to the research topic of trajectory simplification of moving objects. Many excellent trajectory simplification algorithms have been reported, but the development of trajectory simplification algorithms is still relatively slow, and each simplification algorithm has its own limitations. Many algorithms have their own specific application scenarios, and it is necessary to develop new simplification algorithms to broaden the spectrum of trajectory simplification so as to cope with various types of trajectory data sets in the future; in addition, most online algorithms use buffers since interval algorithms often have high time complexity. Therefore, it is necessary to explore new low-cost trajectory simplification algorithms.So far, some related research has focused on the simplification algorithm of moving object trajectory. When the trajectory data simplification algorithm was first applied to computer graphics, the initially processed data only contained spatial information. Therefore, Euclidean distance (PED) was widely used. However, the data collected by the GPS system records time information in addition to space information. If we continue to use PED to study the simplified algorithm of moving object trajectories, we will inevitably lose time information. Therefore, the synchronized Euclidean distance (SED) is gradually applied to the trajectory simplification algorithm. Many studies on trajectory simplification algorithms show that researchers mainly delve into two dimensions: offline simplification and online simplification.The advantage of online trajectory simplification is that it supports real-time applications and can compress trajectory data while picking up new trajectory points as they are acquired. Offline trajectory simplification starts compressing only after all points are acquired from the input trajectory and is suitable for analysing historical trajectory data. Offline trajectory simplification usually has fewer errors compared to online trajectory simplification. However, in many applications, the trajectory data of the moving objects arrive in a stream, such as real-time AIS information received by shore-based systems. These applications include real-time trajectory tracking and position monitoring. Therefore, some online trajectory simplification methods have been proposed to handle this situation.The earliest offline trajectory simplification algorithm based online segments is the Douglas–Peucker algorithm (DP algorithm) proposed in 1973 [6]. The DP algorithm needs to give the threshold of the simplified algorithm in advance. The threshold uses PED, and the algorithm is simplified according to the setting. The threshold recursively selects points greater than the simplified threshold and keeps the algorithm running until all points are less than the threshold set by the simplified algorithm. The TD-TR algorithm (also known as the top-down time ratio algorithm) was proposed by Meratnia and De [7]. Compared with the traditional DP algorithm, the TD-TR algorithm overcomes the shortcomings of the DP algorithm, for example, losing time information. TD-TR uses SED instead in the distance function of the DP algorithm because SED not only retains position but also time information compared with PED distance. Lin et al. [8] proposed the ATS algorithm. The ATS algorithm segments the original trajectory according to the important feature of the trajectory speed, calculates the SED threshold of the small trajectory, and finally uses the DP algorithm to simplify the final trajectory. Ke et al. [9] proposed the Angular algorithm, which uses the accumulated angle deviation to select or reject the trajectory point. By setting the accumulated angle threshold, the angle error before and after the trajectory simplification can be controlled. The time complexity is O (n). Opening Window (OW) is a traditional online trajectory simplification algorithm. The core idea of OW is to initialize a window with a fixed size from the starting point of the trajectory and slide the window over the points on the original trajectory. This process is repeated until the last point of the original trajectory is processed [10]. Opening Window Time Ratio (OW-TR) [7] extended OPW using a synchronized Euclidean distance (SED) error instead of the spatial error. A number of successful online trajectory simplification algorithms have been proposed to simplify the road vehicle trajectories, terrain boundary line, trajectory data mining, and graphics display [11, 12]. Trajcevski et al. [13] proposed an online algorithm called Dead Reckoning, which uses the idea of estimation to estimate subsequent trajectory points. Muckell et al. [14] proposed the SQUISH algorithm, which will add new points directly to the buffer when there is still space in it. When the buffer is full, the algorithm deletes the point with the smallest error. The removal of small information points increases the importance of the left and right points of the discarded points in the area. The trajectory simplified by the algorithm has a reliable error guarantee, and the algorithm can be flexibly adjusted through the simplification rate and error. SQUISH-E [14] can achieve the smallest error under the condition of an artificially given simplification rate. The worst-case time complexity of the algorithm is O (nlogn/β), β represents the artificially set simplification rate. Although it is an online trajectory simplification algorithm, in fact, under the condition of an artificially given simplification rate, the SQUISH algorithm can only perform offline trajectory simplification, and the algorithm needs to repeatedly traverse all points in the original trajectory, which is time-complex. In the most extreme case, the error between the original trajectory and the simplified trajectory will be very considerable.The main innovations and contributions of this paper include as follows: (1) The bounded error theorem of interval floating is proposed, which can fully simplify the trajectory with a certain simplification error. (2) An online trajectory simplification algorithm is presented and implemented, which can simplify trajectory data online. (3) Various experiments were conducted from different data set sizes and different angle thresholds to evaluate the time performance and simplification rate performance of the algorithm. Through experimental comparison, in the face of large-scale trajectory data, the proposed algorithm has better time complexity and simplification rate.


## 2. Related Definitions and Lemmas of Algorithms

### 2.1. Definition 1: Angle Difference of Trajectory Segment [9]

Define the direction angleθ of the trajectory segment as follows: the directions of the trajectory segment pipj¯ and pmpk¯ are denoted by θpipj¯ and θpmpk¯, respectively, and the constraints are(1)θ∈0,2π,1≤i<j≤n,1≤m<k≤n.The angle difference formula is(2)∆θ=θpipj¯−θpmpk¯.For two given anglesθ1 and θ2, the magnitude of their angle difference is(3)minθ1−θ2,2π−θ1−θ2.The angle difference∆θ1,θ2 is divided into two cases, θ1−θ2 and 2π−θ1−θ2 (see Figure 1). Easy to get by definition, the range of angle difference is [0, π].Figure 1
(a), (b), and (c), respectively, show how the angle difference of the trajectory segment is calculated in different situations.
(a)(b)(c)


### 2.2. Definition 2: Angular Deviation of Trajectory Segment [9]

The angle of the moving object at pointpi and the angle change between the points before and after it is the angle deviation of the point, which is represented by the symbol pi.ϵd, and the details are as follows:(4)∆θ=θpipi+1¯−θpi−1pi¯,pi.ϵd=∆θ+2π,∆θ≤−π,∆θ,−π<∆θ≤π,∆θ−2π,∆θ>π.pi.ϵd has a positive value and a negative value (see Figure 2), p2.ϵd and p3.ϵd represent the angle deviation of point p2 and point p3, respectively.Figure 2
Schematic diagram of the calculation method of the angle deviation of each point.


### 2.3. Definition 3: Cumulative Angular Deviation [9]

The meaning of the cumulative angle deviation is the cumulative sum of the angle deflection of all points from the count point to the current point, which is defined as follows:(5)pi.ϵd=0,i=sk,∑m=sk+1ipm.ϵd,sk<i<sk+1.It should be noted thatpsk represents the starting point of the simplified trajectory segment pskpsk+1¯, psk+1 is the end point of the trajectory segment, and the subscript of the trajectory segment needs to satisfy the constraint: sk<i<sk+1.


### 2.4. Lemma 1: Bounded Error of Position Information [15]

The trajectory simplification algorithm that retains the direction information generally achieves the purpose of simplification by constraining the direction of the trajectory, which can ensure a certain direction error. In fact, the algorithm also retains the position information while retaining the direction information. Long et al. [15] proved that the direction-preserving algorithm can maintain the position characteristics. The following introduces the bounded error lemma of position information:In the simplified algorithm that preserves direction information, if the simplified error is withinε, then the shortest vertical Euclidean distance dminped and ε of the original trajectory and the simplified trajectory must satisfy the following relationship:(6)dminped≤12lmaxtanε.Among them,lmax represents the maximum length of the original trajectory segment corresponding to the simplified trajectory segment in the simplified trajectory.Proof.
Letpskpsk+1¯ be a simplified trajectory segment selected arbitrarily. Among them, we stipulate that psk is the starting point of the simplified trajectory section, and psk+1 is the end point of the simplified trajectory section. Then, the simplification of the current trajectory section must satisfy the directional error within ε. For a simplified trajectory segment pskpsk+1¯ selected at random, we can construct a rhombus according to pskpsk+1¯ (see Figure 3), and prove the theorem in the rhombus.
In the rhombus in the figure above, there is a relationship:∆pska¯,pskpsk+1¯=ε. Assuming that the position of pi is outside the rhombus, then there must be a situation where pi is below pska¯. Therefore, there is a difference between the unsimplified trajectory segment pj−1pj¯ and the simplified trajectory segment pska¯. There must be an intersection point between them. If the position of pi is outside the rhombus, the direction error between the original trajectory segment pj−1pj¯ and the simplified trajectory segment pskpsk+1¯ must be greater than ε. So far, the conclusion drawn is in contradiction with our original definition of the direction angle error. So it is deduced that pi must exist within the rhombus constructed by the simplified trajectory segment pskpsk+1¯. So, it is concluded that even the point pi farthest from the simplified trajectory segment pskpsk+1¯ must satisfy the following constraints:(7)dminped≤12lmaxtanε.
Among them, distance represents the vertical Euclidean distance between two elements in the calculation plane, which can be the distance from point to point or point to straight line.Figure 3
Rhombuses constructed from trajectory segments.


### 2.5. Lemma 2: Bounded Error of Direction [9]

The results and discussion may be presented separately, or in one combined section and may optionally be divided into headed subsections. Ke et al. [9] proposed the bounded error theorem of direction in the A algorithm and proved the theorem. The accumulated angle deviation used by the A algorithm is based on the bounded error theorem of direction. The following will prove that the accumulated angular deviation is a bounded error in direction.Assuming that the artificially prescribed direction thresholdpi.εd is εt, for each original trajectory point pi, if the cumulative angle deviation pi.εd of point pi is greater than the given εt, then pi will be retained. The direction error between the final simplified trajectory and the original trajectory must obey the following constraints:(8)εT′<2εt.Proof.
According to the relevant definition introduced above, for a random segment of trajectory segmentpskpsk+1¯, the direction of the trajectory segment pipi+1¯ composed of connected trajectory points between psk and psk+1 can be derived. The specific expression is as follows:(9)ψ=θpskpsk+1¯+∑m=sk+1ipm.εd.
Among them, thepsk is the starting point, psk+1 is the end point, and psk+1, psk+2, psk+3... etc. represent the trajectory points between psk and psk+1.
For the random trajectory segmentpskpsk+1¯, the trajectory segment pipi+1¯ composed of all the adjacent trajectory points in pskpsk+1¯ satisfies the angle constraint θpskpsk+1¯−εt,θpskpsk+1¯+εt (see Figure 4). In other words, for all the trajectory segments pipi+1¯, the direction of pipi+1¯ must be within the εt error in the direction of the first small trajectory segment pskpsk+1.
The vectorpskpsk+1⟶ in the rhombus (see Figure 3) can be expressed as follows:(10)pskpsk+1⟶=pska⟶+apsk+1⟶.
According to (11), it can be seen that the vector sum of the geometric vectors formed by all two adjacent trajectory points in pskpsk+1⟶ can be finally expressed as pskpsk+1⟶, then the following constraints must be derived:(11)θpskpsk+1¯−εt<θpskpsk+1¯<θpskpsk+1¯+εt.
According to the above proofs, the direction angle error of any deleted track segment in the original trajectory is controlled within the range ofε from the original trajectory.
Therefore, when running the trajectory simplification algorithm, setting the algorithm’sεt to half of ε can realize that the error between the simplified trajectory and the original trajectory is within ε.Figure 4
Directional error range chart.


## 2.1. Definition 1: Angle Difference of Trajectory Segment [9]

Define the direction angleθ of the trajectory segment as follows: the directions of the trajectory segment pipj¯ and pmpk¯ are denoted by θpipj¯ and θpmpk¯, respectively, and the constraints are(1)θ∈0,2π,1≤i<j≤n,1≤m<k≤n.The angle difference formula is(2)∆θ=θpipj¯−θpmpk¯.For two given anglesθ1 and θ2, the magnitude of their angle difference is(3)minθ1−θ2,2π−θ1−θ2.The angle difference∆θ1,θ2 is divided into two cases, θ1−θ2 and 2π−θ1−θ2 (see Figure 1). Easy to get by definition, the range of angle difference is [0, π].Figure 1
(a), (b), and (c), respectively, show how the angle difference of the trajectory segment is calculated in different situations.
(a)(b)(c)


## 2.2. Definition 2: Angular Deviation of Trajectory Segment [9]

The angle of the moving object at pointpi and the angle change between the points before and after it is the angle deviation of the point, which is represented by the symbol pi.ϵd, and the details are as follows:(4)∆θ=θpipi+1¯−θpi−1pi¯,pi.ϵd=∆θ+2π,∆θ≤−π,∆θ,−π<∆θ≤π,∆θ−2π,∆θ>π.pi.ϵd has a positive value and a negative value (see Figure 2), p2.ϵd and p3.ϵd represent the angle deviation of point p2 and point p3, respectively.Figure 2
Schematic diagram of the calculation method of the angle deviation of each point.


## 2.3. Definition 3: Cumulative Angular Deviation [9]

The meaning of the cumulative angle deviation is the cumulative sum of the angle deflection of all points from the count point to the current point, which is defined as follows:(5)pi.ϵd=0,i=sk,∑m=sk+1ipm.ϵd,sk<i<sk+1.It should be noted thatpsk represents the starting point of the simplified trajectory segment pskpsk+1¯, psk+1 is the end point of the trajectory segment, and the subscript of the trajectory segment needs to satisfy the constraint: sk<i<sk+1.


## 2.4. Lemma 1: Bounded Error of Position Information [15]

The trajectory simplification algorithm that retains the direction information generally achieves the purpose of simplification by constraining the direction of the trajectory, which can ensure a certain direction error. In fact, the algorithm also retains the position information while retaining the direction information. Long et al. [15] proved that the direction-preserving algorithm can maintain the position characteristics. The following introduces the bounded error lemma of position information:In the simplified algorithm that preserves direction information, if the simplified error is withinε, then the shortest vertical Euclidean distance dminped and ε of the original trajectory and the simplified trajectory must satisfy the following relationship:(6)dminped≤12lmaxtanε.Among them,lmax represents the maximum length of the original trajectory segment corresponding to the simplified trajectory segment in the simplified trajectory.Proof.
Letpskpsk+1¯ be a simplified trajectory segment selected arbitrarily. Among them, we stipulate that psk is the starting point of the simplified trajectory section, and psk+1 is the end point of the simplified trajectory section. Then, the simplification of the current trajectory section must satisfy the directional error within ε. For a simplified trajectory segment pskpsk+1¯ selected at random, we can construct a rhombus according to pskpsk+1¯ (see Figure 3), and prove the theorem in the rhombus.
In the rhombus in the figure above, there is a relationship:∆pska¯,pskpsk+1¯=ε. Assuming that the position of pi is outside the rhombus, then there must be a situation where pi is below pska¯. Therefore, there is a difference between the unsimplified trajectory segment pj−1pj¯ and the simplified trajectory segment pska¯. There must be an intersection point between them. If the position of pi is outside the rhombus, the direction error between the original trajectory segment pj−1pj¯ and the simplified trajectory segment pskpsk+1¯ must be greater than ε. So far, the conclusion drawn is in contradiction with our original definition of the direction angle error. So it is deduced that pi must exist within the rhombus constructed by the simplified trajectory segment pskpsk+1¯. So, it is concluded that even the point pi farthest from the simplified trajectory segment pskpsk+1¯ must satisfy the following constraints:(7)dminped≤12lmaxtanε.
Among them, distance represents the vertical Euclidean distance between two elements in the calculation plane, which can be the distance from point to point or point to straight line.Figure 3
Rhombuses constructed from trajectory segments.


## 2.5. Lemma 2: Bounded Error of Direction [9]

The results and discussion may be presented separately, or in one combined section and may optionally be divided into headed subsections. Ke et al. [9] proposed the bounded error theorem of direction in the A algorithm and proved the theorem. The accumulated angle deviation used by the A algorithm is based on the bounded error theorem of direction. The following will prove that the accumulated angular deviation is a bounded error in direction.Assuming that the artificially prescribed direction thresholdpi.εd is εt, for each original trajectory point pi, if the cumulative angle deviation pi.εd of point pi is greater than the given εt, then pi will be retained. The direction error between the final simplified trajectory and the original trajectory must obey the following constraints:(8)εT′<2εt.Proof.
According to the relevant definition introduced above, for a random segment of trajectory segmentpskpsk+1¯, the direction of the trajectory segment pipi+1¯ composed of connected trajectory points between psk and psk+1 can be derived. The specific expression is as follows:(9)ψ=θpskpsk+1¯+∑m=sk+1ipm.εd.
Among them, thepsk is the starting point, psk+1 is the end point, and psk+1, psk+2, psk+3... etc. represent the trajectory points between psk and psk+1.
For the random trajectory segmentpskpsk+1¯, the trajectory segment pipi+1¯ composed of all the adjacent trajectory points in pskpsk+1¯ satisfies the angle constraint θpskpsk+1¯−εt,θpskpsk+1¯+εt (see Figure 4). In other words, for all the trajectory segments pipi+1¯, the direction of pipi+1¯ must be within the εt error in the direction of the first small trajectory segment pskpsk+1.
The vectorpskpsk+1⟶ in the rhombus (see Figure 3) can be expressed as follows:(10)pskpsk+1⟶=pska⟶+apsk+1⟶.
According to (11), it can be seen that the vector sum of the geometric vectors formed by all two adjacent trajectory points in pskpsk+1⟶ can be finally expressed as pskpsk+1⟶, then the following constraints must be derived:(11)θpskpsk+1¯−εt<θpskpsk+1¯<θpskpsk+1¯+εt.
According to the above proofs, the direction angle error of any deleted track segment in the original trajectory is controlled within the range ofε from the original trajectory.
Therefore, when running the trajectory simplification algorithm, setting the algorithm’sεt to half of ε can realize that the error between the simplified trajectory and the original trajectory is within ε.Figure 4
Directional error range chart.


## 3. Trajectory Simplification Algorithm Based on Interval Floating

### 3.1. Theorem: Bounded Error of Interval Float

This paper proposes the theorem: Bounded Error of Interval Float.If the current trajectory pointpi.εa is in the interval εt<pi.εa<2εt, the algorithm performs a floating operation, that is, the accumulated angle deviation interval that needs to be discarded to simplify the trajectory floats from −εt,εt to min_εa,2εt+min_εa; if the current trajectory point satisfies the accumulated angle deviation is within the interval −εt>pi.εa>−2εt, the accumulated angle deviation If the interval floats from −εt,εt to −2εt+max_εa,max_εa, the simplified error εT′ must satisfy the constraints:(12)εT′<2εt=ε.Among them,min_εa and max_εa respectively represent the minimum and maximum accumulated angle deviation values from the last retained point to the current trajectory point.Proof.
For the simplified trajectory segmentpskpsk+1¯ in Lemma 2, if the cumulative angle deviation of the end point psk+1 is in the interval εt<psk+1.εa<2εt, there must be a small value Ω (see Figure 5), so that the current point psk+1.εa satisfies the following formula:(13)Ω=2εt−psk+1∙εa,and the minimum accumulated angle deviation min_εa in the trajectory section pskpsk+1¯ must satisfy the following formula:(14)min_εa>−εt.
Therefore, pointpsk+1 is not necessarily the first reserved point encountered from point psk, and the interval of the error threshold needs to be floated up: from −εt,εt to min_εa,2εt+min_εa. After that, continue to search for the first reserved point encountered from point psk, and the point pssk+1 whose cumulative angle deviation is greater than 2εt+min_εt for the first time is reserved; in the same way, when −εt>psk+1.εa>−2εt, the interval needs to be floated down to −2εt+max_εa,max_εa.
The direction of the trajectory segmentpipi+1¯ existing between the first and last points of the simplified trajectory pskpssk+1¯ that floats through the interval satisfies the formula:(15)ψ=θpskpssk+1¯+∑m=sk+1ipm.εd.
For the floating interval, the random trajectory segmentpipi+1¯ satisfies the angle constraint in its trajectory segment pskpsk+1¯:(16)θpskpssk+1¯−min_εa,θpskpssk+1¯+2εt+min_εa.
That is, the directions of the small trajectory sectionspipi+1¯ between the simplified trajectory sections pskpsk+1¯ are all within the direction error interval of the floating interval min_εa,2εt+min_εa of the first small trajectory section pskpsk+1 of the simplified trajectory section pskpsk+1¯.
After floating, the simplified trajectory segmentpskpssk+1¯ of the new end point will be obtained, and the rhombus is reconstructed according to pskpssk+1⟶ (see Figure 6). The vector B in the rhombus can be expressed as follows:(17)pskpssk+1⟶=psska⟶+apssk+1⟶.
According to the abovementioned formula, the vector sum of the geometric vectors composed of all the two adjacent trajectory points betweenpskpssk+1¯ can be finally expressed as pskpssk+1⟶, and the satisfied constraints must be derived:(18)θpskpssk+1¯−min_εa<θpskpssk+1¯<θpskpssk+1¯+2εt+min_εa.
In the same way, the descending provable interval must satisfy the constraint:(19)θpskpssk+1¯+max_εa>θpskpssk+1¯>θpskpssk+1¯−2εt+max_εa.
According to the above proofs, the error between a random small track segment deleted in the middle of the simplified track segment and the original track can be guaranteed to bemin_εa,2εt+min_εa or −2εt+max_εa,max_εa.
Therefore, when running the trajectory simplification algorithm, when the cumulative angle deviation of the current point is greater than the given thresholdε, refinding the first reserved point after an interval float must ensure the directional error between the simplified trajectory and the original trajectory in 2εt.Figure 5
The direction range diagram after the interval is floated, the pointpssk+1 marked in the figure is the point.Figure 6
Rhombuses constructed from trajectory segments.


### 3.2. Description of Interval Floating Algorithm

According to related lemmas and theorems, this paper proposes an interval floating-based trajectory simplification algorithm for moving objects. As long as the simplified threshold is set, for each trajectory point collected, the search started from the most recently retained point each time, if there is a trajectory. If the point satisfiespi.εa>2εt, the point will be reserved, which can avoid the situation that the angle deviation of the reserved point is extremely small when its accumulated angle deviation reaches the threshold. For example, we set the direction error to 0.6, and the simplified threshold value when the algorithm is running 0.3, point p3 will be retained instead of point p2, but the contribution of point p2 is much greater than that of p3, so we cannot use pi.εa>εt as the judgment condition (see Figure 7). However, algorithm Angular uses pi.εa>εt as the judgment condition; if it does not exist, it will continue to find the point where the accumulated angle deviation is greater than the simplified threshold from the current point, perform an interval float from the current point, and continue to find the first point after the floating operation. If the point pssk+1 accumulated angle deviation exceeds the floating interval, this point pssk+1 must be retained. At this time, the direction interval is updated to the initial threshold interval again, that is, for each simplified trajectory, they pass the floating interval no more than once. If more than once, the bounded error between the simplified trajectory and the original trajectory cannot be guaranteed (see Algorithm 1).Figure 7
Cumulative angle deviation.Algorithm 1: Simplified Algorithm of Moving Object Trajectory Based on Interval Floating (STIF).
Input: The starting pointPs, ε, εt=ε/2, Angle deviation of current point pi.εd, Cumulative angular deviation of current point pi.εa, Upper interval positive_εt=εt, Lower interval negative_εt=−εt, Current maximum and minimum angle deviation max_εa=0, min_εa=0, Float limit flagOutput: Simplified trajectoryT′for (inti = 1; i < P.size() − 1; i++){pi.εa=pi.εa+pi.εdif (max_εa < pi.εd)max_εa = pi.εd;if (min_εa > pi.εd)min_εa = pi.εd//If the angle deviation of the current point is greater than2∗εtif (Math.abs(pi.εd) > 2∗εt){add (P.get(ii));pi.εa = 0;flag = 0;positive_εt=εt;//“Zero adjustment” in the upper section”negative_εt=−εt; //“Zero adjustment” in the lower intervalmax_εa = 0;min_εa = 0;}if (Math.abs(pi.εa)> εt){//The upper interval meets the floating conditionif (pi.εa > positive_εt && pi.εa < 2∗positive_εt && flag == 0){//Float in the lower intervalnegative_εt = min_εa;//Float up the upper intervalpositive_εt = 2∗εt + min_εa;//Calculate the subsequent points after the interval has floated once. When //the simplified condition is reached again, “zero”flag = 1;} else if(pi.εa < negative_εt && pi.εa > 2∗negative_εt && flag = = 0){//The lower interval meets the floating condition//Float in the upper intervalpositive_εt = max_εa;//Float down in the lower intervalnegative_εt = −2∗εt + max_εa;flag = 1;}else if(flag = = 1){//Already floated once, cannot float againadd (P.get(ii));pi.εa = 0;flag = 0;positive_εt = εt; //“Zero adjustment” in the upper sectionnegative_εt = -εt;//“Zero adjustment” in the lower intervalmax_εa = 0;min_εa = 0;} else if(Math.abs (pi.εa) >2∗εt) { add(P.get(ii));pi.εa = 0;flag = 0;positive_εt = εt;//“Zero adjustment” in the upper sectionnegative_εt = −εt; //“Zero adjustment” in the lower intervalmax_εa = 0;min_εa = 0;}if (pi.εa < negative_εt || pi.εa > positive_εt){add (P.get(ii));pi.εa = 0;flag = 0;positive_εt = εt; //“Zero adjustment” in the upper sectionnegative_εt = −εt; //“Zero adjustment” in the lower intervalmax_εa = 0;min_εa = 0;}} //if (Math.abs(deviation) >error_t)}add (P.get(P.size()-1)); //The last point is added}


## 3.1. Theorem: Bounded Error of Interval Float

This paper proposes the theorem: Bounded Error of Interval Float.If the current trajectory pointpi.εa is in the interval εt<pi.εa<2εt, the algorithm performs a floating operation, that is, the accumulated angle deviation interval that needs to be discarded to simplify the trajectory floats from −εt,εt to min_εa,2εt+min_εa; if the current trajectory point satisfies the accumulated angle deviation is within the interval −εt>pi.εa>−2εt, the accumulated angle deviation If the interval floats from −εt,εt to −2εt+max_εa,max_εa, the simplified error εT′ must satisfy the constraints:(12)εT′<2εt=ε.Among them,min_εa and max_εa respectively represent the minimum and maximum accumulated angle deviation values from the last retained point to the current trajectory point.Proof.
For the simplified trajectory segmentpskpsk+1¯ in Lemma 2, if the cumulative angle deviation of the end point psk+1 is in the interval εt<psk+1.εa<2εt, there must be a small value Ω (see Figure 5), so that the current point psk+1.εa satisfies the following formula:(13)Ω=2εt−psk+1∙εa,and the minimum accumulated angle deviation min_εa in the trajectory section pskpsk+1¯ must satisfy the following formula:(14)min_εa>−εt.
Therefore, pointpsk+1 is not necessarily the first reserved point encountered from point psk, and the interval of the error threshold needs to be floated up: from −εt,εt to min_εa,2εt+min_εa. After that, continue to search for the first reserved point encountered from point psk, and the point pssk+1 whose cumulative angle deviation is greater than 2εt+min_εt for the first time is reserved; in the same way, when −εt>psk+1.εa>−2εt, the interval needs to be floated down to −2εt+max_εa,max_εa.
The direction of the trajectory segmentpipi+1¯ existing between the first and last points of the simplified trajectory pskpssk+1¯ that floats through the interval satisfies the formula:(15)ψ=θpskpssk+1¯+∑m=sk+1ipm.εd.
For the floating interval, the random trajectory segmentpipi+1¯ satisfies the angle constraint in its trajectory segment pskpsk+1¯:(16)θpskpssk+1¯−min_εa,θpskpssk+1¯+2εt+min_εa.
That is, the directions of the small trajectory sectionspipi+1¯ between the simplified trajectory sections pskpsk+1¯ are all within the direction error interval of the floating interval min_εa,2εt+min_εa of the first small trajectory section pskpsk+1 of the simplified trajectory section pskpsk+1¯.
After floating, the simplified trajectory segmentpskpssk+1¯ of the new end point will be obtained, and the rhombus is reconstructed according to pskpssk+1⟶ (see Figure 6). The vector B in the rhombus can be expressed as follows:(17)pskpssk+1⟶=psska⟶+apssk+1⟶.
According to the abovementioned formula, the vector sum of the geometric vectors composed of all the two adjacent trajectory points betweenpskpssk+1¯ can be finally expressed as pskpssk+1⟶, and the satisfied constraints must be derived:(18)θpskpssk+1¯−min_εa<θpskpssk+1¯<θpskpssk+1¯+2εt+min_εa.
In the same way, the descending provable interval must satisfy the constraint:(19)θpskpssk+1¯+max_εa>θpskpssk+1¯>θpskpssk+1¯−2εt+max_εa.
According to the above proofs, the error between a random small track segment deleted in the middle of the simplified track segment and the original track can be guaranteed to bemin_εa,2εt+min_εa or −2εt+max_εa,max_εa.
Therefore, when running the trajectory simplification algorithm, when the cumulative angle deviation of the current point is greater than the given thresholdε, refinding the first reserved point after an interval float must ensure the directional error between the simplified trajectory and the original trajectory in 2εt.Figure 5
The direction range diagram after the interval is floated, the pointpssk+1 marked in the figure is the point.Figure 6
Rhombuses constructed from trajectory segments.


## 3.2. Description of Interval Floating Algorithm

According to related lemmas and theorems, this paper proposes an interval floating-based trajectory simplification algorithm for moving objects. As long as the simplified threshold is set, for each trajectory point collected, the search started from the most recently retained point each time, if there is a trajectory. If the point satisfiespi.εa>2εt, the point will be reserved, which can avoid the situation that the angle deviation of the reserved point is extremely small when its accumulated angle deviation reaches the threshold. For example, we set the direction error to 0.6, and the simplified threshold value when the algorithm is running 0.3, point p3 will be retained instead of point p2, but the contribution of point p2 is much greater than that of p3, so we cannot use pi.εa>εt as the judgment condition (see Figure 7). However, algorithm Angular uses pi.εa>εt as the judgment condition; if it does not exist, it will continue to find the point where the accumulated angle deviation is greater than the simplified threshold from the current point, perform an interval float from the current point, and continue to find the first point after the floating operation. If the point pssk+1 accumulated angle deviation exceeds the floating interval, this point pssk+1 must be retained. At this time, the direction interval is updated to the initial threshold interval again, that is, for each simplified trajectory, they pass the floating interval no more than once. If more than once, the bounded error between the simplified trajectory and the original trajectory cannot be guaranteed (see Algorithm 1).Figure 7
Cumulative angle deviation.Algorithm 1: Simplified Algorithm of Moving Object Trajectory Based on Interval Floating (STIF).
Input: The starting pointPs, ε, εt=ε/2, Angle deviation of current point pi.εd, Cumulative angular deviation of current point pi.εa, Upper interval positive_εt=εt, Lower interval negative_εt=−εt, Current maximum and minimum angle deviation max_εa=0, min_εa=0, Float limit flagOutput: Simplified trajectoryT′for (inti = 1; i < P.size() − 1; i++){pi.εa=pi.εa+pi.εdif (max_εa < pi.εd)max_εa = pi.εd;if (min_εa > pi.εd)min_εa = pi.εd//If the angle deviation of the current point is greater than2∗εtif (Math.abs(pi.εd) > 2∗εt){add (P.get(ii));pi.εa = 0;flag = 0;positive_εt=εt;//“Zero adjustment” in the upper section”negative_εt=−εt; //“Zero adjustment” in the lower intervalmax_εa = 0;min_εa = 0;}if (Math.abs(pi.εa)> εt){//The upper interval meets the floating conditionif (pi.εa > positive_εt && pi.εa < 2∗positive_εt && flag == 0){//Float in the lower intervalnegative_εt = min_εa;//Float up the upper intervalpositive_εt = 2∗εt + min_εa;//Calculate the subsequent points after the interval has floated once. When //the simplified condition is reached again, “zero”flag = 1;} else if(pi.εa < negative_εt && pi.εa > 2∗negative_εt && flag = = 0){//The lower interval meets the floating condition//Float in the upper intervalpositive_εt = max_εa;//Float down in the lower intervalnegative_εt = −2∗εt + max_εa;flag = 1;}else if(flag = = 1){//Already floated once, cannot float againadd (P.get(ii));pi.εa = 0;flag = 0;positive_εt = εt; //“Zero adjustment” in the upper sectionnegative_εt = -εt;//“Zero adjustment” in the lower intervalmax_εa = 0;min_εa = 0;} else if(Math.abs (pi.εa) >2∗εt) { add(P.get(ii));pi.εa = 0;flag = 0;positive_εt = εt;//“Zero adjustment” in the upper sectionnegative_εt = −εt; //“Zero adjustment” in the lower intervalmax_εa = 0;min_εa = 0;}if (pi.εa < negative_εt || pi.εa > positive_εt){add (P.get(ii));pi.εa = 0;flag = 0;positive_εt = εt; //“Zero adjustment” in the upper sectionnegative_εt = −εt; //“Zero adjustment” in the lower intervalmax_εa = 0;min_εa = 0;}} //if (Math.abs(deviation) >error_t)}add (P.get(P.size()-1)); //The last point is added}


## 4. Experiment and Discussion

In order to verify the trajectory simplification algorithmSTIF based on interval floats, this paper uses the Geolife dataset in [16–18]. The GPS trajectory dataset was collected in (Microsoft Research Asia) Geolife project by 182 users in a period of over five years (from April 2007 to August 2012). A GPS trajectory of this dataset is represented by a sequence of time-stamped points, each of which contains the information of latitude, longitude, and altitude. Each file in the data selected for this experiment is larger than 30 KB. The experiment in this paper uses data sets of different sizes and different angle thresholds for experiments and analyzes the time performance and simplification rate performance of the algorithm through the experimental results.The simplification rate of the algorithm is defined as follows:(20)rate=T′T×100%.Among them,T′ represents the simplified trajectory, and T represents the original trajectory. What we hope is that the algorithm can guarantee a low simplification rate within a certain error.


### 4.1. Performance Evaluation Based on Simplified Time

According to the experimental results (see Figure8), when the data size is constant and the threshold is set very small, the simplification time of STIF algorithm is slightly larger than that of Angular. As the threshold increases, the simplification time of STIF algorithm tends to decrease and gradually approach Angular. From the perspective of the two algorithms, whether it is STIF or Angular, as the simplification threshold increases, the simplification time of the algorithm tends to decrease.Figure 8
The performance of the time performance of theAngular algorithm and the STIF algorithm under 5000 trajectories as the direction error increases.The size of the data set ranges from 1000 to 5000. According to the experimental results, for the two algorithms, the average simplification time (see Figures9 and 10) of the simplification thresholds of different sizes decreases with the increase of the data set.Figure 9
The performance of theAngular algorithm in different directions error with the increase of the trajectory data set.Figure 10
The performance of theSTIF algorithm in different directions error with the increase of the trajectory data set.


### 4.2. Performance Evaluation Based on Simplification Rate

According to the experimental results (see Figure11), it can be concluded that under 5000 trajectories, the average simplification rate of the two algorithms tends to decrease with the increase of the simplification threshold, and the simplification rate of STIF algorithm is lower than Angular.Figure 11
The performance of simplification rate performance of theAngular algorithm and the STIF algorithm under 5000 trajectories as the direction error increases.By observing the experimental results (see Figures12 and 13), we can conclude that no matter what the simplification threshold is, the relationship between the simplification rate of the two algorithms and the data scale is that the larger the data scale is, the lower is the simplification rate.Figure 12
The performance of theAngular algorithm in different directions error with the increase of the trajectory data set.Figure 13
The performance of theSTIF algorithm in different directions error with the increase of the trajectory data set.It can be concluded from the experimental results (see Figures14 and 15) that for the two algorithms, the simplification rate decreases with the increase of the simplification threshold among the five data sets of different sizes. Also, compared to algorithm Angular, the highest simplification rate of algorithm STIF is only a data size of 1000. When the simplification threshold is set to 1/12π, it is slightly higher than 0.35, but for algorithm Angular, when the simplification threshold is 1/12π, the highest simplification rate is greater than 0.45, and the lowest simplification rate is also greater than 0.35. Speaking of massive trajectory data, the number of acquisition points for each trajectory is more than tens of thousands of points. In this case, the Angular algorithm retains too many trajectories data are not conducive to efficient data storage. On the contrary, the STIF algorithm can ensure the accurate retention of points while reducing the simplification rate.Figure 14
The change of the simplification rate of different data scales with the increase of the simplification threshold of theAngular algorithm.Figure 15
The change of the simplification rate of different data scales with the increase of the simplification threshold of theSTIF algorithm.


## 4.1. Performance Evaluation Based on Simplified Time

According to the experimental results (see Figure8), when the data size is constant and the threshold is set very small, the simplification time of STIF algorithm is slightly larger than that of Angular. As the threshold increases, the simplification time of STIF algorithm tends to decrease and gradually approach Angular. From the perspective of the two algorithms, whether it is STIF or Angular, as the simplification threshold increases, the simplification time of the algorithm tends to decrease.Figure 8
The performance of the time performance of theAngular algorithm and the STIF algorithm under 5000 trajectories as the direction error increases.The size of the data set ranges from 1000 to 5000. According to the experimental results, for the two algorithms, the average simplification time (see Figures9 and 10) of the simplification thresholds of different sizes decreases with the increase of the data set.Figure 9
The performance of theAngular algorithm in different directions error with the increase of the trajectory data set.Figure 10
The performance of theSTIF algorithm in different directions error with the increase of the trajectory data set.


## 4.2. Performance Evaluation Based on Simplification Rate

According to the experimental results (see Figure11), it can be concluded that under 5000 trajectories, the average simplification rate of the two algorithms tends to decrease with the increase of the simplification threshold, and the simplification rate of STIF algorithm is lower than Angular.Figure 11
The performance of simplification rate performance of theAngular algorithm and the STIF algorithm under 5000 trajectories as the direction error increases.By observing the experimental results (see Figures12 and 13), we can conclude that no matter what the simplification threshold is, the relationship between the simplification rate of the two algorithms and the data scale is that the larger the data scale is, the lower is the simplification rate.Figure 12
The performance of theAngular algorithm in different directions error with the increase of the trajectory data set.Figure 13
The performance of theSTIF algorithm in different directions error with the increase of the trajectory data set.It can be concluded from the experimental results (see Figures14 and 15) that for the two algorithms, the simplification rate decreases with the increase of the simplification threshold among the five data sets of different sizes. Also, compared to algorithm Angular, the highest simplification rate of algorithm STIF is only a data size of 1000. When the simplification threshold is set to 1/12π, it is slightly higher than 0.35, but for algorithm Angular, when the simplification threshold is 1/12π, the highest simplification rate is greater than 0.45, and the lowest simplification rate is also greater than 0.35. Speaking of massive trajectory data, the number of acquisition points for each trajectory is more than tens of thousands of points. In this case, the Angular algorithm retains too many trajectories data are not conducive to efficient data storage. On the contrary, the STIF algorithm can ensure the accurate retention of points while reducing the simplification rate.Figure 14
The change of the simplification rate of different data scales with the increase of the simplification threshold of theAngular algorithm.Figure 15
The change of the simplification rate of different data scales with the increase of the simplification threshold of theSTIF algorithm.


## 5. Conclusions

This article mainly introduces a new trajectory simplification algorithm based on interval floating. Various experiments were conducted from different data set sizes and different angle thresholds to evaluate the time performance and simplification rate performance of the algorithm. Through experimental comparison, algorithmSTIF has outperformed algorithm Angular in simplification rate; in addition, as the data set increases, the average simplification time of algorithm STIF is slightly longer than that of algorithm Angular when the simplification threshold is smaller. With the increase of the threshold, the simplification time of the STIF algorithm is significantly reduced. Therefore, in the face of large-scale trajectory data, the STIF algorithm can show a better simplification rate and simplification time. For future works, it is planned to assess the algorithms with other datasets, considering other transportation modes and trajectories’ characteristics as well as different application scenarios.



---

*Source: 5032375-2022-11-08.xml*