mappymatch fails to some traces and produces weird results for others

[manuelck99]

I'm currently using mappymatch as part of a larger system I'm developing for a university project. My current workflow with the library is that I fetch an OSMnx graph (in EPSG:4326 (WGS 84)), which I use for other purposes too, then I manually build an NxMap, like so:

map = NxMap(parse_osmnx_graph(G_ox, xy=True, network_type=NetworkType.DRIVE))

I then also build a Trace from a Pandas DataFrame, where the rows are sorted chronologically and the coordinates are provided in EPSG:4326 (WGS 84), like so:

trace = Trace.from_dataframe(trace_df, lon_column="longitude", lat_column="latitude", xy=True)

Finally, I map match thousands of such traces with:

matcher = LCSSMatcher(road_map)
match_result = matcher.match_trace(trace)
path_df = match_result.path_to_dataframe()

Unfortunately, two issues sometimes arise.

First, for some few traces the LCSSMatcher produces a match_result with an empty path_df, probably because match_result.path is None. What could be a reason for the LCSSMatcher to produce such a result? I could study your implementation and paper, but I'm asking on a conceptual level here: For what kind of traces does LCSS fail?

Second, sometimes the LCSSMatcher succeeds and I get a populated path_df, however the produced path is not continuous. By that I mean that for example the following edges/roads are produced as a result [(3, 4), (5, 6), (6, 7), (7, 8), ...]. I assumed that an edge's origin would always be the previous edges destination, but like in the example with (3, 4), (5, 6) this is sometimes not the case. What could be a possible reason why the LCSS algorithm produces something like that?

[nreinicke]

Thanks for opening this issue and sorry that you're having trouble with the package. There's a lot of complexity in the various types of traces that the algorithm is trying to match and so it's hard to make too many generalities about why it might fail to match. Would you be able to share any of the traces that are resulting in this weird behavior? Perhaps we can take a look to see if there's a bug or if these are really edge cases that can't be matched properly.