COMP20005 - Assignment 1 : GPS Data Trajectory

The University of Melbourne

School of Computing and Information Systems

COMP20005 Engineering Computation

Assignment 1 

 

 1 Learning Outcomes

In this assignment you will demonstrate your understanding of loops and if statements by writing a program that sequentially processes a file of input data. You are also expected to make use of functions and arrays.

 2 The Story...

The prevalence of smart phones and Internet of Things has accumulated huge volumes of human trajecto

ries, that is, sequences of GPS points recording the locations of people or other objects. For example, Uber

has recorded 7.6 billion trips in 2022.

In this assignment, we are given a set of trajectory data that records people’s locations at different times.

The aim is to identify if any of the trajectories is sufficiently similar to a given query trajectory. Such com

putations are the basic building block of many location-based applications, such as to find shareable Uber

trips (see Figure 1), to make travel recommendations, and, during pandemic, to support contact tracing.

You do not need to be an expert in trajectory data analysis to complete this assignment. This assignment

specification will walk you through the tasks step by step

Below is a sample list of trajectory records (the time when the trajectories are recorded is omitted for

simplicity).

1. Each data trajectory starts with a line containing a ‘#’ character followed by a unique six-digit integer representing the ID of the trajectory.

2. Then, the GPS points captured on the trajectory are stored in the order that they are captured, and

they are separated into at least one and up to five lines1 each containing four points, that is, each

trajectory contains up to 20 points. There are no lines with fewer than four GPS points (except for

the trajectory ID lines). Each GPS point, as separated by a ‘;’, is represented by a pair of latitude and longitude, each of which is a real number with 6 digits after the decimal point.

3. A line of 10 ‘@’s follows the data trajectory lines to separate them from a query trajectory.

4. Finally, the query trajectory is represented by up to five lines, each with four GPS points like above.

For simplicity, there is no ID for the query trajectory. 

#257837

41.141412 -8.618643; 41.141376 -8.618499; 41.142511 -8.620326; 41.143815 -8.622153;

41.144373 -8.623953; 41.144778 -8.626686; 41.144697 -8.627373; 41.145210 -8.630226;

#761770

41.151951 -8.574678; 41.151942 -8.574705; 41.151933 -8.574696; 41.151967 -8.574663;

41.151933 -8.574723; 41.151924 -8.574714; 41.150934 -8.575164; 41.151924 -8.574714;

41.150232 -8.577135; 41.148639 -8.578538; 41.147316 -8.579745; 41.146173 -8.579358;

41.145033 -8.580744; 41.145127 -8.582904; 41.146479 -8.584388; 41.145876 -8.610849;

#576807

41.180499 -8.645994; 41.180517 -8.645949; 41.180049 -8.646048; 41.178888 -8.646804;

41.178465 -8.649495; 41.177961 -8.652152; 41.177196 -8.654049; 41.177925 -8.655012;

41.177853 -8.656353; 41.177277 -8.659647; 41.177619 -8.662518; 41.179221 -8.664561;

41.178537 -8.667432; 41.176674 -8.668944; 41.175182 -8.671374; 41.173308 -8.673894;

41.171841 -8.676918; 41.171949 -8.680032; 41.173191 -8.682615; 41.173776 -8.685441;

...

3 Your Task

You are given a skeleton code file named program.c. Your task is to add code to it to read the input data

and to find the trajectory most similar to the query trajectory. The assignment consists of four stages.

3.1 Stage 1 - Process the First Data Trajectory (6 Marks)

Add code to the stage_one function to read the first data trajectory and print out for the trajectory: the

trajectory ID, the number of points on the trajectory, the latitude and the longitude of the first point on the trajectory, and the distance (2 digits after the decimal point) between the first two points on the trajectory.

3.2 Stage 2 - Process the Rest of Data Trajectories (5 Marks)

Now add code to the stage_two function so that the length of each data trajectory (not the query trajectory)

is computed and visualised. You may assume that the distance values are within the range of (0, 4000) (use

%07.2f for the length output formatting). The length of a trajectory is the sum of the distance between

every two adjacent points (in the input order) on the trajectory.

On the same sample input data, the additional output for this stage should be (you need to work out how

the visualisation works based on this example):

Stage 2

==========

#257837, len: 1121.89 |----+-

#761770, len: 3812.16 |----+----+----+----+

#576807, len: 3957.92 |----+----+----+----+

#484662, len: 2875.40 |----+----+----+

#941008, len: 2043.64 |----+----+-

#707773, len: 0281.15 |--

#507479, len: 1180.29 |----+-

#223260, len: 1121.64 |----+-

#334953, len: 0913.29 |----+

Here, the length of trajectory #257837 is 1121.89.

3.3 Stage 3 - Read the Query Trajectory (5 Marks)

Now add code to the stage_three function to read the query trajectory and calculate its dissimilarity

with the first data trajectory. Consider a query trajectory Tq with points {pq,1, pq,2, . . . , pq,nq } and a data

trajectory Td with points {pd,1, pd,1, . . . , pd,nd }, where nq and nd are the number of points on Tq and Td,

respectively. 

3.4 Stage 4 - Find the Most Similar Data Trajectory (4 Marks)

In this stage, we find the data trajectory most similar to the query trajectory. Add code to the stage_four

function to calculate the dissimilarity for the query trajectory with each data trajectory. The function

should output the ID of the data trajectory of the smallest dissimilarity value (that is, the data trajectory

most similar to the query trajectory), and the corresponding dissimilarity value. You may assume that there

will not be ties in the dissimilarity values.

On the same sample input data, the additional output for this stage should be (use %.2f for the dissimilarity

value output formatting; note the final ‘\n’ in the output):

Stage 4

==========

Most similar data trajectory: #507479

Dissimilarity: 78.48