Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

COMP20005 Engineering Computation

Semester 2, 2024

Assignment 1

Due: 4:00 pm Monday 23rd September 2024

Version 1.0

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.

Figure 1: Application example with human movement trajectories.

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.

Given the coordinates of two points p1  =  ⟨lat1 , long1 ⟩  and p2  =  ⟨lat2 , long2 ⟩, where lati  and longi   (i = 1, 2) represent the latitude and the longitude, the distance (in metres) between p1  and p2 , represented by dist(p1 , p2 ), is calculated based on the haversine formula as follows.

dist(p1.P2) = 6371000 · angle_distance, where

angle distance = 2- atan2(sgrt(chord length), sqrt(1 - chord_length)),

chordJength = sin (to_radian(lat2 — latı)/2)+ (1)

cos(to radian(lat1)) - cos(to radian(lat2)) - sin2(to radian(long2 - longi)/2)

In the equation above, to radian(x) = x · (3.14159/180) is a function that converts a latitude or longitude coordinate x to its radian value.  You need to implement this function and  define  the  constants  properly in your code.  Note that you should not use the constant M_PI provided by the math.h library as it is not supported by the assignment submission system under the assignment compilation settings.

The functions atan2(),  sqrt(),  sin(), and cos() are provided by the math.h library.   If you use this library, make sure to add the “-lm” flag to the “gcc” command at compilation on your own machine.

The output of this stage given the above sample input should be (where “mac:” is the command prompt):

mac:  ./program  < test0 .txt

Stage  1

==========

Trajectory:  #257837

Number  of  points:  8

First  point:  <41 .141412, -8 .618643>

Distance  between  first  two  points:  12 .71

Here, 12.71 is the distance between the first two points on the first trajectory, <-41 .141412, -8 .618643> and <-41 .141376, -8.618499>, as calculated using the haversine formula above.

Hint:  To ensure the result accuracy, use double’s for storing the coordinates and calculating the distance value. Use %05 .2f for the distance output formatting. You may also read all input data before printing out for Stage 1.  You may  (and should)  add more functions  as  appropriate.

As this example illustrates, the best way to get data into your program is to save it in a text file (with a “ .txt” extension, any text editor can do this), and then execute your program from the command line, feeding the data in via input redirection  (using <).

In your program, you will still use the standard input functions such as scanf() to read the data. Input redirection will direct these functions to read the data from the file, instead of asking you o type it in by hand. This will be more convenient than typing out the test  cases manually every time you test your pro-gram. Our auto-testing system will feed input data into your submissions in this way as well. To simplify the marking, your program should not print anything except for the data requested to be output (as shown in the output example).

We will provide a sample test file “test0.txt” on LMS. You may download this file directly and use it to test your code before submission.  This file is created under Mac OS. Under Windows systems, the entire file may be displayed in one line if opened in the Notepad app. You do not need to edit this file to add line breaks. The ‘\n’ characters are already contained in the file. They are just not displayed properly but the scanf() function in C can still recognise them correctly.

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. Their dissimilarity dissim(Tq , Td ) is defined as follows:

Intuitively, for every point pq,i  on Tq , we need to find and calculate the distance to its closest point on Td. The sum of such distances for all points on Tq  is the dissimilarity for Tq  with Td.

Note that the definition of dissimilarity is asymmetric, that is, the dissimilarity for Tq  with Td  may be different from that for Td  with Tq   (dissim(Tq , Td )  dissim(Td ,Tq )).

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

Stage  3

==========

Dissimilarity  with  trajectory  #257837:  1789 .16

Wherever appropriate, code should be shared between stages through the use of functions.  In particular, there should not be long stretches of repeated code appearing in different places in your program.

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):