Implement different decimation algorithms

[cagryInside]

Currently, we have implemented only Douglas–Peucker algorithm to decimate close location. However, we would like to implement different decimation algorithms (e.g., Critical Point Algorithm).

[barbeau]

In particular, we'd like to support streaming decimation algorithms that can run in real-time (i.e., have O(n) complexity), such as Critical Point Algorithm. Douglas–Peucker is O(n^2) and requires the entire line as input. Supporting real-time execution may require modifications to the interface.

[cagryInside]

In addition, we might want to implement a simple caching mechanism for real-time updates. Currently, we don't have cache, so whenever the app receives a location update it sends the location to the server.

[barbeau]

Agreed - there would likely be a small cache built into the streaming decimation algorithm (for Critical Point Algorithm, it was 3 points), but we could also use a general purpose cache for real-time updates. Technically this is a buffer, not a cache (a cache implies that the data is duplicated - a comment I got back from an IEEE paper reviewer ;) ) - I've opened a new ticket to track general purpose buffering (https://github.com/CUTR-at-USF/device-tracker-library/issues/13).

Based on my past experience, an interface for a streaming decimation algorithm would probably look something like this:

public interface LocationDecimationStreaming extends LocationDecimation {

/**
 * Called for each location update received by the app
 * @param location the next location in a stream of locations to decimate
 * @return the next location in the stream of decimated locations, or null if a next location hasn't yet been generated

    Location decimate(Location location);

/**
 * Flushes any currently cached locations that are output from the decimation algorithm, but haven't yet been delivered to the app via the return from the `decimate()` method.  Normally called when the app receives the last location update from the platform, and wants to send the final points in the line to the server.  Locations must be ordered in the ArrayList according to their timestamp, with the oldest location (i.e., minimum timestamp value) being at index 0.
 */

   ArrayList<Location> flush();
}

Streaming usage would look like:

LocationDecimationStreaming mDecimator;

public void initTracking() {
    mDecimator = new CriticalPointAlgorithm();
}

public void onLocationChanged(Location location) {
    Location pastLocation =  mDecimator.decimate(location);

    // Send pastLocation to server, or buffer the location point here    
}

public void teardownTracking() {
    ArrayList<Location> finalLocations =  mDecimator.flush();

    // Send finalLocations to server, or buffer the locations here
}