因此,为了工作,我正在开发一个可以探索任意区域的机器人 Controller 。该区域由一系列顶点定义(它是一个多边形)。这是一个例子:
机器人从中间开始,尝试到达最外层边界,然后一路跟随。但由于地形的原因,它可能无法到达某些区域,只能探索给定的区域:
我想要做的是计算所有尚未探索的单个区域,并返回定义其边界的顶点,如下所示:
计算完成后,我应该有一个新的多边形数组,其中包含 A、B 和 C 的几何图形。
不幸的是,我无法想出一个好的、快速的算法来做到这一点。计算这个的最佳方法是什么?
最佳答案
一种方法是为点p定义一个谓词,使其“接触”封闭区域的边界,可能根据某种容差ε > 0,例如,T
当且仅当 p 位于边界 ε 的距离内。然后遍历探索区域的边界,注意每个顶点的谓词:..,T, T, T, F, F, F, F, F, T, T,...
然后您的区域由 F
的最大字符串、限制这些 F
的两个 T
向量以及它们之间的边界区域的边界分隔。我刚刚用作示例的字符串概述了您的区域 B:五个 F
。
关于geometry - 多边形区域计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11192198/