查找由集retangle

一組矩形（重疊的矩形太）和一組點的。
座標爲integer類型。
矩形的邊平行於軸線

輸出：

任何矩形內的所有點給出

什麼是高效算法和數據結構應該使用？謝謝。

2014-04-01 Xeing

可以使用sweep line algorithm：由X座標排序的點。當矩形進入或離開掃描線（左右邊界的X座標）時引入事件。當前與掃描線相交的矩形是投影到掃描線上時的一組間隔，因此可以使用interval tree或segment tree（後者僅在Y座標壓縮後進行維護，但可以將其作爲預處理步驟進行）來維護。

使用該設置，您只需檢查每個點是否與您的數據結構維護的某個間隔相交。

運行：O（（N + M）日誌（N + M））

來源

2014-04-01 06:33:57

我能想出的最好的辦法是將檢查每一個點(x,y)它是否包含在任何矩形(l,t,w,h)，產生束縛的O(nm)運行時，其中n是點的數量和m是矩形的數目。

來源

2014-04-01 06:12:54 Codor

我的問題是，設定點的要大得多的一套長方形的，我要求*有效*算法，不是天真的解決方案。 – Xeing

2D段樹(example here）是有效的數據結構，以檢查是否點內的任何矩形的

來源

2014-04-01 06:16:12 MBo

由於矩形中的點數多於矩形，因此最好使用矩形中的數據結構。 – Nuclearman

查找由集retangle

回答

相關問題