PMR四叉树数据结构和算法

问题描述

我想实现PMR四叉树能够处理点和随机的多边形，而不是点只能作为传统的四叉树下面演示 http://donar.umiacs.umd.edu/quadtree/lines/pmr.html

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

不过，我找不到任何页面描述PMR四叉树算法或任何样本code了。如果有人了解PMR四叉树的材料，请分享我。

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.

推荐答案

的PMR四叉树通常用来存储多边形的边缘，但可以很容易地扩展到包括积分。有一个在 http://czep.net/quicksilver/ 一个C ++实现它（quadtree.cpp＆安培; quadtree.hpp）。下面是伪code解释算法：

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

这篇关于PMR四叉树数据结构和算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！