如何找出一個形狀是否可以通過

Question

我有一個複雜的多邊形（可能是凹形），並且它的一些邊緣標記爲入口/出口點。在這個多邊形內可能有一個或多個任意形狀的封鎖。我可以使用什麼方法來確定一對入口/出口邊緣之間是否存在一定寬度的路徑？

通過閱讀這個問題，它看起來像一個家庭作業類型 - 它不是。我只希望至少有一些我可以追求的線索，因爲這對我來說是新的。

Answer 1

看看Motion Planning - 這裏有大量的信息。

Answer 2

這取決於路線是否需要寬度。如果必須移動的對象的大小有限，則需要將域多邊形的Minkowski差異與移動對象的多邊形進行比較，然後嘗試通過該多邊形進行路由。

準確計算路徑的一種方法是計算多邊形的可見性圖。可見性圖的頂點對應於域多邊形的頂點（可能帶有障礙物所在的洞），如果兩個頂點彼此「可見」，則兩個頂點由邊連接。如果存在將入口連接到出口的一組邊，則該形狀是可以通過的。你也可以計算諸如最短路徑之類的東西。以天真的方式計算可見性圖並不難，但速度很慢。有非常先進的算法，但它們（AFAIK）尚未實施。幾年前我嘗試了幾次，只有平庸的結果。他們大多數假設頂點處於一般位置，使用精確算術，而實際應用則使用浮點數。