quadtree

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


I am doing a compuational geometric issue which uses TriangularMeshQuadtree from a C# library, and some of its constructors is written as follows (from metadata, so I cannot see the details of implementations):

constructor 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);

constructor 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);

My understanding of a quadtree is that it divides a set of points recursively into 4 sections until every point is unique in one section. I dont understand the definition of maxItem in the above code and how it works with quadtree.


Solution

  • Your understanding "... until every point is unique in one section" is not quite correct. It describes a very special kind of quadtree that is usually used to in example to explain the concept.

    In general, a quadtree can hold many more items per node. This is often done to reduce the number of nodes (if we have more entries per node than we need fewer nodes). The benefit of reducing node count is:

    The maxItem should not be too large, because inside a node the points are usually stored in a linear list. A linear list obviously requires linear search, so that slows things down if the list is too large. In my experience sensible values for maxItem are between 10 and 100.

    Another parameter that is often given is maxDepth. This parameter limits the depth of the tree, which is equal to the number of parents of a given node. The idea is that a bad dataset can result in a tree that is very 'deep', which makes it expensive to traverse. Instead, is a node is at depth=maxDepth, it is prevented from splitting, even if it exceeds maxItem entries.

    Having said all the above, there are useful real-world quadtree-type structures that allow at most one entry per quadrant. One example is the PH-Tree (disclaimer: self-advertisement). It uses other techniques to limit the depth to 32 or 64. It takes a while to explain and it wasn't part of the question, so I just reference the documentation here.