多邊形區域計算

因此，爲了工作，我正在研究探索任意區域的機器人控制器。該區域由一系列頂點（它是一個多邊形）定義。這裏有一個例子：多邊形區域計算

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

任何體面的剪裁器都會返回多個多邊形。正如在你的例子中，如果只返回一個多邊形，解決方案將不正確。至於'寬容'，也許你可以用該容差抵消（膨脹/放氣）內部多邊形或外部邊界多邊形。 –

多邊形區域計算

回答

相關問題