algorithm - 基于 R-Tree : creating new child nodes when a node is full, 的数据结构，但如果我有很多对象在完全相同的位置怎么办？

Question

我意识到我的标题不是很清楚，但我很难想出一个更好的标题。如果有人想纠正它，请纠正。

我正在为具有无限宇宙的二维游戏开发数据结构。数据结构基于一个简单的(!)节点/叶系统，如 R-Tree .

这是基本概念:您可以设置您希望一个节点(一个容器)最多拥有多少个子节点。如果你想添加一个叶子，但叶子应该在的节点是满的，那么它会在这个节点内创建一组新的节点，并将所有当前的叶子移动到它们的新(更准确)节点。这样，人口稠密的地区将比面积很大但人迹罕至的地区有更多的分割。

这适用于普通对象。当我有多个具有完全相同的 X,Y 位置的 maxChildsPerNode 对象时，唯一的问题出现了:因为节点已满，它会创建更多精确的子节点，但旧的叶子将再次被放在完全相同的节点中，因为它们有完全相同的位置 - 导致创建更多节点和更多节点的无限循环。

那么，当我想在我的树中添加比 maxChildsPerNode 更多且位置完全相同的叶子时，我该怎么办？

附言。如果我未能解释我的问题，请告诉我，以便我可以尝试改进解释。

更新:这是我检查完整节点中的所有叶节点是否具有相同位置的方法:

//returns whether all leafs in the given leaf list are identical
    private function allLeafsHaveSamePos(leafArr:Array<RTLeaf<T>>):Bool {
        if (leafArr.length > 1) {
            var lastLeafTopX:Float = leafArr[0].topX;
            var lastLeafTopY:Float = leafArr[0].topY;
            for (i in 1...leafArr.length) {
                if ((leafArr[i].topX != lastLeafTopX) || (leafArr[i].topY != lastLeafTopY)) return false;
            }
        }
        return true;
    }

Answer 1

我想问一个问题...

• 是否比遵守 maxChildsPerNode 约束重要？

我宁愿将此最大值视为何时拆分的结构提示，并在没有有意义的方法执行拆分时简单地忽略它。

当然你最好重新考虑这个名字，否则对于下一个维护者来说会很奇怪。

在伪代码中我会使用这样的东西:

def AddToNode(node, item):
  node.items.append(item)
  if len(node.items) > node.splitHint:
    leftNode = Node(node.splitHint)
    rightNode = Node(node.splitHint)
    node.split(leftNode, rightNode)
    if len(leftNode.items) == 0 or len(rightNode.items) == 0:
      node.splitHint *= 1.5 # famous golden ratio ;)
    else:
      node.items = [leftNode, rightNode]

重要的一步是在检测到提示时修改提示，而不是我们无法遵守提示，以便不在每次插入时执行此检查(这样我们可以获得恒定的摊销成本)。