最大矩形重疊點

給定網格L * C中的N個矩形（N < = 100.000）的座標（L和C的範圍可以從0到1.000.000.000）我想知道什麼是矩形重疊的最大數目在電網的任何一點。最大矩形重疊點

所以我想我會使用一個掃描算法，每個事件（矩形的開頭或結尾）按x值排序，我添加或刪除一個間隔到我的結構。

我必須使用樹來保持間隔的最大重疊，並且能夠添加和刪除間隔。

我知道如何做到這一點，當間隔（開始和結束）的值範圍從0到100.000，但這是不可能的，因爲平面的尺寸從0到1.000.000.000。我怎樣才能實現這樣一棵樹？

L和C是整數嗎？ –

你需要多快的查找？這聽起來像你想提前掃描以便進行O（1）查找。通過矩形掃描你想知道的每個點是不可接受的？ – mprivat

是L和C整數 – user1637030

如果您事先知道所有矩形的座標，則可以使用「座標壓縮」。由於您只有10^5個矩形，這意味着您最多有2 * 10^5個不同的座標，即x和y座標。因此，您可以創建一個從這些座標到1到2 * 10^5的自然數的映射（通過簡單排序座標）。然後，您可以使用您已知的普通樹作爲新座標。

這將足以獲得矩形的數量，但如果您還需要它們重疊的點，則還應該維護一個反向映射，以便您可以返回矩形的實際座標。在一般情況下，答案將是一個矩形，而不僅僅是一個點。

2012-08-30 22:05:41

好吧我明白我會盡力實現這一點，但它似乎是非常棘手的做反向映射。但是一個很好的解決方案。 – user1637030

實際上它應該非常容易 - 對於從普通到壓縮的映射使用某種類型的字典（映射等），對於反向映射，您可以使用保存類型信息的數組「按升序壓縮的x座標是198「。如果你對樹的實現感到滿意，這應該不是一個巨大的負擔。 –

使用interval tree。你的情況有點複雜，因爲你確實需要一個加權區間樹，其中權重是該區間開放矩形的數量。

2012-08-30 20:27:41

它看起來像一棵非常複雜的樹。從來沒有用過這樣的東西，我要研究這個，但是你有比維基百科更好的教程嗎？ – user1637030

對不起，我沒有。 –

回答