geometry - 多边形区域计算

Question

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



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



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



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

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

Answer 1

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