Algorithm to "compress" gps tracks by excluding points not relevants for drawing it to a map

gps_track_compression.py

__author__ = 'cazamagni'

import math


def haversine_distance(origin, destination):
    '''
    http://en.wikipedia.org/wiki/Haversine_formula
    Wayne Dyck's implementation
    '''
    lat1, lon1 = origin
    lat2, lon2 = destination
    radius = 6371 # earth radius in km

    dlat = math.radians(lat2-lat1)
    dlon = math.radians(lon2-lon1)
    a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(lat1)) \
        * math.cos(math.radians(lat2)) * math.sin(dlon/2) * math.sin(dlon/2)
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    d = radius * c

    return d


def normalize_point_list(points):
    '''
    enumerate the points array three at a time and
    discard the central one if it's distance from the line
    connecting the first and the third is below the specified threshold.
    '''
    kept_points = []
    deleted_points = []

    #delta = 0.001 # 1 meter delta
    delta = 0.0001 # 10 cm delta

    def _eval_points(point_0, point_1, point_2):

        hd_0_1 = haversine_distance(point_0, point_1)
        hd_1_2 = haversine_distance(point_1, point_2)
        hd_0_2 = haversine_distance(point_0, point_2)

        if (hd_0_1 + hd_1_2) <= (hd_0_2 + delta):
            return True  # point can be removed
        return False  # point has to be kept

    for point in range(0, len(points)-2):
        if _eval_points(points[point], points[point+1], points[point+2]):
            deleted_points.append(point+1)
        else:
            kept_points.append(points[point])
    print 'removed: %s, kept: %s' % (len(deleted_points), len(kept_points))
    return kept_points, deleted_points
    
    
def normalize_point_list_pro(points):
    '''
    enumerate the points array three at a time and
    discard the central one if it's distance from the line
    connecting the first and the third is below the specified threshold.
    
    Here the threshold is dynamic and its precision linearly increases with the number of discarded points.
    '''
    kept_points = []
    deleted_points = []

    # adjustable delta
    delta_start = 0.001          # upper bound for delta value
    delta_step = 0.0003
    #delta_current = delta_start  # equal to delta_start when initialized

    current_index = 0
    last_kept_index = 0

    def _eval_points(point_0, point_1, point_2):

        hd_0_1 = haversine_distance(point_0, point_1)
        hd_1_2 = haversine_distance(point_1, point_2)
        hd_0_2 = haversine_distance(point_0, point_2)

        jump_distance = current_index - last_kept_index
        delta_current = delta_start - (delta_step * jump_distance)

        if (hd_0_1 + hd_1_2) <= (hd_0_2 + delta_current):
            return True  # point can be removed
        return False  # point has to be kept

    for point in range(0, len(points)-2):
        current_index = point
        if _eval_points(points[point], points[point+1], points[point+2]):
            deleted_points.append(point+1)
        else:
            kept_points.append(points[point])
            last_kept_index = point

    print 'removed: %s, kept: %s' % (len(deleted_points), len(kept_points))
    return kept_points, deleted_points
    
    
    

points = []     #points array:[[lat,lon],[lat,lon],...]

if __name__ == '__main__':
    normalize_point_list(points=points):