# Algorithm for point distribution of traversal between 2 points on a line in time

Not sure if this is best SO forum to post at, please suggest/move to more appropriate place otherwise. A synopsis of the problem 1st:

Given a scenario where we have messages with data that define a user moving from one x,y location to another (that would form a line), and where for purposes of analysis/calculation, we only have available to use the starting and ending x,y's (the endpoints) and the associated timestamps of said endpoints. Using these info, we can determine the distance, time difference, and thus velocity or rate of change/movement. We can then make use of that to define the points that are distributed along the line between the 2 endpoints. That's the simple case, although we have multiple lines to traverse.

Then the next step after would be to have to remap some source input that contains a sequence of the endpoints (they only change when reaching the next endpoint, thus I call them in sample code below as the source "template" x/y to be replaced by their derived point distribution x/y equivalent that roughly defines where they should be. e.g. the x/y sequence "1,5;1,5;1,5;1,8;1,8;...." would really be something like this "1,5;1,6;1,7;1,8;..." where we started from 1,5 to move to 1,8 along a line. 1,6 and 1,7 are thus calculated to be moved to at some point traveling from 1,5 to 1,8.

And the code I have for this is below. I'm looking for review of the algorithm for correctness and how to optimize it as I suspect (based on using it to remap x/y's) that it's a bit flawed, and doesn't perfectly distribute points between the endpoints. And I need it to be as accurate as possible.

for i in range(len(endpts)):
if i < len(endpts) - 1:
ts_diff = abs(endpts[i+1]['ts'] - endpts[i]['ts']) # in seconds, assuming not need convert to ms or ns
distance = calc_distance(endpts[i]['x'], endpts[i]['y'], endpts[i+1]['x'], endpts[i+1]['y']) # where distance calculated as square root of (diff in x)^2 + (diff in y)^2
rate = 1 if ts_diff == 0 else float("{0:.2f}".format(distance / float(ts_diff)))

if endpts[i]['x'] == endpts[i+1]['x'] and endpts[i]['y'] != endpts[i+1]['y']:
# vertical movement/change (in y)
direction = 1 if endpts[i]['y'] < endpts[i+1]['y'] else -1
for j in range(ts_diff+1): # +1 in case ts_diff = 0
# assume each point along the line between endpt[i] and endpt[i+1] is spaced by ~ 1 second apart in terms of timestamps
pt_mapping = {'x': endpts[i]['x'], 'y': endpts[i]['y'] + j * rate * direction, 'time_end': endpts[i]['ts'] + (j + 1)}
distribution_pts.append(pt_mapping)
elif endpts[i]['x'] != endpts[i+1]['x'] and endpts[i]['y'] == endpts[i+1]['y']:
# horizontal movement/change (in x)
direction = 1 if endpts[i]['x'] < endpts[i+1]['x'] else -1
for j in range(ts_diff+1):
pt_mapping = {'x': endpts[i]['x'] + j * rate * direction, 'y': endpts[i]['y'], 'time_end': endpts[i]['ts'] + (j + 1)}
distribution_pts.append(pt_mapping)
else:
# diagonal movement/change in both x & y
direction_x = 1 if endpts[i]['x'] < endpts[i+1]['x'] else -1
direction_y = 1 if endpts[i]['y'] < endpts[i+1]['y'] else -1
for j in range(ts_diff+1):
pt_mapping = {'x': endpts[i]['x'] + j * rate * direction_x, 'y': endpts[i]['y'] + j * rate * direction_y, 'time_end': endpts[i]['ts'] + (j + 1)}
distribution_pts.append(pt_mapping)

for src_msg in src_msgs:
target_xy = get_target_xy(get_epoch_sec_timestamp(src_msg['ts'])) # where ts is ISO8601 ts string to convert to sec since epoch
src_msg['x'] = target_xy['x'] # replacing source template x with derived x
src_msg['y'] = target_xy['y'] # replacing source template y with derived y

# where we get target x/y by finding 1st distribution pt where
# ts >= the src ts of the pt we're looking at, as a way to check
# how far we've moved along from one endpt to reach another, since
# we have no other "tracking" methods to know that
def get_target_xy(ts):
for entry in distribution_pts:
if entry['time_end'] < ts:
continue
return entry
print "Crap, no target xy matched for input time %s" % ts