PMR四叉树数据结构和算法

Question

我想实现PMR四叉树，它可以处理点和随机多边形，而不是像下面演示中的传统四叉树那样只处理点http://donar.umiacs.umd.edu/quadtree/lines/pmr.html

然而，我找不到任何描述PMR QuadTree算法的页面或任何关于它的示例代码。如果有人知道PMR QuadTree的材料，请与我分享。

注意：上面的网页提到了两个材料，但它们不是免费在线下载的。

Answer 1

PMR四叉树通常用于存储多边形的边，但也可以很容易地扩展到包括点。它的C++实现位于http://czep.net/quicksilver/（quadtree.cpp和quadtree.hpp）。下面是解释算法的伪代码：

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
                    }
                }