示例网格http://www.eriding.net/resources/general/prim_frmwrks/images/asses/asses_y3_5d_3.gif（例如）
访问所有可到达的正方形后，该过程即告完成。换句话说，即使某些空间由于被包围而没有障碍，也可能完全无法到达。这是意料之中的。领土。我希望这在尝试到达无法到达的平方时会特别棘手，因为机器人会耗尽所有选择。
在更复杂的方法中，正确的方法似乎是Boustrophedon细胞分解。
但是，我似乎找不到关于Boustrophedon细胞分解算法的很好的描述（即简单的完整描述）。有这样的资源，或者是关于垂直单元分解的更通用的资源，但是它们没有提供对高级算法或低级数据结构的深入了解。
我怎么能有效地访问（映射）此网格？如果存在，我希望有一种算法在网格平方总数方面比$ O（n ^ 2）$更好（即对于$ n * n $网格，它的性能优于$ O（n ^ 4）$ ）。
#1 楼
Boustrophedon细胞分解只是将环境细分为可以由牛角膜路径有效覆盖的区域。可以进行梯形分解，并且可以使用行扫描算法来完成。德伯格等等，以获取所需数据结构和算法的完整说明。Choset，Howie。 “已知空间的覆盖：Boustrophedon细胞分解”自动机器人，2000年。
例如，将一组障碍视为边缘和顶点。假设环境也受到特殊多边形的限制。我们有类似以下内容。要分解此空间，我们只需在每个顶点与最近的线或顶点之间添加垂直边。
要在代码中完成此操作，您只需进行线段相交测试，边的排序列表，以及顶点的排序列表。
从每个顶点$ v_i $以从左到右的顺序，
在每个$ v_i $处创建一条垂直线$ l_i $，一直延伸到第一个边缘或顶点它相交
在每个相交处，创建一个新顶点。
完成此操作后，一组新的边和顶点将仅包含梯形。但我要强调，您不能在线进行此操作（没有事先了解障碍的情况）。如果您想在没有先验知识的情况下进行可靠的覆盖，则可以查看“错误算法”。特别是，这是一个简单的算法，假设环境是有界的。
从开始位置向上和向左移动，直到到达环境的左上角。如果首先遇到障碍，则必须绕过障碍。您知道如果可以绕过某些物体（颠簸并移动），它就是一个障碍。
从左上角向右移动，直到遇到边界。然后向左和向左移动（我们正在对整个空间进行牛头怪）。
当您在左右线上遇到障碍物时，有两种选择。 （i）我们可以绕行直到到达我们要覆盖的左右线，然后继续。 （ii），我们可以转身并覆盖一条新的左右线，直到我们越过障碍物或再次陷入这种情况。我会说明。
在左侧，我们绕过障碍物，直到可以返回到我们试图遵循的“线”。在右侧，我们继续覆盖障碍物一侧的（较小）区域。
第一种方法的优点是，在决定如何处理障碍物之前，您始终要完全绘制障碍物绕开它，因此您可以走更短的路。第二种方法的优点是您完全不必绕开障碍，只需覆盖您所在的区域即可。
请注意，这在在线中定义了牛牙根分解方式：您可以覆盖障碍物之间或障碍物与边界之间的区域。
但是据我所知，第一种方法更易于分析。选择更复杂的算法（例如BFS等），是因为环境不受限制（您不想永远花时间寻找边界），或者在基本上划分环境的方式中确实存在令人讨厌的障碍。为什么这样不好？看这个例子：
左右移动，然后绕过每个障碍物会在每个障碍物之间覆盖太多的小零件。实际上，如果没有全局路径规划，则可以通过将这些列设置为1 px宽，与整个环境一样高且相隔1 px来使它与网格的分辨率一样糟糕。然后每次碰到障碍物时都必须绕过障碍物。
这就是为什么我问您是否对环境的位置有所了解或可以进行全局路径规划的原因。但是，在线与离线讨论以及针对此的最佳算法并不是您真正想要的。
更新：我必须删除图像（而不是https），并将其发布，该图像经常在实际的实际应用程序中使用。 http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/yamauchi_frontiers.pdf
评论
$ \ begingroup $
仅找到Boustrophedon分解算法的描述（简单而言）就足够了。失败的话，对具有类似性能的算法进行简单描述就可以了。
$ \ endgroup $
–伊恩
13年2月20日在22:30
$ \ begingroup $
我添加了一个简单的牛磺腐分解示例。
$ \ endgroup $
–乔什·范德·胡克（Josh Vander Hook）
13年2月21日在4:38
#2 楼
最后，我发现实现此目的的最佳方法是采用一个非常简单的概念：洪水填充。我使用基于堆栈的迭代方法而不是递归选项，并通过使用A *搜索来查找从当前位置到堆栈中下一个位置的路径来修改它的物理空间（仅使用那些已经存在的网格正方形）被访问过，因为我保证可以在两者之间有一条路。）效率似乎相当合理。
评论
$ \ begingroup $
和我一样，您已经发现了基于边界的探索cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1 / ...，它的确运行良好
$ \ endgroup $
–傻笑的人
16年11月9日在21:11
评论
非常有趣的问题。为了清楚起见，您是否将“有效”定义为对任何给定单元的最少重复访问？那可能是表达它的一种方式。确实，我正在尝试避免使用相对于网格平方总数为$ O（n ^ 2）$或更差的算法。
我想这与CNC加工软件所面临的问题类似，该软件必须通过切削工具访问材料来去除材料。
@Rocketmagnet：不太准确，因为CNC机器先验地知道了“障碍”，而我在移动时正在检测它们。
是的，这是对机器人知道其位置的有限环境的在线搜索。障碍的数量，位置和形状是完全未知的-它们可能不是凸形的。