简介：这套MATLAB源码实现了经典的牛耕式（Boustrophedon）栅格分区方法，面向需要进行全覆盖路径规划、栅格地图划分或逐像素图像处理的算法学习者与开发者，帮助解决二维空间中有序遍历与分区效率问题。资源包共9个文件，包含6个.m脚本和3张.png示意图，压缩后仅11KB，结构轻量，便于阅读与二次修改；脚本覆盖主流程、代价计算、启发函数等核心模块，图示则用于观察边界与角落处理效果。已有1751人学习下载，说明该实现具备一定参考价值。通过两套可运行主程序和多个子函数，可快速复现牛耕式路径生成与栅格遍历过程，并在此基础上调整区域大小、起点位置和遍历规则，适合作为课程设计或全覆盖算法研究的起步模板。 我第一次被 boustrophedon 这个词绕晕，是在一个扫地机器人项目的方案评审上。同事说“栅格地图上直接做牛耕分区就行”，我下意识以为要写什么高级的图搜索算法，后来才明白，他指的是让机器人像老黄牛耕地一样，一行到头、掉头、挨着犁下一行。这个词源自古希腊语“牛转弯”，放到路径规划里，就是全覆盖路径规划中最基础也最经得起实战检验的一种策略。
这项技术解决的问题很明确：如何让一台机器人把已知区域不漏地走完，同时尽量少走重复路线。扫地机器人、植保无人机、洗地车、光伏板清洁机器人，底层几乎都离不开它。如果你手里的输入不是精确的几何多边形，而是一张激光SLAM或者视觉重建出来的栅格地图，那你大概率需要自己实现一次牛耕式分区。这篇文章我会把“栅格图上的牛耕式分区”从原理讲到实现细节，再讲讲我实际调参时踩过的坑。
1. 为什么叫“牛耕式”：从黄牛犁地到栅格覆盖
1.1 “直线走完再掉头”是覆盖效率的底线
先直接说结论：在很多覆盖任务里，反复走平行直线看似很“笨”，却是统计上最经济的基础运动方式。原因很简单——路径规划里，机器人的代价通常分为两部分：沿直线行走的代价和转弯代价。直线段上传感器稳定、位姿估计误差积累慢、能耗也相对可控；而转弯阶段需要减速、转向、再加速，时间成本往往是直线段的数倍。扫地机器人弓字形清扫，本质就是每趟少转弯、多走直线，把转弯次数压到理论下限。
牛耕式轨迹还有一个统计层面的优势：如果扫描线间距固定，且机器人有效作业宽度稳定，覆盖一条“垄”后只平移一个作业宽度，那么相邻路径之间几乎不会出现间隙，也不会叠加太多重复。这一点在没有精确传感器的情况下尤其重要，因为你不需要闭环修正就能得到一条分布均匀的路径。
1.2 为什么一定要“分区”
如果只是在一个没有障碍物的矩形房间做牛耕扫描，那确实不需要分区。但真实环境里总有桌子、墙垛、柜子横在扫描线中间。如果不做处理直接让机器人沿着扫描线走，它会在障碍物面前停下，要么掉头、要么绕行。掉头会漏掉障碍物后面的区域；绕行则会打乱“一行接一行”的节奏，导致后续扫描线错位，甚至出现大面积漏覆盖。
所以全覆盖规划的第一步往往不是画轨迹，而是“把让扫描线无法一次穿过的区域切开，切成若干个可以直接扫描的单元”。每个单元内部近似竖直或者近似凸，机器人在单元内部做牛耕扫描时，不需要为躲避障碍物额外改变运动方向。跨单元的移动则单独处理，用“连接”的方式把单元串起来。几何方法里的梯形分解、牛耕分解就是干这个的，栅格版实现的核心逻辑也一样，只是把几何上的“关键点”换成了栅格上的“关键列”。
1.3 栅格图为什么比几何图更好落
纯粹从精度角度，几何分解更漂亮：提取多边形顶点、计算交线、合并单元，结果是一条贴着实际边界的路径。但做工程的人都明白，从激光SLAM地图里提取稳定可靠的几何多边形，本身就是另一场战斗。地图噪声、墙体的轻微倾斜、动态物体的残留，都会让顶点提取不稳定。而栅格地图本身就是一个标了自由/占据的离散网格，把分区算法写成“统计列上连续自由区间”的循环，比维护几何图结构简单得多，对噪声也更鲁棒。
当然，栅格法牺牲了一点精度，但绝大多数机器人的运动步长和传感器误差远大于栅格尺寸，这点损失完全在可接受范围内。我在实际项目中，基本都采用“先拿到占据栅格地图，再做形态学处理，然后直接栅格化分区”的路线，跑起来省心得多。
2. 栅格分区的基本逻辑：关键列在哪里划分
2.1 扫描线“穿墙而过”时的区间变化
分区判据可以用一句话概括：让一条扫描线沿地图从左往右移动，观察它与自由空间交出的线段数量。数量发生变化的位置，往往对应障碍物的“凸起”或“凹下”，那里就是需要切开的地方。
举个生活化的例子：把房间想象成很多竖直的细条。没有柜子时，每条竖条里“可站立区域”是一整段；竖条移到柜子旁边时，可站立区域被柜子截成两段，分段数从1变成了2。这个变化说明地图的连通结构在这里发生突变，如果还按原来的整体做一行扫到底，机器人一定会被柜子挡住。因此在“1变2”的位置切开，把地图拆成左右两个独立区域，每个区域内再做牛耕扫描，就能避开障碍物。
2.2 栅格实现：统计每一列的自由区间
网格化之后，这个判据实现起来非常直白。按列遍历地图，对每一列做一次“连续自由区间”统计，然后比较相邻列的区间数和区间端点位置。区间数量变化，或者某个区间整体发生明显平移，都可以视为关键列的候选。
def free_intervals_in_column(grid, col): intervals = [] rows = grid.shape[0] r = 0 while r < rows: if grid[r, col] == 0: # 0表示自由栅格 start = r while r < rows and grid[r, col] == 0: r += 1 intervals.append((start, r - 1)) else: r += 1 return intervals def find_split_columns(grid): splits = [] prev = free_intervals_in_column(grid, 0) for col in range(1, grid.shape[1]): cur = free_intervals_in_column(grid, col) if changed(prev, cur): splits.append(col) prev = cur return splits这里的 changed 函数不只要比较区间数量，还要考虑“同一区间端点出现剧烈平移”的情况。比如障碍物比较斜时，某列自由区间的端点会连续好几列缓慢移动，这种不算突变；但如果端点一列之间跳了几十个栅格，说明可能有凹角出现，需要检查是否需要细分。
2.3 分区的边界到底取哪一列
确定关键列之后，分割线不能直接压在障碍物所在的列上。比较稳妥的做法是把分割线放在关键列和前一列之间的空隙上。例如第 k 列自由区间数量比第 k-1 列多了一个，说明障碍物在 k 列附近“长出来”，分割线就放在第 k-1 列与第 k 列之间；如果区间数量减少了，说明障碍物接近结束，同样把分割线放在 k-1 与 k 之间。这样左右两个子区域都不会包含被占据栅格，后续扫进去更安全。
用递归的方式可以继续对左右子区域重复这个过程，直到每个子区域内任意一列的自由区间数量都不再变化。这本质上就是牛耕分解在栅格上的递归实现。需要注意，递归时扫描方向可以保持同一方向，也可以每层换一个方向，后者对应更广义的 boustrophedon decomposition，能进一步减少小碎块的产生。
2.4 三种常见特殊边界
第一，障碍物贴着地图边界。此时自由区间数量虽然变化，但被切掉的部分可能非常窄，没必要生成一个独立单元，可以设置最小宽度阈值，过窄的区域直接和相邻区域合并。第二，斜墙会带来锯齿状的关键列序列，隔几列就“跳变”一次，如果每次都切，会把地图切成大量碎条。我在实践里一般要求“关键列连续出现至少两列”才真正切开，能滤掉大部分斜墙造成的抖动。第三，环形障碍物中间有空洞，栅格图上会出现“自由-占据-自由-占据-自由”的结构，简单区间计数无法处理这种多连通区域，需要结合连通域标记，把障碍物的内外边界都识别出来，否则分区会失效。
3. 单元生成之后：往复轨迹与连接顺序怎么定
3.1 单元内部的牛耕轨迹生成
分区完成后，每个单元可以看成一个近似竖直条带。接下来就是单元内部的牛耕轨迹了。把单元的左边界、右边界、顶部、底部提取出来，按设定的扫描间距生成水平扫描线。每条扫描线从单元一侧边界走到另一侧，下一行方向相反。扫描间距一般取机器人底盘有效作业宽度，也就是毛刷、割幅或者喷幅的实际宽度，而不是机器人本体宽度。
def zigzag_cell(cell_left, cell_right, cell_top, cell_bottom, step): path = [] y = cell_top direction = 1 while y <= cell_bottom: if direction == 1: path.append((cell_left, y)) path.append((cell_right, y)) else: path.append((cell_right, y)) path.append((cell_left, y)) y += step direction *= -1 return path这里有个细节：扫描方向不要固定为水平或竖直，而应该选择“沿着单元长边”的方向。比如单元是一个竖直长条，那就水平扫描；如果是一个水平长条，就竖直扫描。原因是长边方向走一趟更长，转弯次数更少，整体效率更高。如果单元内部还有局部凸起，可以先把这部分剔除到相邻单元，尽可能保证单元的近似矩形，这样生成的牛耕线才整齐。
3.2 单元之间的连接顺序不能乱排
每个单元都有一条进入路径和一条离开路径。机器人覆盖完一个单元后，要移动到下一个单元，这一段“空驶路径”不产生覆盖收益，但它会直接拉低整体效率。最简单的做法是按分区顺序依次访问，但这往往不是最短路线，因为分区顺序取决于扫描线的移动方向，和物理位置关系不一定一致。
真正落地时，我会把每个单元看成一个节点，单元之间的转移代价用两个单元入口点的欧氏距离近似，然后做一次最近邻贪心排序：从当前单元出发，找最近的未访问单元作为下一个目标。对于几十个单元的场景，贪心已经足够好；如果单元数量上百，可以用最小生成树或者2-opt做一轮改进。实测下来，单靠一个最近邻排序，空驶距离通常能减少15%以上，代码量却只有十几行。
3.3 一个最小示例演算
拿一张很直观的地图举例：地图中间靠上有一个大障碍物，把地图切成了三个单元，左单元A、右上单元B、右下单元C。A在最左，B在右上，C在右下，整体呈“L”形。如果分区算法先切出A，再往上切出B，最后往下切出C，按A→B→C的顺序覆盖，机器人从B到C需要斜穿地图下方一段较长的空驶；但如果改成A→C→B，虽然覆盖单元的顺序变了，C和A在上方共享一条边界，连接距离短得多，空驶里程能省掉大约四成。这说明单元本身怎么划分重要，访问顺序同样重要。
4. 实现牛耕式分区时最容易被忽略的参数与坑
4.1 栅格分辨率：不是越细越好
栅格分辨率是整个算法最关键的参数之一。太粗，窄通道会被直接抹掉，关键列的跳变信息丢失，分区结果完全失真；太细，整张地图的栅格数量爆炸，算法变慢，而且单个噪点就会变成一个“伪通道”，产生大量碎单元。我的经验值是“机器人有效宽度的一半到三分之一”作为栅格边长。比如一台直径40cm的扫地机器人，栅格尺寸取10cm到20cm比较合适。这个尺度既保留通道细节，又不会把噪声放大。
4.2 关键列检测的“假分裂”怎么压
实际SLAM地图里总有噪点，尤其在墙角附近，传感器数据容易抖动，栅格图上会冒出一个孤立的占据点。如果完全按区间数突变来切，这里就会生成一个宽度才一两格的“假单元”，路径规划进去根本转不开身，还会增加大量无谓的掉头。
我在做关键列检测时，加了两个约束：一是设定最小连续异常列数，只出现一列的变化直接忽略；二是先对栅格地图做一次形态学开运算，去掉孤立噪点再做分区。这两个约束加完，假分裂基本消失。仔细想原因也不复杂：真实障碍物的边界变化通常是连续出现的，而噪点只影响单列，用连续列约束天然能把二者分开。
4.3 覆盖率为什么总是达不到100%
这是统计口径的问题。很多人直接按路径点画线，数一下“路径穿过的栅格”除以“自由栅格”就算出覆盖率，结果算出来很高，实际跑起来却发现墙角、边缘根本没扫干净。原因是机器人本体有宽度，轨迹是一条有宽度的带子，而不是一条无宽度的线。
正确的统计方式是：把轨迹离散成密集点序列，每个点按机器人半径做膨胀，标记所有被膨胀圆覆盖的栅格，再与自由栅格做交集。离散点的间距至少要小于栅格尺寸的一半，否则会有漏标。做完这一步你会发现，覆盖率很少能到100%，能到95%以上已经是很不错的覆盖率，剩下的往往是防撞膨胀区导致的物理不可达区域。
4.4 转角处理与就地旋转空间
栅格规划阶段很容易忽略真实底盘的转向半径。栅格图上看两个单元边界相距两格，机器人实际转向、掉头需要的空间可能远大于这个距离。我曾在调试时遇到一个问题：分区算法正常生成了一条贴着单元边界的转折线，但小车到边缘后无法原地掉头，因为边缘刚好是一堵墙，没有留下转向余量。后来我在每个分区边界处向内部收缩一个机器人半径，把转折点从物理边界上“拉”回一点，才算真正跑通。这个处理看似损失了边缘一丁点覆盖面积，换来的却是现场稳定性和设备安全性。
5. 牛耕式分区之外的延伸：排序、动态环境与工程心得
5.1 用全局信息优化单元访问顺序
前面提到过基于最近邻贪心的单元排序，这里再补充一个更实用的变体：不要只按单元入口的欧氏距离做贪心，而要按“当前机器人所在位置到该单元入口的距离 + 该单元内部估计覆盖时间”共同排序。内部覆盖时间可以粗略用单元面积除以作业宽度得出。这样排序能避免一种尴尬情况——选了一个入口很近但面积很大的单元先做，导致后面几个小单元之间的连接全部绕路。用面积加权之后，整体空驶和转弯次数都能兼顾。
5.2 环境局部变化时尽量复用原分区
动态场景中，地图里会临时出现椅子、箱子、行人。如果每次环境一变就重新全局分区，机器人会不断改变覆盖策略，看着很“聪明”，实际效率很低，甚至可能来回抖动。更工程的做法是：只有当障碍物变化区域影响了某个单元的关键列时，才把这个单元标记为失效，仅对失效单元重新做一次牛耕分区和排序，其余单元维持原有分区结果。这样既保证了覆盖，又不让全局路径剧烈跳变。
我试过在测试场地摆放临时路障，用这种局部重规划方案，机器人绕开路障后仍然能回到原来的牛耕线上继续干活，整体覆盖率没有明显下降，处理耗时也远低于全局重规划。
5.3 做项目的一点心得
牛耕式分区这套算法的价值，不在于它多么“高级”，而在于它用极少的计算量解决了一个非常清晰的问题：先让地图结构变得适合扫描，再按一种低转弯次数的模式把区域覆盖完。真正让工程落地变难的，往往不是算法本身，而是地图质量和设备约束。地图有脏点、栅格分辨率选错、转向空间不足，这些问题都会让同一个算法出现天差地别的表现。先把地图预处理做干净，把分辨率校准到和机器人尺寸匹配，再回头调分区和排序，你会发现牛耕式分区其实出奇地可靠。
本文还有配套的精品资源，点击获取
