标签: range-tree

注意:问题的底部有一个重要的编辑 - 检查出来

题

说我有一套要点:

我希望在半径范围内找到围绕它的点数最多的点 (即圆圈)或内部 (即正方形)2维的点.我将它称为最密集的函数.

对于这个问题中的图表,我将周围的区域表示为圆圈.在上图中,中间点的周围区域以绿色显示.该中间点具有半径内所有点的最多周围点 并且将由最密集的点函数返回.

我试过的

解决这个问题的可行方法是使用范围搜索解决方案; 这个答案进一步解释,它有" 最坏的情况使用这个,我可以获得每个点周围的点数,并选择具有最大周围点数的点.

但是,如果积分非常密集(大约一百万),那么:

那么每一百万点()需要进行范围搜索.最坏的情况,哪里 是范围内返回的点数,对于以下点树类型是正确的:

• 二维的kd树(实际上稍微差一点,在 )
• 2d范围的树木,
• 四叉树,最糟糕的时间

所以,对于一组人来说 半径范围内的点 在该组中的所有点,它给出了复杂性 对于每一点.这产生了超过一万亿次的运营!

有关实现这一目标的更有效,更精确的方法的任何想法,以便我能够在合理的时间内找到具有最多周围点的点,并且在合理的时间内(最好 或更少)？

编辑

原来上面的方法是正确的!我只需要帮助实现它.

(半)解决方案

如果我使用2d范围树:

• 范围报告查询成本 ,为 返回点,
• 对于具有分数级联(也称为分层范围树)的范围树,复杂性是 ,
• 对于2维,即 ,
• 此外,如果我执行范围计数查询(即,我不报告每个点),那么它的成本 .

我会在每一点上执行此操作 - 产生 复杂我想要的!

问题

但是,我无法弄清楚如何为2d分层范围树的计数查询编写代码.

我找到了一个关于范围树的很好的资源(从第113页开始),包括2d-range树的伪代码.但我无法弄清楚如何引入分数级联,也不知道如何正确实现计数查询以使其具有O(log n)复杂性.

我还发现了两个范围树的实现在这里和这里在Java中,一个在C++ 在这里,虽然我不知道该用分数作为级联它指出上述countInRange方法

它在最坏的情况下返回这些点的数量*O(log(n)^ d)时间.它还可以返回矩形中的点,在最坏的情况下*O(log(n)^ d + k)时间,其中k是位于矩形中的点的数量.

这告诉我它不适用分数级联.

精致的问题

因此,为了回答上面的问题,我需要知道的是,是否存在具有分数级联的二维范围树的任何库,其具有范围计数查询的复杂性 所以我不会重新发明任何轮子,或者你能帮助我编写/修改上面的资源来执行这种复杂性的查询吗？

如果你能提供任何其他方法来实现2d点的范围计数查询,也不要抱怨 以任何其他方式!

我目前正在实施2D范围树.我在为我的Node类提出一个似乎合理的模型(用Java)时遇到了麻烦.

树中的节点可以具有以下任何一个:中间值,右和左子指针,子树,数据指针和/或前一个和下一个指针.

我将节点分解为三个独立的逻辑部分

• a)具有midRange值的节点 - 每个节点都有一个midRange
• b)具有左,右和子树点的节点.这表示非叶节点.
• c)不是next,prev和数据指针.这表示叶节点.

我尝试应用Composite和Decorator模式,但无济于事.我试过制作:

1. 节点接口包含所有可能的getter/setter,即:getMidRange,getLeft,getRight,setLeft,setRight等...
2. 有两个类实现接口:Node2D和LinkedNode(叶节点).Node2D做了所有事情,除了保持下一个和上一个的链接.虽然LinkedNode只保留了下一个和上一个的链接.

它是这样的,但是如果有一种更好的方法将它建模为一组类,我就会徘徊？

编辑:范围树(简短信息):在范围树中 - 所有数据都存储在Leaf节点中,并且树始终是平衡的.此外,所有叶子都处于相同的高度.此外,叶子被分类,并通过双向链表链接在一起.最后,但并非最不重要的是,每个非叶子节点都有一个子树 - 它也是一个范围树,但是叶子在下一个属性上排序(比如y,如果原始树在x上排序).

我正在做这个项目，我必须在 3d 空间中搜索对象，效率是一个很大的问题，我认为范围树非常适合我想要做的事情，间隔树也可以工作，但我不是要从树中删除任何内容，一旦我在 3D 空间中添加了每个对象，我将只使用该结构进行搜索。

下面是我将如何使用该结构：

假设我有一个对象数组（我们称之为queryArr）（约 10,000 个对象）每个对象有 3 个参数（x，y，z）我有另一个非常大的对象数组（我们称之为totalArr）（> 5,000,000 个对象） ）。

我想在这里做的是给定的元素queryArr，找到最相似（或相同的元素totalArr）在某些情况下会出现在相同的参数对象totalArr，但在大多数情况下，不会有是具有相同参数的对象。

因此，我将搜索(x+10,y+10,z+10)和之间的所有值(x-10,y-10,z-10)。如果它没有产生任何结果，我会将 x,y,z 乘以 2 并重试，直到产生一些结果。

这样做的最简单方法是一种朴素的搜索方法，它具有复杂性， O(N*M) (N = size of queryArr, M = sie of totalArr)但这种方法非常缓慢和愚蠢。

我认为范围树是要走的路，但我自己从未实现过，我不太明白范围树如何在大于 2 的维度上工作。那么有人知道范围树的良好实现吗？我相信如果我能有一个源代码，我就能理解它们是如何工作的。

顺便说一句，如果您认为此任务有比范围树更好的结构，请告诉我我愿意接受建议。（我已经考虑过 kd-Trees 和 Interval 树）

谢谢，

我有一个要求,我必须根据一些属性值更新图形前端的颜色.属性值有不同的范围....比如-30到-45,-60到-80等等....那么,我需要一个数据结构,我可以存储这些范围(预填充它们)....当我确定这一点时,我想知道这一点落在O(1)时间或O的范围内(logN)时间....所以,我的查询将由一个点组成,输出应该是包含该点的唯一范围...

我在范围树和段树之间感到困惑....我想在c ++ stl map之上构建树.