geometry - 多边形区域计算

Question

因此，为了工作，我正在开发一个可以探索任意区域的机器人 Controller 。该区域由一系列顶点定义(它是一个多边形)。这是一个例子:

机器人从中间开始，尝试到达最外层边界，然后一路跟随。但由于地形的原因，它可能无法到达某些区域，只能探索给定的区域:

我想要做的是计算所有尚未探索的单个区域，并返回定义其边界的顶点，如下所示:

计算完成后，我应该有一个新的多边形数组，其中包含 A、B 和 C 的几何图形。

不幸的是，我无法想出一个好的、快速的算法来做到这一点。计算这个的最佳方法是什么？

Answer 1

一种方法是为点p定义一个谓词，使其“接触”封闭区域的边界，可能根据某种容差ε > 0，例如，T 当且仅当 p 位于边界 ε 的距离内。然后遍历探索区域的边界，注意每个顶点的谓词:..,T, T, T, F, F, F, F, F, T, T,... 然后您的区域由 F 的最大字符串、限制这些 F 的两个 T 向量以及它们之间的边界区域的边界分隔。我刚刚用作示例的字符串概述了您的区域 B:五个 F。