所以，为了工作，我正在研究一个探索任意区域的机器人控制器。该区域由一系列顶点定义（它是一个多边形）。这是一个例子：
机器人从中间开始并尝试到达最外层边界，然后一直跟随它。但是，由于地形的性质，它可能无法到达某些区域，只能探索给定区域：
我想要做的是计算所有尚未探索的单个区域，并返回定义其边界的顶点，如下所示：
计算完之后，我应该有一个新的多边形数组，其中包含 A、B 和 C 的几何图形。
不幸的是，我想不出一个好的、快速的算法来做到这一点。计算这个的最佳方法是什么？
问问题
287 次
2 回答
2
您想要外部边界多边形减去内部粉红色（已探索）多边形的布尔差的 ISTM。但是，没有简单的算法可以解决这个问题，所以我建议您查看并从各种多边形裁剪库中进行选择。
这是一些剪裁库的最新比较 - http://rogue-modron.blogspot.com.au/2011/04/polygon-clipping-wrapper-benchmark.html
也是我自己的开源免费软件多边形裁剪器的无耻插件 - http://angusj.com/delphi/clipper.php
于 2012-06-25T17:34:35.667 回答
2
一种方法是为点p定义一个谓词以“接触”封闭区域的边界，可能根据某个容差 ε > 0，例如，T当且仅当p在边界的 ε 距离内。然后遍历已探索区域的边界，注意每个顶点的这个谓词：..,T, T, T, F, F, F, F, F, T, T,... 然后，您的区域由 s 的最大字符串、限定这些sF的两个顶点以及边界区域之间的边界分隔。我刚刚用作示例的字符串概述了您的区域B：五个s。TFF
于 2012-06-25T21:19:26.653 回答