連接兩個盒子之間的連線避免傳遞其他人

我有幾個隨機分散的盒子（x，y，寬度，高度），其中一些需要從box1中的點（x1，y1）鏈接到點（x2， y2）通過畫一條線。我試圖想出一種方法，通過繪製幾條直的相互連接的線來繞過任何一個盒子（如果不可能用一條直線走向），避免通過任何其他盒子（box1和box2除外））。問題是我不知道這樣的算法（更不用說有一個技術/通用名稱）。希望能夠以算法或表達的想法的形式提供任何幫助。連接兩個盒子之間的連線避免傳遞其他人

感謝

來源

2011-09-04 ccit

你可以作弊。如果先繪製兩個原點框和線條，然後繪製隨機框（與線條的筆觸樣式相同），則看起來線條只是勾勒框線而不是相交。 –

這是不是真的很清楚你想要做什麼..線條給出，或者你必須選擇畫線？因爲如果他們得到了，如果重疊的話，沒有辦法避免重疊 – Simone

也許我明白了......線條不是必須的單個線段，但他們可以獲得連接多個線段嗎？ – Simone

把所有（X，Y）的一組V

添加的起點和終點的箱子的角落 COORDS座標V 。
創建一組邊緣E連接每個不與任何盒子邊交叉的角落（盒子中的對角線除外）。

如何檢查，如果線穿過一個側箱可以用this algorithm
做現在使用您所選擇的路徑搜索算法，找出圖中的路徑（V，E）。

如果您需要一個簡單的算法找到最短路徑，只需使用BFS即可。

（這將產生沿的一些箱子邊走一段路，如果這是不可取的，你可以在步驟1中放點，從實際的角落一段距離三角洲。）

如果邊緣可能不是對角線：

創建線的大電網，這些箱子之間去。
丟棄穿過盒子邊的網格邊緣。
使用您選擇的路徑查找算法在網格中查找路徑。

來源

2011-09-04 10:59:02 aioobe

該算法非常好，但是您能否更詳細地解釋步驟3。只要不與任何方框相交，我是否可以從所有座標（包括開始/結束）創建邊緣？如果需要，還可以修改這種算法以僅生成垂直和水平線（而不是對角線）？ – ccit

是的，如果開始/結束之間的線沒有穿過任何方塊邊，那麼您肯定會想要包含該邊...該邊將實際上是所得到的路徑！關於你的第二個問題，我不確定。然而，如果你解決了這個問題，你最終可能會使用路徑尋找算法（A *，BFS，Dijkstra，...），所以在這兩種情況下你可能都需要設置一些圖。 – aioobe

我喜歡第一種算法，因爲它是有效的，並且有一些距離增量（爲了避免觸及邊緣），它可能是最合適的解決方案。當然，我最終必須有一個圖（和路徑尋找算法），但我想要一個具有最小頂點的圖。你的回答滿足這個要求。我可能會先使用第一個，然後通過將它們放在一個小網格中來調整對角線。謝謝。 – ccit

假設線不能是對角線，這是一個簡單的方法。它是基於BFS也將找到連接點的最短路線：

只需創建一個圖表，包含一個頂點的每個點（x，y）和每個點的邊緣：

((x,y),(x+1,y)) ((x,y),(x-1,y))  ((x,y),(x,y+1))  ((x,y),(x,y-1))

但每個邊緣必須存在，只要它不與盒子重疊。

現在只是從點（X1，Y1）到（x2，y2）做一個簡單的BFS

這是真的，也容易獲得對角線方式相同，但你需要爲每個頂點8層的邊緣，這是，除了先前的4：

((x,y),(x-1,y+1)) ((x,y),(x-1,y-1))  ((x,y),(x+1,y-1))  ((x,y),(x+1,y+1))

但是，每個邊緣必須存在，只有當它不與盒子重疊。

編輯

如果可以不考慮空間劃分爲一個網格，這裏的另一種可能性，它不會給你很最短路徑，雖然。

創建一個圖形，其中每個方框都是一個頂點，並且對於任何其他可以到達而沒有線條重疊第三個方框的方框具有邊緣。現在使用包含兩點的box1和box2之間的dijkstra找到短路徑。

現在考慮每個盒子有一個小的計數，不與任何其他盒子重疊。通過這種方式，您可以鏈接通過dijistra發現的路徑中每個框的進入點和退出點，並通過計數。

來源

2011-09-04 11:49:01 Simone

當你說「每個點（x，y）的頂點」我知道你把空間分成網格嗎？ – ccit

是的，我假設 – Simone

事實上，你可以總是將空間分成像素，如果你需要的是一個實用的算法。將空間劃分爲像素要快得多;它還將允許您使用輔助布爾網格在恆定時間內檢查點和框的重疊。 – Simone

連接兩個盒子之間的連線避免傳遞其他人

回答

相關問題