空间与地图表示：栅格地图、拓扑地图、几何特征地图的构建与对比
做机器人路径规划这么多年，我越来越觉得一个道理：地图选不对，算法全白费。
你想想看，机器人要导航，首先得知道自己在哪里，周围长什么样。这个「长什么样」就是地图。但地图不是照片，它得是计算机能理解的数据结构。说白了，我们得把物理世界翻译成机器能读懂的数学语言。
今天我就带你看看三种最经典的地图表示方式。每种我都踩过坑，也都有心得。
核心观点：没有最好的地图，只有最合适的。场景决定选择。
1. 栅格地图（Occupancy Grid Map）
这是最直观的一种。把空间切成一个个小格子，每个格子要么是障碍物，要么是空地，要么是未知。
我记得第一次做扫地机器人项目时，用的就是栅格地图。当时觉得这玩意儿太简单了，不就是个二维数组嘛。结果真跑起来才发现——内存爆炸。
为什么？因为你要覆盖一个100平米的房间，如果精度是1cm，那就是10000×10000个格子。每个格子存一个浮点数表示占用概率，算下来就是400MB。一个嵌入式设备哪扛得住？
后来我学乖了，用分层栅格。远的地方用粗粒度，近的地方用细粒度。嗯，这招挺管用。
构建方法
栅格地图的构建核心是贝叶斯更新。每次激光雷达扫到一帧数据，我们就更新每个格子的占用概率。
# 伪代码：栅格地图更新
def update_grid(grid, laser_scan, robot_pose):
for each_cell in grid:
# 计算该格子是否在激光束路径上
if cell_is_on_beam(laser_scan, robot_pose, each_cell):
# 增加占用概率
grid[each_cell] = log_odds_update(grid[each_cell], occupied=True)
elif cell_is_beyond_beam(laser_scan, robot_pose, each_cell):
# 增加空闲概率
grid[each_cell] = log_odds_update(grid[each_cell], occupied=False)
return grid这里有个坑：激光束的建模。你不能简单地把激光打到的那一点标记为障碍物，沿途的格子标记为空。因为激光有噪声，而且物体边缘会有反射问题。我建议用射线追踪法（Bresenham算法）来遍历光束路径，这样效率高很多。
我的经验：栅格地图的分辨率不要一味追求高。室内导航5cm就够了，室外20cm也凑合。分辨率翻倍，内存翻4倍，计算量翻4倍。不值当。
优缺点
| 优点 | 缺点 |
|---|---|
| 构建简单，直接对应传感器数据 | 内存消耗大，尤其在大场景下 |
| 适合路径规划（A*、Dijkstra直接可用） | 缺乏语义信息，不知道墙和桌子的区别 |
| 支持多传感器融合 | 精度受限于分辨率 |
| 概率表示，鲁棒性好 | 动态物体处理困难 |
2. 拓扑地图（Topological Map）
拓扑地图就不一样了。它不关心具体的几何尺寸，只关心连通关系。说白了，就是一张图（Graph），节点是地点，边是路径。
我做过一个仓储机器人项目，仓库有几千平米。如果用栅格地图，光存地图就得几百MB。但用拓扑地图，整个仓库就几十个节点——货架区、打包区、充电站、出入口。路径规划就是图搜索，快得飞起。
但拓扑地图有个致命问题：怎么自动构建？
你不能手动标节点吧？那也太傻了。常用的方法是基于Voronoi图或基于关键帧的拓扑提取。
构建方法：基于Voronoi图
先建一个栅格地图，然后提取Voronoi图。Voronoi图的边就是那些离所有障碍物最远的点连成的线。这些线天然就是安全的路径。
# 伪代码：从栅格地图提取拓扑图
def extract_topology(grid_map):
# 1. 计算距离变换
distance_map = compute_distance_transform(grid_map)
# 2. 提取Voronoi图（局部最大值）
voronoi_edges = extract_voronoi(distance_map)
# 3. 提取节点（分支点、端点）
nodes = extract_nodes(voronoi_edges)
# 4. 构建图
graph = build_graph(nodes, voronoi_edges)
return graph我曾经踩过的坑：Voronoi图在狭窄通道里会生成很多细碎的分支。后来我加了剪枝步骤，把长度小于阈值的分支去掉，图就干净多了。
优缺点
| 优点 | 缺点 |
|---|---|
| 内存占用极小，适合大规模场景 | 缺乏几何细节，无法精确定位 |
| 路径规划速度快（图搜索） | 自动构建困难，依赖底层地图 |
| 支持分层表示 | 对动态环境适应性差 |
| 符合人类认知（路口、走廊） | 节点定义不唯一 |
3. 几何特征地图（Geometric Feature Map）
几何特征地图，说白了就是提取环境中的几何基元——直线、圆弧、角点、平面。它不像栅格地图那样存每个点，而是存这些特征的参数。
我记得做AGV（自动导引车）项目时，工厂地面有反光，激光雷达经常打飞。栅格地图里全是噪点，根本没法用。后来换成几何特征地图，只提取墙面直线，反而稳得很。
为什么？因为几何特征有结构化信息。一条直线由两个参数（ρ, θ）决定，比存几百个点鲁棒多了。
构建方法：直线提取
最经典的是Split-and-Merge算法。把激光点云递归地分割成线段，直到每段都满足直线拟合误差。
# 伪代码：Split-and-Merge直线提取
def split_and_merge(points, threshold):
if len(points) < 2:
return []
# 1. 拟合直线
line = fit_line(points)
# 2. 找最大误差点
max_error, max_idx = find_max_error(points, line)
if max_error < threshold:
# 误差可接受，返回这条直线
return [line]
else:
# 误差太大，在最大误差点处分割
left_segment = points[:max_idx+1]
right_segment = points[max_idx:]
left_lines = split_and_merge(left_segment, threshold)
right_lines = split_and_merge(right_segment, threshold)
return left_lines + right_lines我的建议：阈值不要设得太小，否则会提取出很多短线段。我一般设0.05m到0.1m之间。另外，合并步骤也很重要——把共线的相邻线段合并，能减少特征数量。
优缺点
| 优点 | 缺点 |
|---|---|
| 数据压缩率高，一条直线代替几百个点 | 只适用于结构化环境（室内、工厂） |
| 对传感器噪声鲁棒 | 自然场景（树林、山地）很难提取几何特征 |
| 支持数据关联（回环检测） | 构建算法相对复杂 |
| 适合与IMU融合 | 特征匹配容易陷入局部最优 |
4. 三种地图的对比与选择
说了这么多，到底怎么选？我画了一张图帮你理清思路。
我个人的选择逻辑是这样的：
- 小场景（<1000㎡）：栅格地图。简单直接，A*一跑就出路径。
- 大场景（>10000㎡）：拓扑地图。内存是关键瓶颈。
- 结构化环境：几何特征地图。鲁棒性最好。
- 混合使用：实际项目中，我经常把三种地图结合起来。底层用栅格做定位，上层用拓扑做全局规划，中间用几何特征做回环检测。
一句话总结：栅格地图是「是什么」，拓扑地图是「怎么连」，几何特征地图是「长什么样」。三者互补，缺一不可。
好了，关于空间与地图表示，我就讲这么多。每种地图都有它的脾气，选对了事半功倍，选错了寸步难行。你在实际项目中遇到什么问题，欢迎来交流。
公众号:蓝海资料掘金营，微信deep3321