Assignment 4: GPS Track Analysis

Objectives

• to implement a list ADT using dynamic memory allocation
• 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, recording a GPS track for each vessel it monitors. Analysis of those tracks can yield insights into illegal fishing activity. For example, a vessel that has been nearly stationary for a significant period of time in a marine preserve may warrant further investigation for the possibility that it was illegally fishing in the preserve.

Assignment

As a basis for others to work with GPS tracks, implement the track library 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/hw4/Required; you will also need the location library found in that directory).

Then, write a program called Stationary that reads a GPS track and outputs the near-stationary points on that track, starting with the earliest. A near-stationary point is defined as a trackpoint P read from the input that is

• at least as far from the end of the track as the given time bound;
• the start of a part of the track for which all the following points read from input that are strictly less than the time bound away from P are no further than the distance bound away from P; and
• having at least one point X between P and the previous near-stationary point Q that is further away from Q than the given distance bound (X may be P itself).

All distances should be computed with location_distance from the location library.

The time bound and distance bound will be given as command-line arguments in a format suitable for input to strtod (so the values need not be integers). The unit for the time bound is seconds and the value will be positive The unit for the distance bound is kilometers and the value will be non-negative.

The third command-line argument will be the name of the file to read a track from, or not present to indicate that the track should be read from standard input. If a filename is given but the named file cannot be opened for reading, then the message Stationary: error opening FILE must be written to standard error with a trailing newline (replace FILE with the name of the offending file).

Whether the input is read from standard input or from a file, it 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 increasing time. The input will be small enough to fit in memory assuming $O(n)$ space required for a track containing $n$ points and a reasonable constant hidden by the $O$.

The output of Stationary must be written to standard output and must consist of the latitude and longitude of each near-stationary point, written one point per line in order of increasing time, with the coordinates given to six digits after the decimal point (rounded in the same way that printf rounds) and separated by a single space. There must be no other whitespace or other output except for a newline after each near-stationary point. The near-stationary points to output must be determined in the same way as for the track_find_stationary function.

Your Stationary program must run in $O(n^2)$ time, where $n$ is the number of points on the track. Your implementations of the functions in the track library must run in the following time bounds (all bounds exclude the time for calls to malloc and free).

• track_create, track_destroy: $O(1)$
• track_size and track_length: $O(1)$
• track_add_point: $O(1)$ amortized
• track_get_point: $O(\log n)$
• track_for_each: $O(n)$ plus the time for the calls to the function passed to it
• track_find_stationary: $O(n^2)$

Your code will be tested with Valgrind, so make sure there are no memory leaks or other errors reported by Valgrind.

Your program must not crash or go into an infinite loop if any of the specifications for the input (file or command-line) are violated.

Example

[jrg94@perch GPS]$ ./Stationary 15 0.010 east_rock.track
41.308976 -72.935595
41.309050 -72.935525
41.309123 -72.935446
41.311767 -72.931486
41.310894 -72.930687
41.312634 -72.932109
41.324871 -72.901646
41.304399 -72.894219
41.308221 -72.903205
41.308946 -72.909121

(The file east_rock.track and some other sample input tracks are in /c/cs223/hw4; note that Stationary can also be used on GPS tracks produced by fitness trackers if they are converted to the correct format.)

Submissions

Submit your makefile, log file, and your source code necessary to build the executable Stationary using your makefile. Do not submit the provided location library or track.h; your makefile should assume that they have been copied into the current directory.