So we recently merged some work that dealt with rejecting paths from the search space that arent possible given the time stamps on each input gps point. See: valhalla/valhalla#840
route,noise,sample_rate,route_url,trace_attr_url,reporter_url
Quinn Notary Svc_to_Harvest Printing Svc,60.0,20.0,http://valhalla:8002/route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A37.794447%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.404719%7D%2C%7B%22lat%22%3A37.789319%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.401486%7D%5D%2C%22costing%22%3A%22auto%22%2C%22id%22%3A%22my_work_route%22%7D,http://valhalla:8002/trace_attributes?json=%7B%22trace_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A5%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22encoded_polyline%22%3A%22eixagAhv~mhFuJo%7BAm%40gDb%5BwDlZwD%7Cw%40mJd%40%3Fl%40Mj%5BwDzUwCtEm%40dy%40mJly%40%7DJ~b%40cFzPyBvC_%40~C%5DjA%5Dt%40O%60C%3FxBNz%40NcFaHuTuZ%22%2C%22costing%22%3A%22auto%22%7D,http://reporter:8003/report?json=%7B%22match_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A98.69%2C%22mode%22%3A%22auto%22%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22uuid%22%3A%22999999%22%2C%22trace%22%3A%5B%7B%22lat%22%3A37.794749%2C%22lon%22%3A-122.405067%2C%22time%22%3A1500830321%7D%2C%7B%22lat%22%3A37.793797%2C%22lon%22%3A-122.403793%2C%22time%22%3A1500830341%7D%2C%7B%22lat%22%3A37.791173%2C%22lon%22%3A-122.403579%2C%22time%22%3A1500830361%7D%2C%7B%22lat%22%3A37.789243%2C%22lon%22%3A-122.402859%2C%22time%22%3A1500830381%7D%2C%7B%22lat%22%3A37.7898%2C%22lon%22%3A-122.401827%2C%22time%22%3A1500830389%7D%5D%7D
Silver Universal_to_Diane Lavin Accounting,40.0,10.0,http://valhalla:8002/route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A37.772337%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.40449%7D%2C%7B%22lat%22%3A37.775332%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.397206%7D%5D%2C%22costing%22%3A%22auto%22%2C%22id%22%3A%22my_work_route%22%7D,http://valhalla:8002/trace_attributes?json=%7B%22trace_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A5%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22encoded_polyline%22%3A%22iyl%60gAp%7C%7DmhFiMcQsKgOwYy%60%40pb%40kk%40fNaRvSgY~CuEoCeDePoTkBgCoCgDiH%7DJse%40so%40qa%40%7Bj%40sAkBaa%40%7Bi%40qaAmsA_DeE%22%2C%22costing%22%3A%22auto%22%7D,http://reporter:8003/report?json=%7B%22match_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A65.79%2C%22mode%22%3A%22auto%22%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22uuid%22%3A%22999999%22%2C%22trace%22%3A%5B%7B%22lat%22%3A37.772886%2C%22lon%22%3A-122.404412%2C%22time%22%3A1500830370%7D%2C%7B%22lat%22%3A37.773418%2C%22lon%22%3A-122.40361%2C%22time%22%3A1500830380%7D%2C%7B%22lat%22%3A37.773024%2C%22lon%22%3A-122.402899%2C%22time%22%3A1500830390%7D%2C%7B%22lat%22%3A37.772252%2C%22lon%22%3A-122.402221%2C%22time%22%3A1500830400%7D%2C%7B%22lat%22%3A37.772388%2C%22lon%22%3A-122.401573%2C%22time%22%3A1500830410%7D%2C%7B%22lat%22%3A37.773059%2C%22lon%22%3A-122.400638%2C%22time%22%3A1500830420%7D%2C%7B%22lat%22%3A37.773943%2C%22lon%22%3A-122.399776%2C%22time%22%3A1500830430%7D%2C%7B%22lat%22%3A37.774653%2C%22lon%22%3A-122.398884%2C%22time%22%3A1500830440%7D%2C%7B%22lat%22%3A37.775333%2C%22lon%22%3A-122.398067%2C%22time%22%3A1500830450%7D%2C%7B%22lat%22%3A37.775454%2C%22lon%22%3A-122.397734%2C%22time%22%3A1500830457%7D%5D%7D
Allstate Insurance_to_Byron Meyer & Co,80.0,10.0,http://valhalla:8002/route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A37.792878%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.401021%7D%2C%7B%22lat%22%3A37.797396%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.402887%7D%5D%2C%22costing%22%3A%22auto%22%2C%22id%22%3A%22my_work_route%22%7D,http://valhalla:8002/trace_attributes?json=%7B%22trace_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A5%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22encoded_polyline%22%3A%22aeuagAftwmhFgJjAk%40Ng%40%3Fy%5BvD%7BZtDmZvD%7DYtDmZfDeThC_Dl%40gD%5C%5Cwr%40~HaNzAcKjAoNzAeKjAtElt%40%22%2C%22costing%22%3A%22auto%22%7D,http://reporter:8003/report?json=%7B%22match_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A100.0%2C%22mode%22%3A%22auto%22%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22uuid%22%3A%22999999%22%2C%22trace%22%3A%5B%7B%22lat%22%3A37.792689%2C%22lon%22%3A-122.401189%2C%22time%22%3A1500830398%7D%2C%7B%22lat%22%3A37.793536%2C%22lon%22%3A-122.401671%2C%22time%22%3A1500830408%7D%2C%7B%22lat%22%3A37.794196%2C%22lon%22%3A-122.402074%2C%22time%22%3A1500830418%7D%2C%7B%22lat%22%3A37.79495%2C%22lon%22%3A-122.402544%2C%22time%22%3A1500830428%7D%2C%7B%22lat%22%3A37.795923%2C%22lon%22%3A-122.402532%2C%22time%22%3A1500830438%7D%2C%7B%22lat%22%3A37.796998%2C%22lon%22%3A-122.402832%2C%22time%22%3A1500830448%7D%2C%7B%22lat%22%3A37.797185%2C%22lon%22%3A-122.403353%2C%22time%22%3A1500830458%7D%2C%7B%22lat%22%3A37.797128%2C%22lon%22%3A-122.403577%2C%22time%22%3A1500830460%7D%5D%7D
Record Pressing Com_to_Manulife Financial,80.0,10.0,http://valhalla:8002/route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A37.789436%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.391897%7D%2C%7B%22lat%22%3A37.793358%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.398782%7D%5D%2C%22costing%22%3A%22auto%22%2C%22id%22%3A%22my_work_route%22%7D,http://valhalla:8002/trace_attributes?json=%7B%22trace_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A5%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22encoded_polyline%22%3A%22gnnagAtuemhFso%40~%7B%40aCfDoTvYmTbZmOpSkf%40%60p%40%7BTtZe%60%40nh%40yV%60%5C%5CW%5C%5C%7Ci%40zt%40%5D%7C%40kAvC%7BArFzFn%7C%40ut%40nIoC%5Em%40L%22%2C%22costing%22%3A%22auto%22%7D,http://reporter:8003/report?json=%7B%22match_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A100.0%2C%22mode%22%3A%22auto%22%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22uuid%22%3A%22999999%22%2C%22trace%22%3A%5B%7B%22lat%22%3A37.790046%2C%22lon%22%3A-122.391581%2C%22time%22%3A1500830537%7D%2C%7B%22lat%22%3A37.790621%2C%22lon%22%3A-122.39223%2C%22time%22%3A1500830547%7D%2C%7B%22lat%22%3A37.791624%2C%22lon%22%3A-122.393083%2C%22time%22%3A1500830557%7D%2C%7B%22lat%22%3A37.792766%2C%22lon%22%3A-122.39404%2C%22time%22%3A1500830567%7D%2C%7B%22lat%22%3A37.793513%2C%22lon%22%3A-122.394817%2C%22time%22%3A1500830577%7D%2C%7B%22lat%22%3A37.793764%2C%22lon%22%3A-122.395647%2C%22time%22%3A1500830587%7D%2C%7B%22lat%22%3A37.792622%2C%22lon%22%3A-122.396474%2C%22time%22%3A1500830597%7D%2C%7B%22lat%22%3A37.792889%2C%22lon%22%3A-122.397606%2C%22time%22%3A1500830607%7D%2C%7B%22lat%22%3A37.793728%2C%22lon%22%3A-122.397977%2C%22time%22%3A1500830614%7D%5D%7D
Graceway Solution_to_Joseph Tan CPA,60.0,10.0,http://valhalla:8002/route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A37.753527%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.491054%7D%2C%7B%22lat%22%3A37.758594%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.492805%7D%5D%2C%22costing%22%3A%22auto%22%2C%22id%22%3A%22my_work_route%22%7D,http://valhalla:8002/trace_attributes?json=%7B%22trace_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A5%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22encoded_polyline%22%3A%22aoh_gAdjgshFVrPLpHzAdbAqsBbGqsBbGwqAtD%22%2C%22costing%22%3A%22auto%22%7D,http://reporter:8003/report?json=%7B%22match_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A98.69%2C%22mode%22%3A%22auto%22%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22uuid%22%3A%22999999%22%2C%22trace%22%3A%5B%7B%22lat%22%3A37.753842%2C%22lon%22%3A-122.492322%2C%22time%22%3A1500830562%7D%2C%7B%22lat%22%3A37.753789%2C%22lon%22%3A-122.493478%2C%22time%22%3A1500830572%7D%2C%7B%22lat%22%3A37.754647%2C%22lon%22%3A-122.493241%2C%22time%22%3A1500830582%7D%2C%7B%22lat%22%3A37.755876%2C%22lon%22%3A-122.493216%2C%22time%22%3A1500830592%7D%2C%7B%22lat%22%3A37.756652%2C%22lon%22%3A-122.493241%2C%22time%22%3A1500830602%7D%2C%7B%22lat%22%3A37.757467%2C%22lon%22%3A-122.493297%2C%22time%22%3A1500830612%7D%2C%7B%22lat%22%3A37.757966%2C%22lon%22%3A-122.493265%2C%22time%22%3A1500830622%7D%2C%7B%22lat%22%3A37.758735%2C%22lon%22%3A-122.493189%2C%22time%22%3A1500830632%7D%2C%7B%22lat%22%3A37.758847%2C%22lon%22%3A-122.493304%2C%22time%22%3A1500830633%7D%5D%7D
Allstate Insurance_to_Gregory M Haynes,80.0,10.0,http://valhalla:8002/route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A37.792878%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.401021%7D%2C%7B%22lat%22%3A37.78667%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.404513%7D%5D%2C%22costing%22%3A%22auto%22%2C%22id%22%3A%22my_work_route%22%7D,http://valhalla:8002/trace_attributes?json=%7B%22trace_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A5%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22encoded_polyline%22%3A%22aeuagAftwmhFtm%40aHnD~h%40%5C%5C%60H%5ErEjApRhBxWdy%40mJly%40%7DJ~b%40cFzPyBvC_%40~C%5DjA%5Dt%40O%60C%3FxBNz%40N~DrFje%40ro%40xBvClUb%5Btx%40lhA%22%2C%22costing%22%3A%22auto%22%7D,http://reporter:8003/report?json=%7B%22match_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A100.0%2C%22mode%22%3A%22auto%22%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22uuid%22%3A%22999999%22%2C%22trace%22%3A%5B%7B%22lat%22%3A37.793432%2C%22lon%22%3A-122.400099%2C%22time%22%3A1500830589%7D%2C%7B%22lat%22%3A37.792448%2C%22lon%22%3A-122.400658%2C%22time%22%3A1500830599%7D%2C%7B%22lat%22%3A37.792682%2C%22lon%22%3A-122.401646%2C%22time%22%3A1500830609%7D%2C%7B%22lat%22%3A37.791288%2C%22lon%22%3A-122.401518%2C%22time%22%3A1500830619%7D%2C%7B%22lat%22%3A37.790065%2C%22lon%22%3A-122.400904%2C%22time%22%3A1500830629%7D%2C%7B%22lat%22%3A37.788924%2C%22lon%22%3A-122.401386%2C%22time%22%3A1500830639%7D%2C%7B%22lat%22%3A37.788322%2C%22lon%22%3A-122.402504%2C%22time%22%3A1500830649%7D%2C%7B%22lat%22%3A37.787622%2C%22lon%22%3A-122.403616%2C%22time%22%3A1500830659%7D%2C%7B%22lat%22%3A37.787533%2C%22lon%22%3A-122.404123%2C%22time%22%3A1500830669%7D%5D%7D
Quinn Notary Svc_to_Manulife Financial,80.0,10.0,http://valhalla:8002/route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A37.794447%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.404719%7D%2C%7B%22lat%22%3A37.793358%2C%22type%22%3A%22break%22%2C%22lon%22%3A-122.398782%7D%5D%2C%22costing%22%3A%22auto%22%2C%22id%22%3A%22my_work_route%22%7D,http://valhalla:8002/trace_attributes?json=%7B%22trace_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A5%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22encoded_polyline%22%3A%22eixagAhv~mhFuJo%7BAm%40gDm%40wDwC%7Di%40_%40%7DIyBed%40UwDLuEkF_%7C%40m%40uEvD%5DnSiCdZgDzZuDz%5BwDd%40%3FkGgbA%5DeE%22%2C%22costing%22%3A%22auto%22%7D,http://reporter:8003/report?json=%7B%22match_options%22%3A%7B%22turn_penalty_factor%22%3A500%2C%22sigma_z%22%3A4.07%2C%22breakage_distance%22%3A2000%2C%22search_radius%22%3A50%2C%22beta%22%3A3%2C%22gps_accuracy%22%3A100.0%2C%22mode%22%3A%22auto%22%7D%2C%22shape_match%22%3A%22map_snap%22%2C%22uuid%22%3A%22999999%22%2C%22trace%22%3A%5B%7B%22lat%22%3A37.794056%2C%22lon%22%3A-122.404027%2C%22time%22%3A1500830596%7D%2C%7B%22lat%22%3A37.794242%2C%22lon%22%3A-122.402513%2C%22time%22%3A1500830606%7D%2C%7B%22lat%22%3A37.794428%2C%22lon%22%3A-122.400901%2C%22time%22%3A1500830616%7D%2C%7B%22lat%22%3A37.794676%2C%22lon%22%3A-122.399514%2C%22time%22%3A1500830626%7D%2C%7B%22lat%22%3A37.793991%2C%22lon%22%3A-122.39922%2C%22time%22%3A1500830636%7D%2C%7B%22lat%22%3A37.79299%2C%22lon%22%3A-122.398776%2C%22time%22%3A1500830646%7D%2C%7B%22lat%22%3A37.792898%2C%22lon%22%3A-122.397889%2C%22time%22%3A1500830655%7D%5D%7D
I then wrote a small program to rip through the file and check the before and after. The program steps through each test, and calls trace_attributes
on a local service first with the timestamps, and then again with the timestamps removed (so the algorithm cant use them). Here's the program that does this (remember to run a valhalla server on port 8002 for this to make requests against):
#!/usr/bin/env python
import urllib
import json
import requests
import sys
#six degrees of precision in valhalla
inv = 1.0 / 1e6;
#decode an encoded string
def decode(encoded):
decoded = []
previous = [0,0]
i = 0
#for each byte
while i < len(encoded):
#for each coord (lat, lon)
ll = [0,0]
for j in [0, 1]:
shift = 0
byte = 0x20
#keep decoding bytes until you have this coord
while byte >= 0x20:
byte = ord(encoded[i]) - 63
i += 1
ll[j] |= (byte & 0x1f) << shift
shift += 5
#get the final value adding the previous offset and remember it for the next
ll[j] = previous[j] + (~(ll[j] >> 1) if ll[j] & 1 else (ll[j] >> 1))
previous[j] = ll[j]
#scale by the precision and chop off long coords also flip the positions so
#its the far more standard lon,lat instead of lat,lon
decoded.append([float('%.6f' % (ll[1] * inv)), float('%.6f' % (ll[0] * inv))])
#hand back the list of coordinates
return decoded
def fix_request(request):
request['shape'] = request.pop('trace')
request['trace_options'] = request.pop('match_options')
del request['trace_options']['mode']
del request['trace_options']['search_radius']
request['trace_options']['gps_accuracy'] *= float(sys.argv[2])
request['trace_options']['max_route_time_factor'] = float(sys.argv[3])
request['costing'] = 'auto'
return request
skip = True
with open(sys.argv[1]) as f:
for line in f:
if skip:
skip = False
continue
parts = line.split(',')
route = urllib.unquote(parts[4])
route = json.loads(route[route.find('json=')+5:])
route = decode(route['encoded_polyline'])
request = urllib.unquote(parts[5])
request = json.loads(request[request.find('json=')+5:])
request = fix_request(request)
gps = [ [p['lon'], p['lat']] for p in request['shape'] ]
after = requests.post('http://localhost:8002/trace_attributes?', data = json.dumps(request))
after = json.loads(after.text)
after = decode(after['shape'])
for p in request['shape']:
del p['time']
before = requests.post('http://localhost:8002/trace_attributes?', data = json.dumps(request))
before = json.loads(before.text)
before = decode(before['shape'])
geo = {'type':'FeatureCollection','features':[
{'geometry':{'type':'LineString','coordinates':route},'type':'Feature','properties':{'stroke':'#00ff00','stroke-width':2,'description':'original'}},
{'geometry':{'type':'LineString','coordinates':gps},'type':'Feature','properties':{'stroke':'#0000ff','stroke-width':2,'descripition':'fake gps'}},
{'geometry':{'type':'LineString','coordinates':before},'type':'Feature','properties':{'stroke':'#ffff00','stroke-width':2,'descripition':'before'}},
{'geometry':{'type':'LineString','coordinates':after},'type':'Feature','properties':{'stroke':'#00ffff','stroke-width':2,'description':'after'}}
]}
print parts[0]
print ''.join(['http://geojson.io/#data=data:application/json,',urllib.quote(json.dumps(geo, separators=(',', ':')))])
print
You'll notice that the program takes 3 arguments. The first is the name of the csv file. The second argument is a multiplier by which we scale the original requests' gps_accuracy
. When measuring the actual faked locations in the generated gps path from the original route path, i noticed that they were often way outside of the gps_accuracy
. For example there are some where the faked gps point is 140m away but the accuracy is set to 98m. This means that the algorithm will not be able to find the correct route no matter what as it wont search for candidate edges further than 98m from that gps point. I think there may have been a miscommunication. Perhaps it was assumed that we used search_radius + gps_accuracy
when finding candidates but in fact we use: max(search_radius, gps_accuracy)
apologies for this miscommunication. Anyway the third argument is the max_route_time_factor
which is how much time to allow a path between two points to take as a multiplier of the actual time between the two points in the input. For my testing I ended up using: ./test.py blah.csv 2 1.5
so thats doubling the gps_accuracy
and allowing for 50% more time to be spent between two adjacent points in a faked gps.
So what were the results. Well below you'll find geojsons which are linked to geojson.io. Each one has 4 linestrings. a green one which is the original route, a blue one which is the faked gps, a yellow one which is the map match without using time information, and a cyan one which is the map match with using time information. sometimes they overlap, sorry about that...
All but two of them seem fixed. I think this is pretty good given the extreme amount of noise (> 100m) in some of these.