R實現重疊矩形的聯合

Question

我想解決一個問題，我有多個重疊的矩形，我需要找到矩形的組合區域。矩形的相交部分只需要看一次。我在網上搜索，我發現線掃描算法將爲我完美工作，這裏解釋：What is an Efficient algorithm to find Area of Overlapping Rectangles

我的問題是，R有類似的東西已經實現？我在R中找不到類似的東西。如果它已經存在，我不想重新發明輪子。

Answer 1

有趣的問題。假設我們已經四個矩形座標，如下圖所示：

require(data.table) # v1.9.7+ 
dt = data.table(x0 = c(7,17,5,1), x1 = c(14,27,11,10), 
       y0 = c(1,55,6,14), y1 = c(10,70,20,34)) 
dt[, id := .I] # add row numbers 
# x0 x1 y0 y1 id 
# 1: 7 14 1 10 1 
# 2: 17 27 55 70 2 
# 3: 5 11 6 20 3 
# 4: 1 10 14 34 4 

要查看是否矩形i與j相交，條件，IIUC是：

x0_i <= x1_j, x1_i >= x0_j, y0_i <= y1_j, y1_i >= y0_j, where 

x0_i < x1_i, x0_j < x1_j, y0_i < y1_i, y0_j < y1_j 

這可以用條件來實現連接，這最近在data.table，v1.9.7的當前開發版本中實現。請參閱安裝說明here。

ans = dt[dt, 
     .(id1 = pmin(i.id, x.id), id2 = pmax(i.id, x.id), 
      x0 = pmax(x.x0, i.x0), x1 = pmin(x.x1, i.x1), 
      y0 = pmax(x.y0, i.y0), y1 = pmin(x.y1, i.y1)), 
     on = .(x0 <= x1, x1 >= x0, y0 <= y1, y1 >= y0) 
     ][id1 != id2] 
ans = unique(ans) 
# id1 id2 x0 x1 y0 y1 
# 1: 1 3 7 11 6 10 
# 2: 3 4 5 10 14 20 

基本上這個執行自聯接。對於dt中的每一行，它都會根據提供給on=參數的條件找到所有匹配的索引，並根據匹配的行提取兩個矩形及其相交部分的索引。 id1 != id2篩選出自我重疊..

然後我們確保沒有重複。結果顯示哪個矩形id1與哪個矩形id2重疊，以及它們的相交區域x0, x1, y0, y1。

這是或多或少你在找什麼？