多边形区域计算

因此，为了工作，我正在研究探索任意区域的机器人控制器。该区域由一系列顶点（它是一个多边形）定义。这里有一个例子：多边形区域计算

An example region.

的机器人，中间开始，并试图达到最外层边界，然后按照它周围的所有道路。然而，由于地形的性质，但它可能无法达到某些区域，只能探索一个给定的区域：

Full exploration is blocked.

我想要做的就是计算尚未探索所有个别地区，并返回定义其边界的顶点，是这样的：

The calculated regions

此计算之后，我应该有多边形的新的数组，包含A，B，和C.

几何

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

来源

2012-06-25 CodeBunny

一种方法是定义一个谓词点或者根据一些容忍度来“接触”封闭区域的边界， > 0，例如，T当且仅当如果p在±ε的距离内，的边界。然后遍历探索区域的边界，注意每个顶点的谓词：..,T, T, T, F, F, F, F, F, T, T,...然后，您的区域由最大的字符串F s，两个界定这些F的边界以及边界区域之间的边界限定。我刚刚用作示例的字符串概述了您的区域B：五F s。

来源

2012-06-25 21:19:26

ISTM，你想要外部边界多边形的布尔差异减内部粉红色（探索）多边形。然而，对此没有简单的算法，所以我建议你看一下并从各种多边形剪裁库中进行选择。

这里是一个相当新的一些剪辑库中的比较 - http://rogue-modron.blogspot.com.au/2011/04/polygon-clipping-wrapper-benchmark.html

，也是一个无耻的插头我自己的开源免费软件多边形剪钳 - http://angusj.com/delphi/clipper.php

来源

2012-06-25 17:34:35

这与多边形裁剪类似，但我想要返回一系列多边形，而不仅仅是一个。我还想要有一个“宽容” - 如果探索区域的点与外边界“接近”，那么它就好像我已经达到了它。 – CodeBunny

任何体面的剪裁器都会返回多个多边形。正如在你的例子中，如果只返回一个多边形，解决方案将不正确。至于'宽容'，也许你可以用该容差抵消（膨胀/放气）内部多边形或外部边界多边形。 –

多边形区域计算

回答

相关问题