1

我正在阅读R* Tree 的这个实现，我注意到它们计算重叠的方式与论文定义的方式不同。

在论文中，重叠定义如下：

对于给定的节点/矩形k ，计算k和k的每个兄弟（不包括k）之间的交集面积总和。

重叠放大是这个值的增量，如果将项目r添加到k ，节点k的重叠是多少。

像这样的东西：

childOverlapEnlargement(Node child, item r)
{
    childEnlarged = child.union(r);
    sum = 0;
    for(each sibling s of child which isn't node)
    {
        sum += area(childEnlarged.intersect(s)) - area(child.intersect(s));
    }
    return sum;
}

在另一种实现中，它们按给定节点与要插入的项目的交集区域进行排序。像这样的东西：

childOverlapEnlargement(Node node, item r)
{
    return area(node.intersect(r));
}

显然，它们的实现在计算上比论文的定义要少。但是，我找不到任何明显的逻辑为什么这两个计算应该相等。

所以我的问题是：

  1. 这两个计算是否总是最终选择相同的子树？为什么？
  2. 如果它们确实导致选择不同的子树，结果是更好还是接近论文的定义？还是选择错误？

编辑：重新阅读他们的实现，我意识到他们不是在比较两个兄弟姐妹的交集，而是每个潜在叶子的交集和被插入的项目。奇怪的是，他们选择了与插入项目重叠最少的兄弟姐妹。您不想插入与所插入项目重叠最多的节点吗？

4

1 回答 1

1

也许您正在查看的实现有错误或不正确。没有人是完美的。

请注意，R*-tree 试图最小化重叠放大，而不是重叠本身。

一些重叠可能是不可避免的。如果已经存在重叠，则在插入其他矩形时，您不能期望它会破坏。但是您可以尝试至少不增加重叠量。

至于性能考虑，请检查您是否需要实际计算相交矩形。尝试代替计算area(intersection())来做一个功能intersectionSize()。这确实有所作为。例如，ifA.maxX = 1和B.minX = 2I 可以立即将交集大小设为 0，而无需查看任何其他维度。

避免急切地预先计算您可能需要的所有交叉点等。相反，只计算您实际需要的那些。分析您的代码，看看您是否可以优化关键代码路径。那里通常有一些低垂的果实。

于 2013-01-16T07:35:29.617 回答