如何有效地计算大型重叠组？

Question

我有两组非常大的鸟，它们在X英里半径的圆圈里飞行，每一组都有一个跟踪器，所以我可以在任何给定的时刻确定它们的位置。这两个圆环有一部分重叠(类似于维恩图的样子)。

因为这些是鸟，所以在任何时间点，鸟A(在圆圈1中)可能随机地在重叠区域或不在重叠区域。

在周期性的基础上，我想要计算交叉点上的鸟，并确定它们是哪些鸟。

我遇到的问题是为它确定正确的数据结构。我曾考虑过使用Bloom过滤器，但它不允许移除(鸟从重叠中移出)，并且非常占用内存。

我对任何想法都持开放态度(将数据存储在Redis中以进行读取，等等)。

Answer 1

如果圆具有固定的圆心和半径，当您收到一个位置时，您可以判断该位置是否在重叠中(例如，到每个圆心的距离是否小于半径)。因此，您的问题是维护一个从中删除和插入项目的集合。我首先尝试的是一个非常普通的数据库，或者一个内存中的HashSet。

如果Redis适合你，最容易做的事情就是当一只鸟在重叠的时候创建一个键，当它不在重叠的时候删除它。这使您可以测试是否有鸟在重叠中，但不能有效地读出哪些鸟在重叠中。当然，您可以在插入一只鸟并且以前没有在重叠中时递增计数器，在鸟移出重叠时递减计数器，以保持重叠中鸟的运行计数。

在我看来，您可以使用Redis排序集来维护重叠中的一组鸟-参见例如ZRANGE，ZADD，ZREM。如果达到某种限制，您可以为每只鸟存储一个记录，其中包含指向其他鸟记录的下一个和前一个链接，并在重叠区域中构建鸟的双向链接列表-使用Redis或任何您信任的键值存储。