长沙市人才网_商标购买网站_百度极速版客服电话_国外网站排名 top100

系列文章目录

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
TODO:写完再整理

文章目录

系列文章目录
前言
Boustrophedon Decomposition实现地图全覆盖的原理
Boustrophedon Decomposition实现区域分解原理
- 事件
- - IN事件
  - OUT事件
  - MIDDLE事件
- 代码实现
- 其他demo
论文
优缺点

前言

认知有限，望大家多多包涵，有什么问题也希望能够与大家多交流，共同成长！

本文先对****做个简单的介绍，具体内容后续再更，其他模块可以参考去我其他文章

提示：以下是本篇文章正文内容

Boustrophedon Decomposition实现地图全覆盖的原理

在分解计算的同时,邻接图也被确定。同样,每个单元格是图中的一个节点,相邻单元格的节点之间有一条边。类似深度优先的图搜索算法输出一个路径列表,表示对邻接图的穷举遍历。遍历路径列表构成了对邻接图的穷举遍历。

最后,使用上述路径列表计算机器人实际走的路径。当机器人进入一个"未清洁"的单元格时,规划Boustrophedic运动,然后规划到路径列表中下一个单元格的路径。当机器人进入一个"已清洁"的单元格时,它只是规划一条穿过该单元格到路径列表中下一个单元格的路径。重复这两个动作,直到到达路径列表的末尾,即直到每个单元格都被清洁。

Boustrophedon Decomposition实现区域分解原理

Boustrophedon Cell分解方法与梯形分解方法相似。同样,一个切片从左到右扫过一个由多边形障碍物填充的有界平面环境。

本质上,当切片的连通性发生变化时,单元格打开和关闭
在这里插入图片描述

事件

IN事件

在IN事件中,切片连通性增加,当前单元格关闭,两个新单元格打开
在这里插入图片描述

OUT事件

在OUT事件中,切片连通性减少,两个当前单元格关闭,一个新单元格打开
在这里插入图片描述

MIDDLE事件

梯形分解和Boustrophedon分解方法之间的区别在于中间事件
在MIDDLE事件中,不打开也不关闭单元格,而是简单地更新当前单元格。
用另外两种类型的事件取代了中间事件:FLOOR和CEILING。FLOOR事件对应于多边形障碍物顶部的顶点,CEILING事件对应于障碍物底部的顶点
在这里插入图片描述
event结构包含事件的位置、类型和指向与之关联的边(或多条边)的指针。
event结构最多有两种类型的边指针:floor指针和ceiling指针。

IN事件的ceiling指针指向从事件发出的下一条边,floor指针指向在事件终止的前一条边。
OUT事件的floor指针指向从它发出的下一条边,ceiling指针指向在事件终止的边。
CEILING事件只有一个ceiling指针,指向从事件发出的边;
FLOOR事件只有一个floor指针,指向在事件终止的边。

流程

该算法的输入是一个多边形列表,其顶点按逆时针顺序列出。该算法首先从多边形列表创建一个事件列表。多边形没有特定的顺序,但在我们的实现中,我们做了一个通用假设,即没有两个IN事件或两个OUT事件具有相同的x坐标。

在考虑特定多边形时,算法首先找到多边形的IN事件。算法遍历多边形的顶点列表,直到遇到最左边的顶点。这个顶点及其相关信息被插入到事件列表中。由于顶点是以逆时针方式排序的,下一个顶点序列是CEILING事件。回想一下,虽然这些顶点对应于多边形的下侧,但它们是CEILING事件,因为它们对应于紧接在多边形下方的单元格的ceiling。

算法遍历多边形列表,插入每个顶点作为CEILING事件,直到算法遇到最右边的顶点。这个顶点及其相关信息被插入到事件列表中作为OUT顶点。剩下的顶点对应于FLOOR事件。

当遇到事件时,将它们插入到按事件的x坐标排序的有序事件列表中。插入过程是O(n log n),其中n是多边形环境中的总边数(或顶点数)。

（2）单元格cell
单元格cell可以用两个列表表示:一个floor边列表和一个ceiling边列表,它们都界定单元格cell。因此,cell结构包含两个指向边列表的指针:一个floor指针和一个ceiling指针。cell结构还包含一个指向相邻单元格的链表。最后,cell结构有两个标志:visited和cleaned,它们在算法的后面使用。

Boustrophedon分解的单元格cell是以增量方式通过扫描线方法计算的。扫描环境类似于按顺序访问事件列表中的每个事件,因为事件列表已经排序。

第一个单元格是最左边的单元格。在我们的实现中,假设在实际扫描过程开始之前(即,扫描从最左边的IN事件左边开始),最左边的单元格被人为地打开。还假设环境的上方由一条边界,下方由一条边界。因此,第一个单元格的floor和ceiling指针指向这些边界边。

第一个真正的事件是IN事件。在IN事件处,确定切片与当前单元格的floor的交点和切片与当前单元格的ceiling的交点。用f和c表示这些点，如下图
在这里插入图片描述
通常,当前单元格的floor和ceiling有多条边,因此交点f和c是当前单元格最后一条floor边和ceiling边的端点。现在,确定了当前单元格的所有floor段和ceiling段,该单元格被认为是关闭的。

接下来,要打开两个新单元格:底部单元格和顶部单元格。底部单元格的floor中第一条边的起点是点f,底部单元格的ceiling中第一条边的起点是事件。底部单元格的floor指针设置为先前关闭的单元格的floor指针,底部单元格的ceiling指针设置为打开事件的ceiling指针。相反,对于顶部单元格,floor中第一条边的起点是事件,而ceiling中第一条边的起点是点c。在这里,新的floor指针设置为事件的floor指针,新的ceiling指针设置为先前关闭的单元格的ceiling指针。

当遇到FLOOR事件时,更新当前单元格的floor指针。具体来说,与事件相关的floor边被添加到当前单元格的floor边列表中。类似地,当遇到CEILING事件时,与事件相关的ceiling边被添加到ceiling边列表中。

最后,当遇到OUT事件时,两个单元格关闭,一个新单元格打开。再次,让底部单元格和顶部单元格表示在OUT事件处关闭的两个单元格,新单元格表示在IN事件处打开的单元格。设f为当前切片与底部单元格的floor列表中当前边的交点,c为当前切片与顶部单元格的ceiling列表中当前边的交点。点f是底部单元格的floor列表中最后一段的端点,事件位置是底部单元格的ceiling列表中最后一段的端点。同样,事件位置是顶部单元格的floor列表中最后一段的端点,c是顶部单元格的ceiling列表中最后一段的端点。一旦确定了底部和顶部单元格的所有floor段和ceiling段,底部和顶部单元格就关闭了，如下图
在这里插入图片描述
接下来,要打开一个新单元格。第一条floor段的起点是f,第一条ceiling段的起点是c。新单元格的floor指针设置为前一个底部单元格的floor指针,新单元格的ceiling指针设置为前一个顶部单元格的ceiling指针。

单元格邻接列表也是增量构建的。回想一下,每个单元格都有一个指向相邻单元格列表的指针,该指针在IN和OUT事件中更新。目标是将相邻单元格插入到邻接列表中,使得相邻单元格围绕当前单元格按逆时针顺序排列。在IN事件处,当前单元格被分成两个新单元格:底部和顶部。首先,顶部单元格的指针被插入到当前单元格的邻接列表的前面,然后底部单元格的指针被插入到新邻接列表的前面。结果是

neighbor_list = bottom -> top -> old_neighbor_list

在OUT事件处,底部和顶部单元格合并成一个新单元格。首先,顶部单元格的指针被插入到新单元格的邻接列表的末尾,然后底部单元格的指针被插入到邻接列表的末尾。结果是

neighbor_list = old_neighbor_list -> top -> bottom

这个过程产生了一个邻接列表,其元素是相邻单元格,从当前或新单元格的右下方开始,按逆时针方向排列

在访问了事件列表中的所有事件后,所有单元格及其邻接关系都被计算出来;实际上,Boustrophedon分解及其邻接图已经确定。

代码实现

import numpy as np
import matplotlib.pyplot as plt
from typing import List, Tuple
from matplotlib.patches import RegularPolygonPoint = Tuple[int, int]
Cell = List[Point]def is_adjacent(cell1: Cell, cell2: Cell) -> bool:"""判断两个单元格是否相邻"""for p1 in cell1:for p2 in cell2:if abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]) == 1:return Truereturn Falsedef merge_cells(cells: List[Cell]) -> List[Cell]:"""合并相邻的单元格"""merged_cells = []for cell in cells:merged = Falsefor i, merged_cell in enumerate(merged_cells):if is_adjacent(cell, merged_cell):merged_cells[i] = merged_cell + cellmerged = Truebreakif not merged:merged_cells.append(cell)return merged_cellsdef bcd(env: np.ndarray) -> np.ndarray:"""Boustrophedon Cellular Decomposition"""rows, cols = env.shapecell_grid = np.zeros_like(env, dtype=int)  # 创建一个与环境大小相同的网格,用于存储单元格的IDcell_id = 1  # 初始单元格ID为1for col in range(cols):slice = env[:, col]  # 获取当前列的数据cells = []  # 存储当前列的单元格cell = []  # 存储当前单元格的像素坐标for row in range(rows):if slice[row] == 0:  # 如果当前像素是障碍物if cell:  # 如果当前单元格非空cells.append(cell)  # 将当前单元格添加到cells列表中cell = []  # 重置当前单元格为空else:  # 如果当前像素是自由空间cell.append((row, col))  # 将当前像素的坐标添加到当前单元格中if cell:  # 如果最后一个单元格非空cells.append(cell)  # 将最后一个单元格添加到cells列表中if col == 0:  # 如果是第一列for cell in cells:  # 遍历第一列的每个单元格for row, col in cell:  # 遍历单元格中的每个像素坐标cell_grid[row, col] = cell_id  # 将像素点标记为当前单元格的IDcell_id += 1  # 单元格ID加1else:  # 如果不是第一列prev_cells = []  # 存储上一列的单元格信息for row in range(rows):if cell_grid[row, col-1] != 0:  # 如果上一列的当前行不是障碍物prev_cell = [(row, col-1)]  # 初始化一个新的上一列单元格while col > 0 and cell_grid[row, col-1] == cell_grid[row, col-2]:  # 向左遍历,找到连续的、属于同一单元格的像素prev_cell.append((row, col-2))  # 将像素坐标添加到当前的上一列单元格中col -= 1  # 列号减1,继续向左遍历prev_cells.append(prev_cell)  # 将当前的上一列单元格添加到prev_cells列表中i = 0  # 上一列单元格的索引for cell in cells:  # 遍历当前列的每个单元格if i < len(prev_cells) and len(cell) == len(prev_cells[i]):  # 如果当前单元格与上一列的对应单元格长度相同for row, col in cell:  # 遍历当前单元格的每个像素坐标cell_grid[row, col] = cell_grid[prev_cells[i][0]]  # 将像素点标记为上一列对应单元格的IDi += 1  # 上一列单元格索引加1else:  # 如果当前单元格与上一列的对应单元格长度不同,或者上一列没有对应单元格for row, col in cell:  # 遍历当前单元格的每个像素坐标cell_grid[row, col] = cell_id  # 将像素点标记为新的单元格IDcell_id += 1  # 单元格ID加1return cell_grid  # 返回生成的单元格网格def merge_cells_bcd(cell_grid: np.ndarray, threshold: int = 5) -> np.ndarray:"""合并BCD算法生成的单元格:param cell_grid: 单元格网格:param threshold: 长度差阈值,默认为5:return: 合并后的单元格网格"""rows, cols = cell_grid.shapemerged_grid = np.copy(cell_grid)  # 创建一个副本,用于存储合并后的单元格网格for col in range(1, cols):  # 从第二列开始遍历prev_cell_id = None  # 上一个单元格的IDprev_cell_length = 0  # 上一个单元格的长度for row in range(rows):curr_cell_id = cell_grid[row, col]  # 当前单元格的IDif curr_cell_id != 0:  # 如果当前单元格不是障碍物if curr_cell_id == prev_cell_id:  # 如果当前单元格与上一个单元格ID相同curr_cell_length = prev_cell_length + 1  # 当前单元格长度加1else:  # 如果当前单元格与上一个单元格ID不同curr_cell_length = 1  # 重置当前单元格长度为1if prev_cell_id is not None and curr_cell_id != prev_cell_id:  # 如果上一个单元格存在,且与当前单元格ID不同if abs(prev_cell_length - curr_cell_length) < threshold:  # 如果上一个单元格长度与当前单元格长度差小于阈值merged_grid[row - prev_cell_length : row, col] = prev_cell_id  # 将当前单元格合并到上一个单元格else:  # 如果长度差大于等于阈值prev_cell_id = curr_cell_id  # 更新上一个单元格ID为当前单元格IDprev_cell_length = curr_cell_length  # 更新上一个单元格长度为当前单元格长度else:  # 如果上一个单元格不存在,或者与当前单元格ID相同prev_cell_id = curr_cell_id  # 更新上一个单元格ID为当前单元格IDprev_cell_length = curr_cell_length  # 更新上一个单元格长度为当前单元格长度return merged_griddef generate_environment(shape=(600, 1200), n_stars=15, n_triangles=15, max_size=50):"""随机生成一个环境:param shape: 环境的形状(高度,宽度):param n_stars: 五角星的数量:param n_triangles: 三角形的数量:param max_size: 图形的最大尺寸:return: 生成的环境图像"""env = np.ones(shape, dtype=np.uint8)# 随机生成五角星for _ in range(n_stars):x, y = np.random.randint(0, shape[1]), np.random.randint(0, shape[0])size = np.random.randint(10, max_size)star = RegularPolygon((x, y), 5, radius=size, orientation=np.random.uniform(0, 2*np.pi), facecolor='black')plt.gca().add_patch(star)# 随机生成三角形for _ in range(n_triangles):x, y = np.random.randint(0, shape[1]), np.random.randint(0, shape[0])size = np.random.randint(10, max_size)triangle = RegularPolygon((x, y), 3, radius=size, orientation=np.random.uniform(0, 2*np.pi), facecolor='black')plt.gca().add_patch(triangle)plt.axis('equal')plt.axis('off')plt.tight_layout()fig = plt.gcf()fig.canvas.draw()env = np.array(fig.canvas.renderer._renderer)[:, :, 0]env = 1 - (env < 128).astype(np.uint8)plt.close()return envdef display_grid(env: np.ndarray, cell_grid: np.ndarray):"""显示原始环境和分解后的单元格网格"""fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 6))ax1.imshow(env, cmap='binary')ax1.set_title('Original Environment')ax1.axis('off')cell_colors = np.random.rand(np.max(cell_grid) + 1, 3)cell_colors[0] = [1, 1, 1]  # 障碍物为白色ax2.imshow(cell_colors[cell_grid])ax2.set_title('BCD Grid')ax2.axis('off')plt.tight_layout()plt.show()# 测试代码
env = generate_environment(shape=(600, 1200), n_stars=30, n_triangles=30, max_size=80)
cell_grid = bcd(env)
display_grid(env, cell_grid)  # 显示合并后的单元格网格

其他demo

https://blog.csdn.net/qq_35635374/article/details/142416475

论文

https://www.ri.cmu.edu/pub_files/pub4/choset_howie_1997_3/choset_howie_1997_3.pdf
https://blog.csdn.net/jucat/article/details/139012652

优缺点

TCD 会对所有的顶点画延长线，但 BCD 只会选择那些两端都可以延长顶点画线。因此 BCD 先对于 TCD 来说减少了很多冗余的区域分解。因此，TCB是区域分解的基础，但BCD 的分解方式也更加的流行一些。

相邻子区域边界重复覆盖
Boustrophedon Decomposition VS Trapezoidal Decomposition
在这里插入图片描述

Boustrophedon Cell分解拥有更少单元格的优势在于可以最小化来回运动的boustrophedon运动的数量
在这里插入图片描述
如上图，考虑两个相邻的梯形单元格,它们的宽度分别是机器人宽度的两倍半。为了覆盖每个梯形,机器人必须进行三次通过,总共六次纵向运动。使用Boustrophedon分解方法,这两个单元格合并成一个单调多边形单元格,需要五次通过才能覆盖