我正在尋找一種爲矩形提供索引的數據結構。我需要插入算法儘可能快，因爲矩形將在屏幕上移動（想想用你的鼠標拖動一個矩形到一個新的位置）。具有快速插入的矩形的空間索引
我已經研究過R-Trees，R + Trees，kD-Trees，Quad-Trees和B-Trees，但是根據我的理解，插入的通常很慢。我更喜歡在次線性時間複雜度插入，所以也許有人可以證明我錯誤列出的任何數據結構。
我應該能夠查詢什麼矩形在點（x，y）或什麼矩形相交矩形（x，y，寬度，高度）的數據結構。
編輯：我想插入這麼快的原因是因爲如果你想到一個矩形在屏幕上移動，他們將不得不被刪除，然後重新插入。
謝謝！
您提到的數據結構相當混雜：特別是B-樹應該很快（插入成本隨着存在的項目數的對數增長），但不會加速你的交集查詢。
忽略這一點 - 並希望最好 - 空間數據結構分爲兩部分。第一部分將告訴您如何從數據構建樹結構。第二部分將告訴您如何跟蹤描述存儲在該節點下的項目的每個節點的信息，以及如何使用它來加速查詢。
您通常可以在不使用關於如何構建樹的（昂貴的）想法的情況下捏住有關在每個節點上跟蹤信息的想法。例如，您可以通過位交叉點的座標爲每個矩形創建一個鍵，然後使用完美的普通樹結構（例如B樹或AVL樹或紅黑樹）來存儲它仍然保留每個節點的信息。實際上，這可能會加快您的查詢速度 - 儘管在實際數據上實施並測試它之前，您無法分辨出來。大多數方案中的樹狀結構說明的目的是提供性能保證。
兩個後記：
1）我喜歡帕特里夏樹木這一點 - 他們是相當容易實現，並且添加或刪除條目不擾亂樹形結構多，所以你不會有太多的工作更新存儲在節點上的信息。
2）最後一次我看了一個窗口系統，它根本就沒有考慮到這些聰明的東西 - 它只是保持一個線性項目列表，並在需要時通過它進行搜索：速度夠快。
這可能是一個擴展的評論，而不是一個答案。
我對你真正想要的東西有點困惑。我猜想你想要一個數據結構來支持對「給定矩形的ID，返回當前座標」等問題的快速回答。是對的嗎 ？
或者你想回答'位置（x，y）'是什麼矩形？在這種情況下，具有與顯示器的高度和寬度匹配的尺寸的數組可能就足夠了，數組中的每個元素都是該像素上矩形的列表（推測是短的）。
但是，然後你聲明，你需要一個插入算法儘可能快地處理不斷移動的矩形。如果屏幕上只顯示10個矩形，則可以只包含一個包含每個矩形座標的10個元素的數組。然後更新他們的職位將不需要任何插入數據結構。
有多少個矩形？他們創建的速度有多快？並被摧毀？你想如何處理重疊？矩形只是一個邊界，還是包含內部？
我編輯了我的問題來清楚地解釋我想要的內容。 – TheCloudlessSky 2010-04-02 23:15:08
我會使用多尺度網格方法（相當於四叉樹的某種形式）。
我假設你使用整數座標（即像素），並有足夠的空間來容納所有的像素。
有一組矩形列表，每個像素一個。然後，bin兩個一個地再做一遍。再次，一次又一次，直到你有一個像素覆蓋了一切。
現在，關鍵是你插入你的矩形在水平，這是一個很好的匹配矩形的大小。這將像（像素大小）〜= min（高度，寬度）/ 2一樣。現在對於每個矩形，只有少數幾個插入要做列表（你可以用一個常量來限定它，例如選擇一個有4到16個像素的東西）。
如果你想在x，y上尋找所有的矩形，你可以看看最小像素的列表，然後在包含它的2x2 binned像素的列表中，然後在4x4等等。你應該有log2（像素數）步驟來查看。（對於較大的像素，您必須檢查（x，y）是否確實在矩形中;您預計其中大約一半的邊界會成功，並且所有矩形在矩形內都會成功，所以您期望沒有比直接查看像素多出2倍以上的工作）。
現在，怎麼樣插入？這非常便宜 - O（1）堅持在列表的前面。
刪除怎麼辦？這比較昂貴;您必須仔細查看並修復每個您輸入的像素的列表。大約相同大小的空間和中重疊的矩形數量大約爲O（n）。如果你有大量的矩形，那麼你應該使用其他數據結構來保存它們（散列集，RB樹等）。 （請注意，如果您的最小矩形必須大於一個像素，則不需要實際形成多尺度結構一直到像素級;只需向下，直到最小的矩形不會失去希望地丟失在您的binned像素中）
也許我錯過了一些東西，但是如何在亞線性時間插入？只要讀取每個矩形的座標就已經是一個O（n）操作。 – 2010-04-02 23:04:08
如果「屏幕」具有索引的所有對象（kd，quad，r/trees），則插入必須爲
TheCloudlessSky
2010-04-02 23:10:18
如果有一個界限有多快矩形可以移動，那麼詢問是否有辦法分攤重建過程並不是沒有道理的。 – user287792 2010-04-02 23:11:33