search

gis-ops / docker-valhalla

This is our flexible Docker repository for the Valhalla routing engine
MIT License
233 stars 69 forks source link

wrong interpolated edge_index #56

Closed JackCaster closed 2 years ago

JackCaster commented 2 years ago

I stumbled upon a strange behavior. When I map-match a series of GPS points, the edge_index for some interpolated coordinates is wrong and it suggests a type overflow. For example a request to match this path in Sweden:

{"shape": [{"lat": 59.1351943, "lon": 12.9106227}, {"lat": 59.1350895, "lon": 12.9102298}, {"lat": 59.1349769, "lon": 12.9098136}, {"lat": 59.1348625, "lon": 12.9094006}, {"lat": 59.1347436, "lon": 12.9089806}, {"lat": 59.1346232, "lon": 12.9085561}, {"lat": 59.1345016, "lon": 12.9081334}, {"lat": 59.1343729, "lon": 12.9076922}, {"lat": 59.1342497, "lon": 12.9072771}, {"lat": 59.1341196, "lon": 12.9068384}, {"lat": 59.1339959, "lon": 12.9064213}, {"lat": 59.1338713, "lon": 12.9060012}, {"lat": 59.1337374, "lon": 12.905547}, {"lat": 59.1336053, "lon": 12.905092}, {"lat": 59.1334732, "lon": 12.9046269}, {"lat": 59.1333367, "lon": 12.9041463}, {"lat": 59.1331933, "lon": 12.9036414}, {"lat": 59.1330518, "lon": 12.9031436}, {"lat": 59.1330518, "lon": 12.9031436}, {"lat": 59.1329084, "lon": 12.9026386}, {"lat": 59.1327607, "lon": 12.902146}, {"lat": 59.1326166, "lon": 12.9016645}, {"lat": 59.1324723, "lon": 12.9011763}, {"lat": 59.1323391, "lon": 12.9006928}, {"lat": 59.1322038, "lon": 12.9002123}, {"lat": 59.1320647, "lon": 12.899733}, {"lat": 59.1319351, "lon": 12.8992546}, {"lat": 59.1317997, "lon": 12.8987592}, {"lat": 59.1316708, "lon": 12.8982624}, {"lat": 59.1315455, "lon": 12.8977589}, {"lat": 59.1314248, "lon": 12.8972375}, {"lat": 59.1312915, "lon": 12.8967272}, {"lat": 59.1311525, "lon": 12.8962211}, {"lat": 59.1310191, "lon": 12.8956994}, {"lat": 59.1308916, "lon": 12.8951789}, {"lat": 59.130766, "lon": 12.8946585}, {"lat": 59.130766, "lon": 12.8946585}, {"lat": 59.1306456, "lon": 12.8941393}, {"lat": 59.1305301, "lon": 12.8936165}, {"lat": 59.1305301, "lon": 12.8936165}, {"lat": 59.1304226, "lon": 12.8931162}, {"lat": 59.1303123, "lon": 12.8926208}, {"lat": 59.1301916, "lon": 12.8921108}, {"lat": 59.1300863, "lon": 12.8916491}, {"lat": 59.129992, "lon": 12.8911705}, {"lat": 59.1299016, "lon": 12.8907186}, {"lat": 59.1298205, "lon": 12.8902816}, {"lat": 59.1297394, "lon": 12.8898267}, {"lat": 59.1296575, "lon": 12.8893859}, {"lat": 59.1295691, "lon": 12.8889934}, {"lat": 59.1294846, "lon": 12.8885876}, {"lat": 59.129424, "lon": 12.8882083}, {"lat": 59.1293505, "lon": 12.8878079}, {"lat": 59.1292792, "lon": 12.8874015}, {"lat": 59.1292097, "lon": 12.8869955}, {"lat": 59.1291376, "lon": 12.8866155}, {"lat": 59.1290589, "lon": 12.8862546}, {"lat": 59.1289931, "lon": 12.8859302}, {"lat": 59.1289455, "lon": 12.8856161}, {"lat": 59.1289455, "lon": 12.8856161}, {"lat": 59.1288869, "lon": 12.8853347}, {"lat": 59.1288386, "lon": 12.8850719}, {"lat": 59.1288386, "lon": 12.8850719}, {"lat": 59.1287849, "lon": 12.8848249}, {"lat": 59.1287556, "lon": 12.8845553}, {"lat": 59.1287556, "lon": 12.8845553}, {"lat": 59.1287277, "lon": 12.8842934}, {"lat": 59.1286984, "lon": 12.884024}, {"lat": 59.1286634, "lon": 12.8837711}, {"lat": 59.1286208, "lon": 12.8835339}, {"lat": 59.1285614, "lon": 12.883309}, {"lat": 59.1285039, "lon": 12.8830943}, {"lat": 59.1284515, "lon": 12.8828419}, {"lat": 59.1284063, "lon": 12.8825895}, {"lat": 59.1283572, "lon": 12.8823216}, {"lat": 59.1283037, "lon": 12.8820254}, {"lat": 59.1283037, "lon": 12.8820254}, {"lat": 59.1282491, "lon": 12.8817226}, {"lat": 59.1282491, "lon": 12.8817226}, {"lat": 59.1281905, "lon": 12.8814059}, {"lat": 59.1281359, "lon": 12.8811005}, {"lat": 59.1280742, "lon": 12.8807817}, {"lat": 59.1280178, "lon": 12.880447}, {"lat": 59.1279617, "lon": 12.8800798}, {"lat": 59.1279099, "lon": 12.8797194}, {"lat": 59.1278427, "lon": 12.8793521}, {"lat": 59.127774, "lon": 12.8789595}, {"lat": 59.1277071, "lon": 12.8785752}, {"lat": 59.1276366, "lon": 12.8781806}, {"lat": 59.1275606, "lon": 12.8777764}, {"lat": 59.1274786, "lon": 12.8773348}, {"lat": 59.127397, "lon": 12.8769022}, {"lat": 59.1273152, "lon": 12.8764539}, {"lat": 59.1272349, "lon": 12.8760064}, {"lat": 59.1271525, "lon": 12.8755564}, {"lat": 59.1271525, "lon": 12.8755564}, {"lat": 59.1270718, "lon": 12.8751185}, {"lat": 59.126988, "lon": 12.8746642}, {"lat": 59.126988, "lon": 12.8746642}, {"lat": 59.1269029, "lon": 12.8742095}, {"lat": 59.1268169, "lon": 12.87375}, {"lat": 59.1268169, "lon": 12.87375}, {"lat": 59.1267256, "lon": 12.8732622}, {"lat": 59.126637, "lon": 12.8728158}, {"lat": 59.126637, "lon": 12.8728158}, {"lat": 59.1265425, "lon": 12.8723569}, {"lat": 59.1264432, "lon": 12.8718861}, {"lat": 59.12634, "lon": 12.8714167}, {"lat": 59.1262321, "lon": 12.8709484}, {"lat": 59.1262321, "lon": 12.8709484}, {"lat": 59.1261191, "lon": 12.8704805}, {"lat": 59.1259994, "lon": 12.8700021}, {"lat": 59.1258912, "lon": 12.8695509}, {"lat": 59.1257755, "lon": 12.8690892}, {"lat": 59.1257755, "lon": 12.8690892}, {"lat": 59.125659, "lon": 12.8686384}, {"lat": 59.1255351, "lon": 12.8681984}, {"lat": 59.1255351, "lon": 12.8681984}, {"lat": 59.1254139, "lon": 12.8677511}, {"lat": 59.1252822, "lon": 12.8673184}, {"lat": 59.1252822, "lon": 12.8673184}, {"lat": 59.1251535, "lon": 12.8668918}, {"lat": 59.1250219, "lon": 12.8664892}, {"lat": 59.1248912, "lon": 12.8660713}, {"lat": 59.1247589, "lon": 12.8656683}, {"lat": 59.1246179, "lon": 12.8652747}, {"lat": 59.1244861, "lon": 12.8648921}, {"lat": 59.1243598, "lon": 12.8644952}, {"lat": 59.1242398, "lon": 12.8641084}, {"lat": 59.1242398, "lon": 12.8641084}, {"lat": 59.1241014, "lon": 12.8637066}, {"lat": 59.1239704, "lon": 12.8633126}, {"lat": 59.1238494, "lon": 12.8629063}, {"lat": 59.1237271, "lon": 12.8625139}, {"lat": 59.1236051, "lon": 12.8621097}, {"lat": 59.1236051, "lon": 12.8621097}, {"lat": 59.123488, "lon": 12.8617131}, {"lat": 59.123365, "lon": 12.8613567}, {"lat": 59.1232449, "lon": 12.8609957}, {"lat": 59.1231265, "lon": 12.8606566}, {"lat": 59.1230168, "lon": 12.860282}, {"lat": 59.1228905, "lon": 12.8598888}, {"lat": 59.1227557, "lon": 12.859479}, {"lat": 59.1226172, "lon": 12.8590575}, {"lat": 59.1224671, "lon": 12.8586303}, {"lat": 59.1224671, "lon": 12.8586303}, {"lat": 59.1223177, "lon": 12.8582021}, {"lat": 59.1223177, "lon": 12.8582021}, {"lat": 59.1221753, "lon": 12.8577751}, {"lat": 59.122022, "lon": 12.8573452}, {"lat": 59.1218761, "lon": 12.856908}, {"lat": 59.1217169, "lon": 12.8564687}, {"lat": 59.1215626, "lon": 12.8560176}, {"lat": 59.1214098, "lon": 12.8555618}, {"lat": 59.121243, "lon": 12.855078}, {"lat": 59.1210756, "lon": 12.8545847}, {"lat": 59.1209085, "lon": 12.8540814}, {"lat": 59.1207395, "lon": 12.8535718}, {"lat": 59.1205756, "lon": 12.853047}, {"lat": 59.1204041, "lon": 12.8525221}, {"lat": 59.1202493, "lon": 12.851977}, {"lat": 59.1200829, "lon": 12.8514452}, {"lat": 59.119922, "lon": 12.8508939}, {"lat": 59.1197689, "lon": 12.8503191}, {"lat": 59.1196252, "lon": 12.8497712}, {"lat": 59.1194774, "lon": 12.8492097}, {"lat": 59.1194774, "lon": 12.8492097}, {"lat": 59.1193306, "lon": 12.8486497}, {"lat": 59.1193306, "lon": 12.8486497}, {"lat": 59.1191924, "lon": 12.8480979}, {"lat": 59.1190519, "lon": 12.8475405}, {"lat": 59.11892, "lon": 12.8469791}, {"lat": 59.1187896, "lon": 12.8464276}, {"lat": 59.1186604, "lon": 12.8458586}, {"lat": 59.118536, "lon": 12.8452921}, {"lat": 59.118422, "lon": 12.8447179}, {"lat": 59.1183107, "lon": 12.8441446}, {"lat": 59.1182072, "lon": 12.8435604}, {"lat": 59.1181037, "lon": 12.8429671}, {"lat": 59.1180048, "lon": 12.8424031}, {"lat": 59.1178989, "lon": 12.8418071}, {"lat": 59.1177946, "lon": 12.8412336}, {"lat": 59.1177946, "lon": 12.8412336}, {"lat": 59.1176914, "lon": 12.8406515}, {"lat": 59.1175849, "lon": 12.8400723}, {"lat": 59.1174818, "lon": 12.8394931}, {"lat": 59.1173815, "lon": 12.8389184}, {"lat": 59.1172824, "lon": 12.8383592}, {"lat": 59.1171735, "lon": 12.8377909}, {"lat": 59.1170789, "lon": 12.837276}, {"lat": 59.116967, "lon": 12.8366385}, {"lat": 59.1168594, "lon": 12.8360661}, {"lat": 59.116761, "lon": 12.8354896}, {"lat": 59.116761, "lon": 12.8354896}, {"lat": 59.1166592, "lon": 12.8349059}, {"lat": 59.1165538, "lon": 12.8343218}, {"lat": 59.1164504, "lon": 12.8337388}, {"lat": 59.1163452, "lon": 12.8331675}, {"lat": 59.1162412, "lon": 12.832611}, {"lat": 59.1161397, "lon": 12.8320477}, {"lat": 59.116035, "lon": 12.8314858}, {"lat": 59.1159374, "lon": 12.8309205}, {"lat": 59.1158359, "lon": 12.8303586}, {"lat": 59.1158359, "lon": 12.8303586}, {"lat": 59.1157334, "lon": 12.8297988}, {"lat": 59.1156382, "lon": 12.8292573}, {"lat": 59.1155509, "lon": 12.8287563}, {"lat": 59.1154558, "lon": 12.8282577}, {"lat": 59.1153768, "lon": 12.8277809}, {"lat": 59.1152894, "lon": 12.827325}, {"lat": 59.1152023, "lon": 12.8268581}, {"lat": 59.1151214, "lon": 12.8264156}, {"lat": 59.1150441, "lon": 12.8259364}, {"lat": 59.1149772, "lon": 12.8255326}, {"lat": 59.1148854, "lon": 12.8250042}, {"lat": 59.1148001, "lon": 12.8245355}, {"lat": 59.1147128, "lon": 12.8240587}, {"lat": 59.1146205, "lon": 12.8235788}, {"lat": 59.1146205, "lon": 12.8235788}, {"lat": 59.114527, "lon": 12.8230964}, {"lat": 59.1144336, "lon": 12.8225948}, {"lat": 59.1143275, "lon": 12.8220892}, {"lat": 59.1142197, "lon": 12.8215909}, {"lat": 59.1141086, "lon": 12.8210934}], "costing": "auto", "shape_match": "map_snap"}

returns (partial output)

...
{"distance_from_trace_point":0.723,"edge_index":5,"type":"matched","distance_along_edge":0.255,"lat":59.128400,"lon":12.882594},
{"distance_from_trace_point":0.776,"edge_index":5,"type":"matched","distance_along_edge":0.466,"lat":59.128351,"lon":12.882326},
{"distance_from_trace_point":0.916,"edge_index":5,"type":"matched","distance_along_edge":0.698,"lat":59.128296,"lon":12.882031},
{"distance_from_trace_point":0.916,"edge_index":5,"type":"interpolated","distance_along_edge":0.698,"lat":59.128296,"lon":12.882031},
{"distance_from_trace_point":1.070,"edge_index":5,"type":"matched","distance_along_edge":0.936,"lat":59.128240,"lon":12.881729},
{"distance_from_trace_point":1.070,"edge_index":18446744073709551615,"type":"interpolated","distance_along_edge":0.936,"lat":59.128240,"lon":12.881729},
{"distance_from_trace_point":0.874,"edge_index":6,"type":"matched","distance_along_edge":0.064,"lat":59.128183,"lon":12.881411},
{"distance_from_trace_point":0.817,"edge_index":6,"type":"matched","distance_along_edge":0.146,"lat":59.128129,"lon":12.881105},
{"distance_from_trace_point":0.267,"edge_index":6,"type":"matched","distance_along_edge":0.233,"lat":59.128072,"lon":12.880783},
{"distance_from_trace_point":0.565,"edge_index":6,"type":"matched","distance_along_edge":0.322,"lat":59.128013,"lon":12.880450},
...

where you can see that one edge_index is 18446744073709551615:

{"distance_from_trace_point":1.070,"edge_index":18446744073709551615,"type":"interpolated","distance_along_edge":0.936,"lat":59.128240,"lon":12.881729},

Because 18446744073709551615 is the max uint64, it may be an error in type casting. I see this happening for interpolated matches only. I also noticed that this happens when the interpolation is between two edges (in the case above, the interpolation is between edge 5 and 6):

{"distance_from_trace_point":1.070,"edge_index":5,"type":"matched","distance_along_edge":0.936,"lat":59.128240,"lon":12.881729},
{"distance_from_trace_point":1.070,"edge_index":18446744073709551615,"type":"interpolated","distance_along_edge":0.936,"lat":59.128240,"lon":12.881729},
{"distance_from_trace_point":0.874,"edge_index":6,"type":"matched","distance_along_edge":0.064,"lat":59.128183,"lon":12.881411}

while it works fine within the same edge (in the case above, the within the edge 5 the interpolation is correct):

{"distance_from_trace_point":0.916,"edge_index":5,"type":"matched","distance_along_edge":0.698,"lat":59.128296,"lon":12.882031},
{"distance_from_trace_point":0.916,"edge_index":5,"type":"interpolated","distance_along_edge":0.698,"lat":59.128296,"lon":12.882031},
{"distance_from_trace_point":1.070,"edge_index":5,"type":"matched","distance_along_edge":0.936,"lat":59.128240,"lon":12.881729},

These GPS are in Sweden, but I can replicate the same behavior in Italy too. Is this something you experienced too?

nilsnolde commented 2 years ago

we're only using map-matching for live traffic tbh, didn't have a need otherwise yet. however, what you're pointing to is a valhalla issue. we're really just wrapping whatever is happening upstream with some more convenience than the upstream docker image. wanna say, whenever you see strange valhalla behavior, esp with weird responses, it's more likely the culprit is there, e.g. https://github.com/valhalla/valhalla/issues/3371

JackCaster commented 2 years ago

Right, I apologize. I should have opened that isse there. Thank you for pointing that out