algorithm - PMR QuadTree数据结构和算法

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗Update the question所以堆栈溢出的值小于aa>。
在下面的演示中，我想实现pmr四叉树，它可以处理点和随机多边形，而不是像传统的四叉树那样只处理点。
on-topic
但是，我找不到任何页面描述PMR四叉树算法或任何关于它的示例代码如果有人知道PMR四叉树的材料，请与我分享。
注意：上面的网页提到了两种材料，但它们不是免费在线下载的。

最佳答案

PMR四叉树通常用于存储多边形的边，但也可以很容易地扩展到包含点在http://czep.net/quicksilver/（四叉树CPP和四叉树HPP）上有一个C++实现。下面是解释算法的伪代码：

class Box
    double CenterX
    double CenterY
    double Size

// a SpatialItem must implement Intersects against a Box (i.e. a rectangle)
class SpatialItem
    abstract bool Intersects(Box box)

class PMRQuadTreeNode
    int level // the level of this node
    int maxDepth // the maximum number of levels of the quadtree
    int splittingThreshold // determines when to split the node
    Box bounds
    PMRQuadTreeNode[] childNodes
    SpatialItemCollection items

    // Determines if the Leaf Node is overflowing and should be split
    // NOTE: Leaves at the maximum depth never overflow
    bool IsOverflowing()
        if (level == maxDepth)
            return false

        return items.Count > splittingThreshold

    // Insert adds the SpatialItem to items if it intersets against bounds
    // If this Node IsOverflowing, then it is Split and becomes an internal
    // Node with 4 Leaf Nodes
    void Insert(SpatialItem item)
        if (item.Intersects(bounds))
            if (IsLeaf)
                items.Add(item)
                if (IsOverflowing())
                    Split()
            else
                foreach (Node child in childNodes)
                    child.Insert(item)

    // When a Node is Split, each SpatialItem is added to each Child Node it
    // intersects. Split is *NOT* called again for each child - items are
    // merely added directly to each Child's items collection.
    void Split()
        CreateChildNodes() // create and initialize 4 child nodes
        foreach (var item in items)
            foreach (var child in childNodes)
                // don't call Insert() here, as Split should only be called once
                if (item.Intersects(child.bounds))
                    child.items.Add(item)
        items.Clear()
        IsLeaf = false

    void CreateChildNodes()
        static double[] XOffsets = new double[] { -0.25, 0.25, 0.25, -0.25 }
        static double[] YOffsets = new double[] { -0.25, -0.25, 0.25, 0.25 }

        childNodes = new PMRQuadTreeNode[4]

        for (int i = 0..3)
            childNodes[i] = new PMRQuadTreeNode {
                level = level + 1
                maxDepth = maxDepth
                splittingThreshold = splittingThreshold
                bounds = new Box {
                        CenterX = bounds.center.X + XOffsets[i] * bounds.size,
                        CenterY = bounds.center.Y + YOffsets[i] * bounds.size,
                        Size = bounds.size / 2
                    }
                }