为什么四叉树有时需要一个最大数来保存在一个节点中？

Question

我正在做一个使用 C# 库中的 TriangularMeshQuadtree 的计算几何问题，它的一些构造函数编写如下（来自元数据，所以我看不到实现的细节）：

构造函数 1：

// Summary:
    //     Constructor to use if you are going to store the objects in x/y space, and there
    //     is a smallest node size because you don't want the nodes to be smaller than a
    //     group of pixels.
    //
    // Parameters:
    //   xMax:
    //     eastern border of node coverage.
    //
    //   xMin:
    //     western border of node coverage.
    //
    //   yMax:
    //     northern border of node coverage.
    //
    //   yMin:
    //     southern border of node coverage.
    //
    //   maxItems:
    //     number of items to hold in a node before splitting itself into four branch and
    //     redispensing the items into them.
    public TriangularMeshQuadtree(double xMax, double xMin, double yMax, double yMin, int maxItems);

构造函数 2：

//
    // Summary:
    //     Gets quad tree of a list of triangular surface in the plane with normal of dir
    //
    // Parameters:
    //   surfaces:
    //     A list of triangular surface
    //
    //   dir:
    //     The normal of plane on which quad tree is projected
    //
    //   maxItemNumber:
    //     The maximum number of items in each node of quad tree
    //
    //   transformator:
    //     Coordinate transformator
    //
    // Returns:
    //     A quad tree
    public static TriangularMeshQuadtree GetQuadTree(List<SubTSurf> surfaces, Vector3 dir, int maxItemNumber, out CoordinateTransformator transformator);

我对四叉树的理解是，它将一组点递归地分成4个部分，直到每个点在一个部分中都是唯一的。我不明白上面代码中 maxItem 的定义以及它如何与四叉树一起工作。

Answer 1

您对“...直到每个点在一个部分中都是唯一的”的理解不太正确。它描述了一种非常特殊的四叉树，通常用在例子中来解释这个概念。

一般来说，四叉树的每个节点可以容纳更多的项目。这通常是为了减少节点的数量（如果我们每个节点的条目多于我们需要的节点数）。减少节点数的好处是：

减少内存使用（每个节点都会增加一些内存开销）
通常搜索速度更快（每个节点都添加一个慢的间接），即一个非常 'deep' 的树遍历速度很慢。

maxItem 不应该太大，因为在节点内部，点通常存储在线性列表中。线性列表显然需要线性搜索，因此如果列表太大，速度会变慢。根据我的经验，maxItem 的合理值在 10 到 100 之间。

另一个经常给出的参数是maxDepth。该参数限制树的深度，等于给定节点的父节点数。这个想法是，一个糟糕的数据集会导致一棵非常 'deep' 的树，这使得遍历起来很昂贵。相反，如果一个节点位于 depth=maxDepth，它就不会分裂，即使它超过 maxItem 条目。

综上所述，现实世界中存在有用的四叉树类型结构，每个象限最多允许一个条目。一个例子是 PH-Tree（免责声明：自我广告）。它使用其他技术将深度限制为 32 或 64。解释需要一段时间，这不是问题的一部分，所以我只引用 documentation here.

为什么四叉树有时需要一个最大数来保存在一个节点中？

Why a quadtree sometimes need a max number to hold in a node?

quadtree