獲取一組矩形的輪廓

我正在尋找一種算法來獲取由一組不重疊的矩形創建的圖形的輪廓。該圖可以是任何形狀，但是它是簡單連接的，即不包含孔。獲取一組矩形的輪廓

我需要怎麼寫這樣的一個功能的想法：

IEnumerable<Point> GetContour(IEnumerable<Rect> rects)

算法的時間複雜度並不重要，它只是在合理的時間來執行。

來源

2010-02-18 corvus

我可能會在兩遍中做到這一點。第一個將矩形轉換爲一組點（按照繞線順序），包括另一個矩形的角點是沿着邊緣的點。這樣，您最終將得到一個點圖，您可以輕鬆檢測哪些點在哪些矩形之間共享。

因此，只需在圖形中搜索沒有共享矩形的第一個點，並沿着沒有共享矩形的點開始步行路線，或者在前一個點沒有共享矩形的情況下開始兩個共享矩形，直到返回到起點。

您需要爲您的路線維護一個堆棧，以及以前探索點的地圖。

我剛剛剛剛做過這件事（雖然它不僅限於rects，而且我已經完成了第一次），它的工作原理非常好。我看到它能夠在一秒鐘內以更多次的時間計算出一條路線，而不是我可以用一個整數計算出來，所以表現看起來相當不錯，儘管這是用C++編寫的。

來源

2010-02-18 16:21:14 philsquared

謝謝你，好主意而且很容易實現。 – corvus 2010-02-19 09:21:31

這似乎凹殼問題的一個特定情況..許多算法確實存在解決相反凸包問題：

賈維斯三月（wikipedia）爲O（n^2）
格雷厄姆掃描（wikipedia）O（nlogn）

這些是最簡單的，至少有3個，但他們只是優化性能，叔帽子不是你的主要目標之一。

我認爲賈維斯3月可以很容易地適應你的情況，其中你只有矩形。考慮一下這樣一個事實，即在每一段時間裏，這個算法通常都會採用與計算的最後兩點相交的線右側的第一個點，所以如果有更好的選擇規則，可以在特定情況下使其適應凹面的矩形。

在任何情況下也有一個特定的凹殼這裏描述算法：link，你也可以下載他們的API here（這應該是描述算法的論文：link）

來源

2010-02-18 17:07:56 Jack

凹形船體是獨特的嗎？我不確定我們是否可以應用這一點。謹慎地詳細闡述一下？ – 2010-02-18 17:13:04

我認爲這些算法的複雜性在於推斷我們已經知道的信息 - 纏繞和內部/外部。我們知道每個矩形，我們可以使用這些信息來幫助我們找到合成輪廓。 – philsquared 2010-02-18 17:19:47

是的，你知道里面/外面的矩形，但你必須把它們當作想要追蹤輪廓的點，因爲在任何情況下，你都需要看看你正在計算的船體上的矩形的哪些點而且你無法事先知道它。凹殼不是唯一的，但在這種情況下，它可以是矩形對齊（這在問題中沒有指定）。我會盡力爲這個問題制定一個完整的解決方案。 – Jack 2010-02-18 17:44:51

獲取一組矩形的輪廓

回答

相關問題