查詢輸入矩形重疊的矩形集合

在多維空間中，我有一個矩形集合，所有矩形都與網格對齊。（我正在鬆散地使用「矩形」一詞 - 在三維空間中，它們將是直角棱柱。）查詢輸入矩形重疊的矩形集合

我想查詢此集合中與輸入矩形重疊的所有矩形。

什麼是保存矩形集合的最佳數據結構？我會不時向矩形中添加矩形和刪除矩形，但這些操作將不經常發生。我想要快速的操作是查詢。

一種解決方案是將矩形的角落保留在列表中，並對列表進行線性掃描，找出哪些矩形與查詢矩形重疊，並跳過不包含查詢矩形的矩形。

但是，我希望查詢操作比線性更快。

我看過R-tree data structure，但它包含點的集合，而不是矩形的集合，我沒有看到任何明顯的方式來推廣它。

我的矩形的座標是離散的，以防您覺得有幫助。

我對通用解決方案感興趣，但我也會告訴你我的具體問題的屬性：我的問題空間有三個維度，它們的多樣性差異很大。第一維有兩個可能的值，第二維有87個值，第三維有180萬個值。

來源

2010-06-28 user82928

如果你的第一個維度只有兩個可能值和棱鏡沒有退化（即2D結構），那麼看來你的問題只有2個維度... – 2010-06-29 00:50:30

退化結構是允許的，但謝謝指出。 – user82928 2010-06-30 23:33:54

你用kd-tree實現了這個嗎？我正在尋找它的代碼。 – 2013-07-16 07:05:22

你或許可以使用KD-Trees可用於根據維基頁面矩形：

變化

取而代之點

相反的點，kd樹也可以的包含矩形或 hyperrectangles [5]。一個二維矩形是認爲是一個4D對象（xlow，xhigh， ylow，yhigh）。因此，範圍搜索成爲返回所有與搜索矩形相交的矩形的所有矩形的問題。該樹被構建爲通常的方式，其中所有的矩形都在葉上。在正交範圍搜索中，相對座標爲時與中位數比較時使用。例如，如果當前的級別沿着xhigh分割，我們檢查矩形的搜索的xlow座標。如果中位數小於搜索的xlow座標矩形，則左側分支中的任何矩形都不會與與搜索矩形相交，因此可以修剪爲。否則兩個分支應該穿過。另見間隔樹，，這是一維特例。

來源

2010-06-29 01:11:41

你用kd-tree實現了這個嗎？我正在尋找它的代碼。 – 2013-07-16 07:05:56

您必須使用某種分區技術。但是，由於您的問題受到限制（只使用矩形），因此可以簡化數據結構。我沒有仔細考慮過這個，但類似這樣的東西應該可以工作;）

使用離散值約束 - 您可以創建一個輔助表類數據結構，其中存儲第二維的離散值（ 87個可能的值）。假設這些值表示與此維度垂直的平面。對於這些平面中的每一個，您都可以在此輔助表中存儲與這些平面相交的矩形。

同樣，對於第三維，您可以根據需要使用具有儘可能多的等間隔值的另一個表（180萬太多了，因此您可能希望將此數值減小至少幾個量級），然後創建一個映射兩個選定值之間的矩形。

給定一個查詢矩形，您可以定時查詢第一個表以確定可能與此查詢相交的一組表。然後，您可以在第二個表上執行另一個查詢，並對第一個和第二個查詢結果的結果進行交集。這應該縮小您必須執行的實際相交測試的數量。

來源

2010-06-29 06:16:26 tathagata

我們用PN來稱呼原始問題 - 其中N是維數。

假設我們知道P1 - 1維問題的解：找出一個新的區間是否與給定的區間集合重疊。一旦我們知道要解決它，我們可以檢查新矩形是否與每個x/y/z投影中的矩形集合重疊。

所以P3的解決方案相當於P1_x和P1_y和P1_z。

爲了有效地解決P1，我們可以使用排序列表。列表中的每個節點都將包含座標和打開的intetrvals-up-to-this-coordinate。

假設我們有以下區間： [1,5] [2,9] [3,7] [0,2]

則列表將如下所示：

{0,1}，{1,2}，{2,2}，{3,3}，{5,2}，{7,1}，{9,0}

如果我們收到新的區間，例如[6,7]，我們發現列表中最大的項目小於6：{5,2}，smllest項目大於7：{9,0}。

所以很容易說新的區間確實與現有的區間重疊。

而且在排序列表中的搜索是比線性:)更快

來源

2010-08-24 16:48:01

查詢輸入矩形重疊的矩形集合

回答

相關問題