PMR QuadTree data structure and algorithm [closed]

Question

I want to implement PMR Quadtree which can process points and random polygons instead of point only as traditional QuadTree in below demo http://donar.umiacs.umd.edu/quadtree/lines/pmr.html

However, I could not find any pages describe the PMR QuadTree algorithm or any sample code about it. If someone know about the PMR QuadTree material, please share me.

Note: The above Webpage mentions two materials but they are not free to download online.

Dugaid

Answer 1

The PMR Quadtree is typically used to store edges of a polygon but can easily be extended to include points as well. There is a C++ implementation of it at http://czep.net/quicksilver/ (quadtree.cpp & quadtree.hpp). Below is pseudocode explaining the algorithm:

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

Staceystaci

I found it several days ago. Anyway, thank you for your answer. – Dugaid