mappymatch.matchers.lcss.lcss

Classes

LCSSMatcher(road_map[, distance_epsilon, ...])

Map matcher based on the Longest Common Subsequence (LCSS) algorithm.

class mappymatch.matchers.lcss.lcss.LCSSMatcher(road_map: MapInterface, distance_epsilon: float = 50.0, similarity_cutoff: float = 0.9, cutting_threshold: float = 10.0, random_cuts: int = 0, distance_threshold: float = 10000)

Map matcher based on the Longest Common Subsequence (LCSS) algorithm.

This matcher implements the trajectory segmentation approach described in:

Zhu, Lei, Jacob R. Holden, and Jeffrey D. Gonder. "Trajectory Segmentation Map-Matching Approach for Large-Scale, High-Resolution GPS Data." Transportation Research Record: Journal of the Transportation Research Board 2645 (2017): 67-75.

The algorithm works by: 1. Computing candidate paths through the road network 2. Scoring path segments using LCSS similarity 3. Iteratively refining segments by identifying cutting points 4. Merging segments until similarity threshold is met

Args:

road_map: The road network to match against (must implement MapInterface) distance_epsilon: Maximum distance (in meters) for a GPS point to be considered near a road segment. Points beyond this distance contribute less to similarity. Default is 50 meters. similarity_cutoff: Minimum similarity score (0-1) to stop iterative refinement. Higher values demand better matching quality. Default is 0.9. cutting_threshold: Distance threshold (in meters) for identifying potential cutting points where trajectory should be split. Default is 10 meters. random_cuts: Number of random cutting points to add at each iteration for exploration. Usually 0 for deterministic results. Default is 0. distance_threshold: Maximum distance (in meters) for matching a point to a road. Points beyond this are left unmatched. Default is 10000 meters (10km).

Examples:

>>> from mappymatch.matchers.lcss import LCSSMatcher
>>> from mappymatch.maps.nx import NxMap
>>>
>>> # Load a road network
>>> road_map = NxMap.from_file('network.pickle')
>>>
>>> # Create matcher with default parameters
>>> matcher = LCSSMatcher(road_map)
>>> result = matcher.match_trace(trace)

match_trace(trace: Trace) → MatchResult

Match a GPS trace to the underlying road network.

This is the primary method of any matcher. It takes a sequence of GPS coordinates and returns matching results that link each coordinate to road segments.

Args:

trace: A Trace object containing the GPS coordinates to match

Returns:

A MatchResult containing: - matches: A list of Match objects linking each GPS point to a road - path: An optional list of Road objects representing the matched route

Examples:

>>> matcher = SomeMatcher(road_map)
>>> trace = Trace.from_csv('gps_data.csv')
>>> result = matcher.match_trace(trace)
>>>
>>> # Access the matches
>>> for match in result.matches:
...     if match.road is not None:
...         print(f"Matched to road {match.road.road_id}")