計算相交矩形的周長和麪積？

Question

我搜索了很多，但我沒有找到一個適合這種情況的好答案。 我們有一些水平或垂直的矩形。它們可以隨機放置在頁面上。它們可以重疊或具有共同的邊緣或彼此分開。 我想找到一個O（nlogn）算法，可以找到這些矩形的周長和麪積。 這些圖片可能會使問題變得清晰。

我認爲區間樹木可能會有所幫助，但我不知道怎麼樣。

Answer 1

它可以通過掃描線算法完成。

我們將從左到右掃一條想象的線。 我們將注意到直線和矩形集合之間的交集代表一組間隔，並且當我們遇到矩形的左邊緣或右邊緣時它會改變。

假設交叉點在x座標x1和x2之間沒有變化。 然後，如果相交的後X1長度爲大號，線會掃過的區域等於（X2 - X1）* 大號，通過掃描從X1到X2。

例如，你可以看看X1爲左藍線，並X1爲以下圖片右側的藍線（我是從你偷了，並修改了一下:)）：

應該清楚，我們的掃描線的交點在這些點之間不會改變。但是，藍色的交叉點與紅色的交叉點完全不同。

我們需要一個數據結構，這些操作：

insert_interval(y1, y2); 
get_total_length(); 

那些很容易用一個段樹實現的，所以我就不贅述了。現在

，算法會是這樣的：

1. 採取所有垂直細分領域，並通過它們的x座標進行排序。
2. 對於每一個相關的x座標（只顯示爲矩形邊緣的那些是很重要的）：
   • 令x1是以前的相關x座標。
   • 設x2爲當前相關x座標。
   • 設L是我們的數據結構給出的長度。
   • 將（x2 - x1）* L加到總面積總和中。
   • 刪除數據結構中x = x2段的所有右邊邊。
   • 將所有的左邊的邊上的x = x2段加到數據結構中。

通過離開和右我的意思是一個矩形的邊。

這個想法僅用於計算區域，但是，您可以修改它來計算周長。基本上你會想知道它在某個x座標變化之前和之後的交集長度之間的差異。這個算法的複雜度是O（N log N）（雖然它取決於你可能得到的值的範圍，但這很容易處理）。

你可以在TopCoder上找到更多關於掃描線算法的更多信息。

你可以閱讀關於PEG judge wiki上使用分段樹的各種方法。

這是我的（真的很老的）算法的實現，作爲SPOJ problem NKMARS的解決方案：implementation。

Answer 2

以下是O（N2）解決方案。

int area = 0; 
FOR(triange=0->N) 
{ 
    Area = area trianlges[triangle]; 
    FOR(int j = triangle+1 -> N) 
    { 
     area-= inter(triangle , j) 
    } 
} 
return area; 

int inter(tri a,tri b) 
{ 
    if ((min(a.highY ,b.highY) > max(a.lowerY, b.lowerY)) && (min(a.highX ,b.highX) > max(a.lowerX, b.lowerX))) 
    return (min(a.highY ,b.highY) - max(a.lowerY, b.lowerY)) * (min(a.highX ,b.highX) - max(a.lowerX, b.lowerX)) 

    else return 0; 
}