Assignment 3: GPS Track Analysis

Objectives

• to implement a list ADT
• to use opaque structs

Introduction

Many species of fish have been overfished, threatening their ecosystems and causing economic hardship to the communities that rely on them. International agreements to limit fishing have allowed some fisheries to recover, but illegal fishing remains a problem. Global Fishing Watch monitors the global commercial fishing fleet in near real-time, receiving signals from beacons on the vessels it monitors and recording a GPS track. As the vessels move around the globe, different receivers may record different parts of the track for a particular vessel. For complete analysis, the different track segments received by different receivers must be combined into a single complete track. Once the track has been combined, we can perform further analysis, for example comparing two tracks from different vessels to determine their closest approach to each other – two vessels that have a very close approach may warrant further investigation for transferring illegal catch from one vessel to another.

Assignment

As a basis for others to work with GPS tracks, implement the track module by creating the implementation file track.c. Your implementation must define the functions and structures declared in the track.h header file found in /c/cs223/hw3/Required/. For parameters and return values for the functions, times are in seconds since a fixed epoch, latitudes and longitudes are in degrees, and distances are in kilometers. The other pre- and post-conditions for the functions in the track module are documented in the header file. You will also need the more_math, location, and trackpoint modules defined by the corresponding .c and .h files in that same directory.

The location module defines operations on geographic locations specified by latitudes and longitudes. The trackpoint module defines operations on GPS trackpoints, which are locations with timestamps, corresponding to the locations where a tracked object was observed and the time at which is was observed there. The trackpoint module also defines operations on GPS track segments, which are two consecutive trackpoints recorded for the same tracked object. The track module that you must complete defines operations on complete GPS tracks, which are arbitrarily long sequences of trackpoints for the same tracked object, in increasing order by timestamp.

After completing the track module, write a program called GPS that performs one of two operations on GPS tracks depending on the command-line arguments. There will be three command-line arguments. The first will be -combine or -closest to indicate whether to combine multiple GPS tracks into one or to determine the closest approach of two tracks. The remaining two command-line arguments will be the names of files containing the tracks to work with. Both filenames will be valid (the files will be present and openable for reading) and distinct.

Each file will contain one trackpoint per line, with each trackpoint given as latitude and longitude (as decimal degrees), and a time (in seconds since a chosen epoch), in that order and with each field in a form suitable for input to strtod and separated by a single space. There will a newline at the end of each trackpoint and no other whitespace on any line. The input will be ordered by strictly increasing time.

For the -combine option, the tracks contained in the two files should be combined into a single track. That single track should contain all the trackpoints from the individual tracks, ordered by increasing time. If some trackpoints are duplicated across the two tracks, then the result should contain only one copy. If there are trackpoints with the same timestamp but different locations, the resulting combined track should contain neither of those trackpoints. The program should write the combined GPS track to standard output in same format as the input files, with all values written with six digits after the decimal point and with the last digit rounded.

For the -closest argument, the program should write to standard output the closest approach of the two tracks, rounded to the nearest kilometer (or inf if there is no overlap in time bewteen the two tracks). "Closest approach" is defined as the minimum distance over all recorded timestamps that are between (inclusive) the start and end times of both tracks, where the location along one track is determined by linear interpolation separately on the latitudes and longitudes of the next earliest and latest trackpoints if that track does not contain a trackpoint with a timestamp that is present in the other. The distance between two points should be calculated with location_distance from the location module.

Your implementations of the functions in the track library must run in the following worst-case time bounds (all bounds exclude the time for calls to malloc and free).

• track_create: $O(1)$
• track_size and track_length: $O(1)$
• track_add_point: $O(1)$
• track_destroy and track_get: $O(n)$
• track_for_each: $O(n)$ plus the time for the calls to the function passed to it
• track_merge: $O(k)$, where $k$ is the number of "overlapping"¹ points in the two tracks to merge (if $t_1$ is the track that starts earlier and $t_2$ is the other track, then $k$ is the number of trackpoints in $t_1$ at or after the start of $t_2$ plus the number of trackpoints in $t_2$ at or before the end of $t_1$; if the starting times are the same then $k$ is the total number of points on the two tracks at or before the earlier ending point)
• track_closest_approach: $O(n + m)$, where $n$ and $m$ are the number of points on the two tracks

¹"Overlapping" is not really the right term if one track start and end time are contained within the other's – in this case $k$ is the number of points in the contained track (all are at or before the end of the containing track) plus the number of points in the containing track at or after the start of the contained track, which includes the points after the end of the contained track.

No specific error messages are required if the files specified on the command line are not readable, or are not in the correct format. Your program must not crash or hang if any of the specifications for the user input (file or command-line) are violated. The functions in your track module will not be tested with actual parameters that violate their preconditions.

Testing

In addition to tests that verify that your GPS program works correctly, there is a set of unit tests in track_unit.c in /c/cs223/hw3/Required that test the individual functions in the track module. In addition to building the GPS executable, your makefile must have a rule for building an executable called TrackUnit from the provided modules, track_unit.c, track.h, and your track.c. Your makefile should assume that the provided files from /c/cs223/hw3/Required have been copied into the current directory; they will not necessarily be in their original locations.

Your code will be tested with valgrind, so make sure there are no memory leaks or other errors reported by valgrind, including for invalid user input.

Although it is good practice to error-check malloc calls, we will not test out-of-memory conditions – there will be sufficient memory to process all inputs on the Zoo as long as your implementation of the track module consumes $O(n)$ memory for a trackpoint of $n$ points (with a reasonable constant hidden by the $O$).

You may assume that the epoch is within human history and that all timestamps are in the range of time from the beginning of modern human history to a time no further in the future than the beginning of modern human history is in the past.

Example

For -combine, consider the track below, where two receivers each recorded part of the track. The red dots indicate trackpoints recorded by one receiver and recorded in one file, and the bold outlines indicate trackpoints recorded by another receiver and recorded in another file.

The merged track from the two receivers would contain one copy of each trackpoint. For the purposes of runtime, $k = 7$ in this example: 3 points from the red track (52, 58, 75), and 4 from the bold track (52, 66, 71, 75).

$ cat merge_example_red.in
-23.590 76.148 10.0
-23.349 76.236 25.0
-23.306 76.436 37.0
-23.349 76.623 42.0
-23.480 76.716 48.0
-23.524 76.864 52.0
-23.460 77.003 58.0
-23.194 77.266 75.0
$ cat merge_example_bold.in
-23.524 76.864 52.0
-23.359 77.030 66.0
-23.241 77.134 71.0
-23.100 77.353 80.0
-23.142 77.502 90.0
-23.292 77.523 98.0
-23.397 77.483 106.0
-23.488 77.620 112.0
-23.617 77.595 120.0
$ ./GPS -combine merge_example_red.in merge_example_bold.in
-23.590000 76.148000 10.000000
-23.349000 76.236000 25.000000
-23.306000 76.436000 37.000000
-23.349000 76.623000 42.000000
-23.480000 76.716000 48.000000
-23.524000 76.864000 52.000000
-23.460000 77.003000 58.000000
-23.359000 77.030000 66.000000
-23.241000 77.134000 71.000000
-23.194000 77.266000 75.000000
-23.100000 77.353000 80.000000
-23.142000 77.502000 90.000000
-23.292000 77.523000 98.000000
-23.397000 77.483000 106.000000
-23.488000 77.620000 112.000000
-23.617000 77.595000 120.000000

For -closest consider the two tracks in the example below, where the large dots represent recorded trackpoints, and the smaller dots represent positions interpolated at timestamps present in one track but not the other. The dashed lines represent the distances between pairs of points (recorded or interpolated) with matching timestamps. The closest approach is approximated as the distance between the trackpoints with timestamp 24.

$ cat closest_bottom.in
-30.873 160.212 10.0
-30.643 160.277 20.0
-30.509 160.493 24.0
-30.550 160.733 36.0
-30.463 160.943 45.0
-30.625 161.291 55.0
$ cat closest_top.in
-30.164 160.114 10.0
-30.262 160.247 15.0
-30.322 160.446 20.0
-30.334 160.589 24.0
-30.324 160.773 30.0
-30.179 161.074 45.0
-30.078 161.154 50.0
$ ./GPS -closest closest_top.in closest_bottom.in
21

Submissions

Submit your makefile, log file, and your source code necessary to build the executables GPS and TrackUnit using your makefile. Do not submit the provided more_math, location, and trackpoint modules, track.h, or track_unit.c.