【覆盖搜索】牛耕法覆盖搜索

做项目的时候用到了牛耕法做覆盖搜索，这里简单学习一下

问题背景

任务

我们需要探讨的是这样一个问题背景：

1. 首先我们具有一个待搜索的目标区域，这个区域通常是多变形的，可凸可凹；
2. 区域内有一些多变形的障碍物，同样可凸可凹；
3. 搜索区域的智能体（无人机、智能车、扫地机器人之类的）的搜索范围远小于区域面积；
4. 搜索起点位于待搜索区域的边界上，或可通过一定的规划算法使智能体到达区域边上。

我们的任务是：生成一系列的路径，使得智能体可以完成对于待搜索区的覆盖搜索。

难点

避开区域中的多变形障碍物，实现区域的全覆盖搜索

常用算法

常用以下几种算法进行覆盖搜索：

1. 牛耕法
2. 生成树覆盖算法
3. 深度优先搜索/广度优先搜索
4. 磨盘法

牛耕法介绍

Boustrophedon 意思是牛耕地的方式，是利用平行线覆盖区域。 该模式如下图所示(图源：知乎)。

而对于复杂多多变形而言，需要首先划分搜索区域，然后对每一个区域采用上面的方法进行覆盖搜索。也就是说，整个算法分为大致两个过程：分解和搜索。

分解

牛耕法的分解核心逻辑是吧一个复杂的包含障碍物的多变形区域分解为若干个互不重叠的、单联通的单元，在每个单元内，智能体可以进行无障碍的长距离直线扫描。

我们把分解可以分为下面四个步骤

识别临界点

算法使用一条虚拟的扫描线（通常我们用垂直线）从左向右移动，当扫描线扫过地图时，它会不断与多边形边界相交喵。我们需要寻找的是临界点，即这个扫描线与边界交集的地方。我们把临界点分成以下四种：

1. IN：切入点，扫面线开始碰到一个新的空腔（如障碍物的最左端）
2. OUT：切出点，扫面线离开一个空腔（如障碍物最右端）
3. SPLIT：分裂点，到描线有一个连通段
4. MERGE：合并点，两条扫描线合为一条

区域切分

每当扫描线遇到一个SPLIT或MERGE时，算法就会在这些点画出垂直线，将当前的自由空间切段。在障碍物左侧时，空间分裂成上下两个分支；在障碍物右侧时，上下两个分支重新合并，这些切线将整个地图划分为若干个梯形或单连通多变形。

构建邻接图

切分玩了以后我们需要知道这些区域是咋连接的，所以需要这一步。

在这一步中，我们首先将每个子区域看作一个节点，如果两个子区域在屋里上相邻，就在它们之间连一条边。这样子我们就可以得到很多封闭的区域了喵，这些区域我们可以叫做cell喵（喵喵喵我是可爱的小猫）。通过这些区域，我们可以利用深度优先搜索或者广度优先搜索来规划机器人便利这些区域的先后顺序。

然后通过这一步理论上就可以将任务区域划分到几个Cell。

单元路径填充与连接

在每个Cell内部，由于没有障碍物，直接填充我们在第一节提到的那种平行线覆盖就好啦，当一个Cell扫描完了以后呢，我们就可以根据上一步生成的顺序来搜索下一个Cell了喵！效果是下面这样的（主包加了一点平滑）：

现在这个算法还有点小问题，主要是搜索顺序上的，我后面修复一下。

To Be Written

后面还会补充一下写代码时候遇到的坑，以及讨论一下牛耕法是如何实现相邻区域连续扫描的喵。