您如何有效計算大型重疊組？

Question

我有2個非常大的一組飛行在X英里半徑的圓圈裏，每個圓圈都有一個跟蹤器，所以我可以確定它們在任何給定時刻的位置。這兩個圈的一部分重疊（類似於維恩圖的樣子）。

由於這些是鳥類，在任何時間點，鳥A（在圓圈1）可以是在重疊區域中與否，隨機。

在定期，我要計算在路口的鳥，並確定它們是鳥類。

我遇到的問題是爲此確定正確的數據結構。我曾考慮過使用布隆過濾器，但它不允許移除（鳥從重疊中移出）並且內存密集。

我願意接受任何想法（在Redis的存儲數據，從讀等）。

Answer 1

如果圓具有固定中心和半徑，當你收到你能告訴如果該位置是在重疊的位置處（例如，如果每個中心的距離小於半徑）。所以你的問題是維護一個從哪個項目被刪除和插入的集合。我會嘗試的第一件事情將是一個完美的普通數據庫，或者內存中的HashSet。

如果Redis的適合你的，容易做到的事情是創建一個鍵時，一隻鳥在重疊並刪除它時，它不是。這允許您測試是否有任何鳥在重疊中，但不能讀出哪些鳥有效。當一隻鳥被插入並且之前沒有重疊時，你當然可以增加一個計數器，並且當一隻鳥移出重疊時減少計數器，以保持重疊中的鳥數。

在我看來，你可以使用Redis的有序set維護一組小鳥在重疊的 - 例如見ZRANGE，ZADD，ZREM。如果你碰到某種限制，你可以爲每隻鳥存儲一條記錄，其中包含指向其他鳥類記錄的下一個和前一個鏈接，並且在重疊區域中構建一個雙向鏈接的鳥類列表 - 使用Redis或任何鍵值存儲您的信任。