在JavaScript中剪裁矩形

我正在嘗試編寫一個函數，它需要兩個重疊的矩形，並返回一個覆蓋矩形A區域但排除矩形B區域的矩形數組。看看這個算法看起來像什麼，因爲可能碰撞的數量是巨大且難以解釋的。在JavaScript中剪裁矩形

tl; dr我試圖使用另一個矩形剪裁矩形，導致覆蓋其餘區域的矩形集合。

|-------------|        |-------------| 
|A   |        |R1   | 
|  |-------|----|       |-----|-------| 
|  |B  | |   To    |R2 | 
|  |  | |   ====>   |  | 
|  |  | |       |  | 
|-----|-------| |       |-----| 
     |   | 
     |------------| 

POSSIBLE OVERLAP PATTERNS 

|-----|   |-----|  |-----|  |-----| 
| |---|-|  |-|---| |  | |-| |  | |-| | 
|-|---| |  | |---|-|  |-|-|-|  | |-| | 
    |-----|  |-----|   |-|   |-----| 

    |-|   |-----|   |-----| 
|-|-|-|  | |---|-|  |-|---| | 
| |-| |  | |---|-|  |-|---| | 
|-----|  |-----|   |-----|

注意，可能的重疊圖案是兩倍示出，因爲矩形A和B可以是醚矩形任何上述內容中重疊圖案。

來源

2013-05-18 Robert Hurst

這可能是使用了頂點這個可行的。您可以根據B中頂點之間的距離A計算新的矩形座標。 – Nikki

存在另一個問題，結果有時會超過一個矩形。我認爲在一到九之間。 –

當然有一個標準的算法？無論如何;一個主意。有4個座標和4個y座標，您的新區域將始終是這些區域的組合。 4 x座標將畫布分成5個垂直波段，y座標劃分爲5個水平波段，如果最差的情況最差，則有25個不重疊的矩形屬於A，B，兩者都不是。你保留僅屬於A的屬性並排除所有其他屬性。 – boisvert

不會有任何特定設置一個獨特的解決方案，但你可以很容易地找到該算法的解決方案之一：

內的查找矩形高於矩形B.如果頂部A高於B（即在px中具有較低的值），則存在這樣的矩形。該矩形由（A的左邊緣，A的上邊緣）至（A的右邊緣，B的上邊緣）定義。
如果B的左邊緣在A的左邊緣的右邊，則下一個矩形是:(A的左邊緣，min（A的上邊緣，B的上邊緣））到（B的左邊緣，最大值（A的底部邊緣，B的底部邊緣））
如果B的右邊緣到B的右邊緣的左側，類似於上面
...和下文B

總共，您將獲得0到4個矩形。

僞帶着幾分不尋常的，但是爲了這個目的明確的，矩形的定義：

function getClipped(A, B) { 
    var rectangles = []; 
    if (A.top < B.top) { 
     rectangles.push({ left: A.left, top: A.top, right: A.right, bottom: B.top }); 
    } 
    if (A.left < B.left) { 
     rectangles.push({ left: A.left, top: max(A.top, B.top), right: B.left, bottom: min(A.bottom, B.bottom) }); 
    } 
    if (A.right > B.right) { 
     rectangles.push({ left: B.right, top: max(A.top, B.top), right: A.right, bottom: min(A.bottom, B.bottom) }); 
    } 
    if (A.bottom > B.bottom) { 
     rectangles.push({ left: A.left, top: B.bottom, right: A.right, bottom. A.bottom }); 
    } 

    return rectangles; 
} 

var rectA = { left: nn, top: nn, right: nn, bottom: nn}; 
var rectB = { left: nn, top: nn, right: nn, bottom: nn}; 

var clipped = getClipped(rectA, rectB) ;

來源

2013-05-18 08:24:04

有些情況未涉及 - 例如如果B比A更寬並且將A切入兩個...... – boisvert

@boisvert，它將被覆蓋。你所有的九個地區都完全覆蓋。在數學上不像你的解釋那麼優雅，但是有一個非常簡單的算法。 –

糟糕...我沒有注意你使用最小和最大。你是對的，它工作得很好。不要看到任何不雅的事情。 – boisvert

兩個矩形將屏幕分爲9個區域（而不是14個）。再想想你的配置：

y1 -> |-------------|  
     |A   |   
y2 -> |  |-------|----| 
     |  |B  | | 
     |  |  | | 
     |  |  | | 
y3 -> |-----|-------| | 
      |   | 
y4 ->  |------------| 
    ^ ^ ^^
     x1 x2  x3 x4

的X座標定義5條垂直帶，但第一（左）和去年（右）都提不起興趣，所以你只需要在3個頻段工作，從X1到X4。 y座標相同：從y1到y4三個水平帶。

這是9個矩形區域屬於A，B，沒有或兩者。你的榜樣劃分是這樣的：

|-----|-------|----|  
    |A |A  |none| 
    |-----|-------|----| 
    |A |Both |B | 
    |  |  | | 
    |  |  | | 
    |-----|-------|----| 
    |none |B  |B | 
    |-----|-------|----|

所以比較A和B的座標，你會發現其中9個區僅屬於A.它們是保持區域。

來源

2013-05-18 08:21:05 boisvert

謝謝，這是非常有幫助的。乾杯！ –

但是，請參閱dan.p的答案，爲您提供一個完整的解決方案... – boisvert

在JavaScript中剪裁矩形

回答

相關問題