后端【免费下载链接】valhallaOpen Source Routing Engine for OpenStreetMap项目地址https://gitcode.com/gh_mirrors/va/valhalla点击查看免费下载Meili 是 Valhalla 开源路由引擎Open Source Routing Engine for OpenStreetMap中负责**地图匹配map matching**的核心命名空间它把一段通常带有噪声的 GPS 轨迹测量点序列匹配到底层路网之上输出每个点吸附到哪条边、吸附在什么位置以及完整路径走了哪些边。本文以 Meili 架构文档 为主线结合仓库源码与配置实现逐层拆解 Meili 的候选生成、Viterbi 搜索、插值、路径构建、备选路径alternatives与 Thor 契约并给出可直接落地的配置参数、库 API 与 HTTP 服务调用方式。读完本文你将能够理解 Meili 的完整处理流水线知道如何调整匹配精度与性能参数并能独立通过配置文件和源码定位每一个关键环节。概述Meili 在 Valhalla 中的定位Meili 是 Valhalla 库中的一个命名空间提供地图匹配所需的算法与数据结构。它的功能范围本质上限定于微软 Newson 与 Krumm 提出的Hidden Markov Map Matching Through Noise and Sparseness方法给定一组 GPS 测量HMM 中的观测每个测量需要匹配到一组潜在候选路段HMM 中的隐状态之一问题转化为寻找概率最大的候选序列。Meili 的命名延续了 Valhalla 的北欧神话主题Meili 是 ThorValhalla 的路由库的兄弟因为地图匹配与路由紧密相关因此得名。此外该软件的主要作者来自 Mapillary 团队注意到美丽mĕilì的中文发音与 Meili 相同这也被作者视为两个团队间一次美好的合作。一个需要特别强调的架构边界是Meili 不负责把匹配结果打包成 Thor 路由模块定义的路线路径route path。也就是说从 Meili 的输出MatchResult序列 EdgeSegment序列转换为 Thor 路由 API 期望的格式存在非平凡的工作量这一转换正是下文Thor Contract一节的主题。从源码结构看Meili 模块的完整实现位于 src/meili/实现与 valhalla/meili/头文件中主要包括candidate_search、map_matcher、map_matcher_factory、match_result、match_route、measurement、routing、state、stateid、transition_cost_model、emission_cost_model、viterbi_search等组件。Meili 代码布局五步处理流水线Meili 的主入口是MapMatcher::OfflineMatch见 src/meili/map_matcher.cc#L691其处理流程可以划分为以下步骤Measurements │ ▼ [AppendMeasurements] ──► 决定哪些点参与匹配、哪些点留待插值构建候选矩阵 │ ▼ [CandidateQuery] ──► 为每个参与匹配的测量点查询半径内的候选边 │ ▼ [ViterbiSearch] ──► 在状态图上动态规划求出概率最高的 StateId 序列 │ ▼ [FindMatchResults] ──► 输出每个 State 对应的 MatchResult吸附点信息 │ ▼ [Interpolation] ──► 把被跳过的测量点投影到相邻 State 间的路线上 │ ▼ [ConstructRoute] ──► 沿 LabelSet 回溯 EdgeLabel 链产出 EdgeSegment 序列AppendMeasurements构建候选矩阵Meili 的第一步是决定要对哪些轨迹点进行地图匹配。你可能认为它会对每一个点都做匹配它确实最终会为每个点产生结果但在实际的路由计算中它并不一定使用每一个点。这里允许指定一个插值距离interpolation distance当相邻点彼此靠得很近时只保留其中一个用于匹配计算其余点会在匹配完成后被插值interpolate到匹配路线上。这样做有两个收益提升速度——参与路由计算的点数大幅减少规避静止物体的 GPS 抖动问题——原地抖动会产生看似来回折返的噪声点。这部分工作由AppendMeasurements函数完成src/meili/map_matcher.cc#L837它把参与匹配的轨迹点追加进一个可以理解为矩阵的结构中。这个矩阵里有什么对于AppendMeasurements决定参与路由计算的每一个输入点矩阵中建立一列column每一列可以有 1 行或多行但不同列的行数不一定相同。每一行代表该轨迹点的一个边候选edge candidate——即输入轨迹点搜索半径范围内、路网图中某条边上的一个吸附点snap point。上图为某个输入轨迹点在 50m 半径内的 4 个洋红色边候选。AppendMeasurements最终会调用CandidateQuery::Query来获取给定轨迹点的候选列表。CandidateQuery精细分辨率的空间索引缓存CandidateQuery与 Loki 的Loki::Search提供类似功能但有一个关键差异CandidateQuery维护了路网几何的精细分辨率内存空间索引/缓存。这意味着一旦缓存预热它能在处理大量点时获得比 Loki 高得多的吞吐量。这正是地图匹配与路由使用场景的本质区别路由通常不会有成千上万个途经点但 GPS 轨迹常常以 1Hz 频率上报——一段 15 分钟的轨迹就接近 1000 个点。因此在候选查询上Meili 必须走内存索引这条更快的路。文档也明确指出未来希望能移除CandidateQuery、改用Loki::Search的功能但当前性能考量阻止了这一替换。从实现上看候选查询组件的空间查询算法简单而高效详见 implementation-details.md在查询前把路网图块graph tile空间划分为grid_size的方格网格默认为 500×500见 valhalla/meili/config.h预计算每个方格与哪些路段相交查询时只需从半径覆盖的方格中取回所有路段即可。核心实现在 src/meili/candidate_search.cc 的CandidateCollector::WithinSquaredDistance中它遍历半径内的候选边、同时取出其反向边opposing edge并将轨迹点投影到边上生成候选Location。Viterbi在状态图上寻找最高概率路径Viterbi 是一种用于在隐状态图如隐马尔可夫模型中寻找路径的动态规划算法。在 Meili 中它被用来以最少的路径计算次数确定最高概率的地图匹配结果。可以把上文描述的候选矩阵看作状态图中的一系列节点每一列中的每一行都与前一列、后一列中的每一行存在连接代码中把这些唯一的列/行组合称为State状态每个 State 拥有一个StateId它记录该状态属于哪一列0..n以及该列中的哪一个候选0..m。在上图中候选 0、1、2 位于 column 0候选 3、4、5、6 位于 column 1。ViterbiSearch通过逐对迭代相邻列、并在列间候选行之间跑路由来工作。路由过程中度量两个指标发射成本emission cost候选点离路网有多近与 HMM 中发射概率负相关转移成本transition cost两个候选之间沿路网路径的网络距离的函数与 HMM 中转移概率负相关。Viterbi 搜索结束时返回一条概率最高成本最低的路径即一个StateId序列。需要说明的是路径上可能存在某些段落无法在给定的两个State之间甚至相邻两列的全部候选对之间找到路由——这就是下文会讲到的不连续discontinuity。在实现层面valhalla/meili/viterbi_search.h 定义了统一接口IViterbiSearch与两个实现NaiveViterbiSearch朴素 Viterbi 算法支持最大化/最小化两种目标和ViterbiSearch基于 Dijkstra 的惰性 Viterbi 算法只支持最小化目标因为其基于 Dijkstra。MapMatching类继承自ViterbiSearchvalhalla/meili/map_matching.h并实现其虚成本函数TransitionCost与EmissionCost每个候选在进入组件时会被赋予唯一 ID 与相同的时间戳ID 标识状态、时间标识它来自哪个候选簇内部称这种包装后的候选为state。Match Points产出 MatchResult状态图路径计算完成后需要取出 Meili 输出的第一部分——最终路径用到了哪些候选。这通过FindMatchResults完成src/meili/map_matcher.cc#L450它遍历状态返回一个MatchResult对象向量。MatchResult包含的关键信息详见 valhalla/meili/match_result.h匹配到了哪条边edgeidValhalla 瓦片数据中标识边与节点的GraphId吸附到边之后所在的经纬度lnglat沿边的距离以百分比表示等。这些元数据很有用最终服务 API 的地图匹配输出中会包含它们——要么通过起终点Location间接携带要么直接出现在trace_attributes或 OSRM 风格输出中。Interpolation把跳过的点投影回路线前面得到的MatchResult只覆盖了AppendMeasurements认为必须参与路由计算的那些点。对于一部分输入点我们并没有为它们建立列或状态。下面是一个 ASCII 示意图p1p2------p3-------p4p5p6-----------p7--------------p8-----------p9p10上例中{p2, p5, p6, p9}全部是被插值的点它们因为距离前一个点太近而被跳过p9则是因为靠近最后一个无法被插值的点终点。接下来的做法是再次遍历相邻状态对如果两个状态之间存在未被使用即被插值的输入点就把这些点按顺序依次投影到这两个状态之间的路线上。以上图为例如果在 p4 和 p7 之间找到了路线就把 p5 和 p6 投影到该路线几何上以计算它们的MatchResult。插值还有一个重要保证序列顺序不变——最终路线几何中 p4 一定在 p5 之前、p5 在 p6 之前、p6 在 p7 之前。实现对应 src/meili/map_matcher.cc#L169 的InterpolateMeasurements其在OfflineMatch主循环中按列逐一插入插值结果src/meili/map_matcher.cc#L774-L800。Route Building沿 LabelSet 回溯出 EdgeSegment接下来取 Meili 输出的第二部分——实际穿过的图路径。这通过ConstructRoute计算src/meili/match_route.cc#L204ConstructRoute使用State获取以LabelSet中EdgeLabel集合形式存储的边序列LabelSet保存了一次图扩展graph expansion看到的所有边标签edge label对于给定的State我们知道它到达目标State时看到的最后一个标签因此只要沿着EdgeLabel链一路回溯到起始State即可还原路线——这就像没有指针的链表靠的是LabelSet中的索引MergeRoute函数src/meili/match_route.cc#L93负责恢复两个状态之间的路径。从这些EdgeLabel出发最终构造出EdgeSegment对象向量这是ConstructRoute返回的最终对象。EdgeSegment记录它是图中的哪条边这条边被使用了多少起止比例匹配到该EdgeSegment上的第一个与最后一个MatchResult该EdgeSegment之后是否存在不连续discontinuity——如前所述当两列之间所有候选对都找不到路径时就会出现不连续。在构建过程中代码还会在标记为break或break_through的MatchResult处切断EdgeSegment。这类位置表示最终输出中希望产生路线分段route legs的地方为了不必在序列化阶段再拆分构建路线时就先把边切好。Alternatives返回 top k 最可能路径Meili 支持备选路径的概念API 中称之为best_paths文档建议未来重构为alternatives。它允许用户获取top k个最可能的路径但有两条重要限制限制一不连续即停止返回。如果某个结果中出现不连续则其后不再返回更多结果。例如即使请求 2 条结果如果第一条匹配就出现了不连续你只会得到 1 条。限制二冗余路径会被剔除。冗余路径指已经在前一个结果中见过的路径——技术上讲即EdgeSegment序列已经出现过。为什么会发生常见情形是一个MatchResult有两个候选但无论选哪一个路径经过的边序列完全相同。也就是说MatchResult的位置可能在动但路径没有实质变化。这在路口很常见一个候选位于某条边的中途另一个候选位于上一条边的末端而两条边都在路径上路径并未实质性改变。从 src/meili/map_matcher.cc#L728-L809 的OfflineMatch实现可以看到主循环按k迭代每次调用vs_.SearchPathVS从最后一列反向取得状态序列再还原为正序的StateId遇到不连续时置found_discontinuity并累积最大成本当已有结果且又发现不连续时立即停止对每条候选路径若在已有结果中找不到重复std::find(best_paths.rbegin(), best_paths.rend(), match_results)才保留从而天然实现了上述两条限制。Complications节点吸附候选的两大难题地图匹配中最大的复杂性来自节点吸附候选node snapped candidates——即输入轨迹点在图上最近的点是连接两条或多条边的节点。这类候选带来两个问题性能问题。你可能会想在该节点为每条边都放一个候选不就行了但这样做非常浪费因为每增加一个候选都会放大 Viterbi 需要计算的路由排列组合数量。因此路由器中采用了专门逻辑把节点吸附候选当作单个候选处理。歧义问题。节点本身并不指向某条边而 Meili 的其他数据结构MatchResult和EdgeSegment都基于边。于是当匹配发生在节点上时需要大量特判逻辑来打补丁。典型场景是某轨迹点是路线两个分段leg之间的分界点导致上一段的终点在某条边上、下一段的起点在另一条边上而共用的同一个MatchResult只存储一条边引用会与其中一段不一致。Thor Contract把匹配结果翻译成路由路径Meili 本身没有外部 API——它曾经有过但已被重构为通过 Valhalla 其余路由 API 访问。这意味着它必须满足与 Thor 相同的契约。该契约包含两部分一系列Location每个Location的选定候选被填充在 Meili 场景中即把MatchResult翻译为候选一条路径即一系列表示路径上各边及其成本/时长的PathInfo。上文描述的 Meili 主入口是OfflineMatchoffline指算法类型与在线算法相对。Thor 必须把该函数的输出——如前所述一串MatchResult与一串EdgeSegment——转换为契约格式。转换过程分两步首先通过FormPath每个路径查找算法都实现一个把EdgeSegment构建成PathInfo对象向量同时用MatchResult构建起终点Location然后对路径的每一段调用TripLegBuilder::Build参见 Thor 架构文档 中对TripLegBuilder的说明它会把路径补充成包含名称、几何等属性的详细TripPath供后续导航/引导生成使用与其他所有路由操作一样。配置参数精度与性能的调优旋钮启动 Meili 服务或实例化MapMatcherFactory都需要传入 Valhalla 配置文件Meili 的全部配置集中在配置文件的meili节点下当前仓库中可在 test/bindings/valhalla.json 等测试配置中找到meili节点的真实形态。所有交通模式节点auto、pedestrian、bicycle、multimodal都可以持有各自的参数设置否则使用default节点中的设置。地图匹配参数下表列出各交通模式可配置的参数说明以 configuration.md 为基础默认值同时对照当前仓库 valhalla/meili/config.h 源码存在差异处以源码为准参数说明文档默认值源码默认值当前仓库sigma_z非负值指定输入 GPS 序列的精度正态分布的方差也用于加权测量的发射成本4.074.07EmissionCost::sigma_zbeta非负经验值用于加权两个连续候选之间的转移成本33TransitionCost::betamax_route_distance_factor非负值限制路由搜索范围距离到下一测量点的距离 × 该因子55TransitionCost::max_route_distance_factormax_route_time_factor非负值限制路由搜索范围时间到下一测量点的时间 × 该因子55TransitionCost::max_route_time_factorbreakage_distance非负值米若两个连续测量点相距超过该距离则不考虑两者之间的连通性20002000TransitionCost::breakage_distance_metersinterpolation_distance若两个连续测量点距离小于该值则后一点被插值进匹配路线1010Routing::interpolation_distance_meterssearch_radius非负值米为每个测量点搜索道路候选的半径5050CandidateSearch::search_radius_metersmax_search_radius指定search_radius的上界100200CandidateSearch::max_search_radius_meters为 GPS 点与对应路线点最大允许差值turn_penalty_factor非负值惩罚从一条路段转向下一条路段的转弯0200TransitionCost::turn_penalty_factor按转弯角度确定转弯成本从源码注释还可以看到一些文档表格之外但对调优很有价值的信息CandidateSearch::cache_size默认 100240控制候选查询的空间索引缓存大小grid_size默认 500控制路网网格划分的粗细两者直接影响内存占用与候选查询吞吐EmissionCost::gps_accuracy_meters默认 5表示 GPS 测量默认精度用于确定最大搜索半径每个参数都配有is_xxx_customizable开关如is_search_radius_customizable默认true、is_breakage_distance_customizable默认false、is_turn_penalty_factor_customizable默认true决定该参数是否允许被用户请求中的 URL 查询参数覆盖——这与下面的服务参数customizable密切相关。注意由于 configuration.md 文档与当前源码在turn_penalty_factor、max_search_radius两个默认值上存在出入实际部署时请以当前仓库 valhalla/meili/config.h 与valhalla_build_config生成的真实配置为准。服务参数以下参数仅在 Meili 服务HTTP 接口中使用参数说明默认值mode指定默认交通模式multimodalcustomizable指定允许通过 URL 查询参数自定义的参数[mode, search_radius]verbose控制调试用的详细输出false各参数对精度与性能的影响结合 HMM 模型详见下节可以给出调优方向sigma_z与发射成本它对应发射概率中高斯分布的方差直接决定候选离测量点越近越可能被选的权重。GPS 精度越差该值应越大beta与转移成本它对应转移概率中经验指数分布的参数决定路线距离与测量点间大圆距离的差值在多大程度上惩罚一条转移。beta越小转移成本对距离差越敏感search_radius/max_search_radius控制每个点的候选数量。半径过小可能漏掉真实候选过大则显著增加候选数并放大 Viterbi 的路由排列组合拖慢匹配过程文档明确指出当 GPS 精度未知时过大的search_radius可能拖慢匹配过小则可能漏掉候选interpolation_distance控制高密度轨迹的抽稀程度。更大的插值距离能减少参与匹配的点数、提升吞吐并规避静止/低速抖动导致的错误 U-turn 推断max_route_distance_factor/max_route_time_factor/breakage_distance限制两个候选之间路由搜索的代价上限超限即视为不连续从而控制最坏情况下的计算量turn_penalty_factor按转弯角度累加转弯成本作为转移成本的独立组成部分见 implementation-details.md 中 Routing 一节路径查找过程中会聚合路段间的转弯成本用于惩罚带转弯的路径对auto、bicycle等模式尤其重要。核心原理HMM 图形模型与算法演进图形模型一个有向无环图DAG把上面的例子放进图形模型见 algorithms.md每个测量点对应一列节点图中的一个节点HMM 中的隐状态代表一个候选——即元组(road segment, offset)指明地图上某路段的一个位置。边(u, v)表示节点u能够影响关于v的决策。以边(node 9, node 12)为例因为从 node 9 到 node 12 实际走的路远比看起来长所以 node 12 不太可能是最后一个测量点的匹配。一个测量点只受其前一个测量点影响整个图是一个有向无环图DAG在 HMM 语境下也称为 trellis 图。两个概率模型共同量化某测量点匹配某节点的可能性发射概率emission probability节点离测量点越近测量点越可能匹配它转移概率transition probability从u步行到v的路线距离越接近测量点间的距离v的测量点越可能匹配u的测量点之后。用伪代码表达# 高斯分布 def emission_prob(u): c 1 / (SIGMA_Z * math.sqrt(2 * math.pi)) return c * math.exp(-great_circle_distance(u.measurement, u)**2) # 经验分布 def transition_prob(u, v): c 1 / BETA # 计算路线距离代价高昂后续会讨论如何减少该函数的调用次数 delta math.abs(route_distance(u, v) - great_circle_distance(u.measurement, v.measurement)) return c * math.exp(-delta)一条路径是若干边的列表路径概率定义为def path_prob(path): assert path u, v path[0] joint_prob emission_prob(u) for u, v in path: joint_prob * transition_prob(u, v) * emission_prob(v) return joint_prob任务是寻找所有可能序列中概率最大的序列。为方便起见图中加入两个虚拟节点——源节点s与目标节点t以及对应的虚拟边所有发射、转移概率均为 1.0于是任务变成找一条从s到t的、使路径概率最大的路径。朴素解法枚举所有路径暴力解法是枚举源与目标之间的所有路径并选最优def maximum_path_prob(adjacency_list, s, t): return max((path_prob(path), path) for path in all_paths(adjacency_list, s, t), keylambda prob, path: prob) # 递归生成从 s 到 t 的所有路径 def all_paths(adjacency_list, s, t): if s t: return [[]] paths [] for v in adjacency_list[s]: for path in all_paths(adjacency_list, v, t): paths.append([(s, v)] path) return pathsViterbi 算法按层展开的动态规划Viterbi 算法通常用于在 HMM 中寻找最可能序列。在 DAG 上它像广度优先搜索BFS一样逐层level by level搜索。搜索/展开过程中Viterbi 算法记住每个节点的最优解从源节点出发的最优路径及其路径概率并据此求下一层的最优解def viterbi_search(adjacency_list, s, t): # 初始化每个节点的联合概率 joint_prob {} for u in adjacency_list: joint_prob[u] 0 predecessor {} queue FIFOQueue() queue.push(s) joint_prob[s] emission_prob(s) predecessor[s] None while not queue.empty(): # 取出节点 u u queue.pop() # 保证 u 的最优解已找到 assert joint_prob[u] maximum_path_prob(adjacency_list, s, u)[0] if u t: break for v in adjacency_list[u]: # 松弛操作 new_prob joint_prob[u] * transition_prob(u, v) * emission_prob(v) if joint_prob[v] new_prob: joint_prob[v] new_prob predecessor[v] u if v not in queue: queue.push(v) return joint_prob[t], construct_path(predecessor, s, t)为什么需要惰性降低转移概率计算次数Viterbi 与基于 DAG 的拓扑排序都能求最优路径但两者都必须探索所有边。而在地图匹配模型中探索一条边是昂贵的——展开边(u, v)时为了计算转移概率需要在路网中求u到v的最短路径。假设有S个测量点、每个测量点平均T个状态Viterbi 或拓扑排序需要遍历所有边即做S * T * T次最短路径计算。这在密集城区平均T很大非常糟糕。为减少转移概率计算次数Meili 使用Dijkstra 算法来尽可能避免提取那些不太可能的节点。与 Viterbi 一样Dijkstra 以动态规划方式求解但它的优势是贪心地每次提取最可能的节点借助这一策略一旦目标被提取最优解即已保证找到其余节点可以安全丢弃。应用 Dijkstra 前需要把最大化问题转换为最小化问题。推导如下T transition_prob E emission_prob lg math.log10 assert 0 E(u) 1.0 and 0 T(u, v) 1.0最大化path_prob(path)等价于product(E(u) * T(u, v) for u,v in path)等价于最大化利用lg(a*b) lg(a) lg(b)sum(lg(E(u)) lg(T(u, v)) for u,v in path)等价于最小化sum(-lg(E(u)) -lg(T(u, v)) for u,v in path) # 必须非负 assert 0 -lg(E(u)) and 0 -lg(T(u, v))经过转换节点的发射概率变成节点成本node cost边的转移概率变成边成本edge costdef node_cost(u): return -1 * math.log10(emission_prob(u)) def edge_cost(u, v): return -1 * math.log10(transition_prob(u, v))问题变成找一条从s到t的、最小化sum(node_cost(u) edge_cost(u, v) for u, v in path)的路径——这正是 Dijkstra 能高效求解的形态。由于与 Viterbi 相似只需把viterbi_search中的 FIFO 队列换成优先队列、把概率计算换成成本计算就能得到一个贪心、惰性但更快的 Viterbi 算法版本。Viterbi Search 与 Routing 的分工implementation-details.md 特别对比了 Viterbi Search 与 Routing 两个模块两者都在寻找最优路径但目标不同前者找最可能序列后者找最短距离路径两者都基于 Dijkstra 算法但图形模型不同前者在trellis 图上工作后者在路网上工作Routing 模块valhalla/meili/routing.h基于 AStar从单一源点路由到多个目标点——因为目标集合恰是候选查询为测量点提供的候选簇算法可以直接瞄准测量点位置估计启发式成本它不直接构造路径而是把搜索树LabelSet返回给源状态供后续路径构建使用与 Thor 中的路径算法不同Routing 扫描的是节点而非边因此这里不处理转弯限制turn restriction。MapMatching类valhalla/meili/map_matching.h是 HMM 地图匹配算法的核心组件输入候选簇序列从每个簇中选出一个候选组成最可能的候选序列Viterbi 路径。它把实际搜索委托给 Viterbi Search 模块但自己定义似然度的量化方式——继承ViterbiSearch并实现TransitionCost与EmissionCost。文档同时指出你可以像MapMatching一样继承任一实现并实现这两个虚成本函数从而基于其他路网数据源如 pgRouting开发自己的地图匹配算法。库 API 与 MatchResult 关键字段Meili 的库 API详见 library-api.md目前仍标注为测试中、可能随时变更。核心对象如下Measurementvalhalla/meili/measurement.h从 GPS 设备读到的测量点通常带噪声需要匹配可附加精度accuracy与搜索半径search radius等属性提升匹配效果#include valhalla/meili/measurement.h using namespace valhalla; // 构造函数 const midgard::PointLL lnglat(13.44, 53.67); // 从 GPS 设备读到的带噪声位置 float gps_accuracy 4.07, // GPS 精度米 search_radius 30; // 在该半径米范围内搜索道路候选 meili::Measurement(lnglat, gps_accuracy, search_radius);MapMatcherFactoryvalhalla/meili/map_matcher_factory.h为指定交通模式生产MapMatcher同时管理所有 matcher 共享的内存数据结构如瓦片。建议只实例化一次并保持到其所有 matcher 销毁之后传入非法配置会抛出std::invalid_argument。工厂还维护一个图瓦片读取器与一个候选查询实例并在所有 matcher 间共享因此从工厂创建 matcher 很廉价——但注意工厂与 matcher 都不是线程安全的。MapMatchervalhalla/meili/map_matcher.h负责把序列匹配到路网。离线匹配一个序列std::vectorMatchResult meili::MapMatcher::OfflineMatch(const std::vectorMeasurement sequence);它返回与Measurement序列一一对应的MatchResult序列。MatchResultvalhalla/meili/match_result.h包含匹配/插值到的路段、匹配位置、到该位置的距离等若该测量点是匹配而非插值得到的结果上会附有对应的状态 ID由于路由搜索树已存储在各状态中可通过该 ID 找到状态并用 valhalla/meili/match_route.h 中的辅助函数重建路线。主要字段// 匹配后的坐标 const valhalla::midgard::PointLL meili::MatchResult::lnglat(); // 从测量点到匹配坐标的距离 float meili::MatchResult::distance(); // GraphId在 Valhalla 瓦片数据中标识边和节点 valhalla::baldr::GraphId meili::MatchResult::edgeid();服务 APIHTTP 调用实践Meili 服务 API详见 service-api.md同样标注为测试中接受POST请求体中的 GeoJSON 要素或几何MultiPoint或LineString类型。URL 参数参数说明默认值mode序列的交通模式可选auto、bicycle、pedestrian、multimodalmultimodalsearch_radius数值范围[0, 100]指定为每个测量点搜索道路候选的半径米40指定交通模式可以限制可匹配的道路类型如auto只考虑可行驶道路从而提升匹配精度与速度模式未知时使用默认的multimodal即考虑所有道路类型。响应为 GeoJSONMultiLineString要素匹配坐标保存在属性matched_coordinates的 JSON 数组中若某测量点未匹配到任何道路对应匹配坐标为null。示例请求curl -X POST https://localhost:8002?search_radius35modeauto示例请求体{ coordinates: [ [ 13.288925, 52.438512 ], [ 13.288938, 52.438938 ], [ 13.288904, 52.439169 ], [ 13.288821, 52.439398 ], [ 13.288824, 52.439491 ], [ 13.288824, 52.439563 ] ] }示例响应{ status: 200, message: OK, data: { type: Feature, geometry: { type: MultiLineString, coordinates: [ [ [ 13.288884, 52.438507 ], [ 13.288852, 52.438835 ], [ 13.288844, 52.439090 ], [ 13.288825, 52.439136 ], [ 13.288805, 52.439159 ], [ 13.288601, 52.439365 ], [ 13.288538, 52.439384 ], [ 13.288719, 52.439636 ] ] ] }, properties: { matched_coordinates: [ [ 13.288884, 52.438507 ], [ 13.288848, 52.438934 ], [ 13.288805, 52.439159 ], [ 13.288601, 52.439365 ], [ 13.288685, 52.439590 ], [ 13.288719, 52.439640 ] ] } } }可以看到响应中的matched_coordinates是每个测量点吸附到路网后的位置与输入坐标一一对应且均已被拉到道路上这正是FindMatchResults产出的MatchResult元数据在服务层的最终呈现。相关文档与源码导航如果你想继续深入以下是本主题相关的仓库路径架构文档主文档 Meili 架构配套的算法视角、实现细节、配置说明、库 API 与服务 API源码实现src/meili/map_matcher.cc、src/meili/match_route.cc、src/meili/candidate_search.cc头文件与数据结构valhalla/meili/ 下的map_matcher.h、map_matcher_factory.h、match_result.h、match_route.h、measurement.h、routing.h、state.h、stateid.h、viterbi_search.h、config.h测试配置示例meili配置节点的实际形态可见于 test/bindings/valhalla.json地图匹配相关测试覆盖见 test/gurka 与 test/ 下如mapmatch.cc、viterbi_search.cc等用例例如 test/viterbi_search.cc。赞分享后端【免费下载链接】valhallaOpen Source Routing Engine for OpenStreetMap项目地址https://gitcode.com/gh_mirrors/va/valhalla点击查看免费下载相关推荐tiny11builder用 PowerShell 把 Windows 11 镜像做成精简 ISOtiny11builder用 PowerShell 把 Windows 11 镜像做成精简 ISO 旧笔记本装完原版 Win11C 盘先被 Clipcham后端Valhalla Meili 地图匹配算法解析从 HMM 建模到 Viterbi 与 Dijkstra 求解Valhalla Meili 地图匹配算法解析从 HMM 建模到 Viterbi 与 Dijkstra 求解 本文以 Valhalla 仓库中 Meili 架后端numpy-ml 隐马尔可夫模型HMM完整指南MultinomialHMM 的前向-后向、Viterbi 与 Baum-Welch 实现numpy ml 隐马尔可夫模型HMM完整指南MultinomialHMM 的前向 后向、Viterbi 与 Baum Welch 实现 numpy ml机器学习人工智能上一篇5分钟快速部署Whisper-WebUI打造专业级语音转字幕平台下一篇VisualCppRedist AIO一站式解决Windows运行库依赖的终极指南 创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考