獲取一組矩形的輪廓

Question

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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