cad c#四叉树

四叉树是一种常用的二维空间索引结构，可以用来加快对空间数据的查询和处理。C#中可以通过定义一个Quadtree类来实现四叉树。

以下是一个简单的Quadtree类实现：

public class Quadtree<T>
{
    private QuadtreeNode<T> root;

    public Quadtree(RectangleF bounds)
    {
        root = new QuadtreeNode<T>(bounds);
    }

    public void Insert(T data, RectangleF bounds)
    {
        root.Insert(data, bounds);
    }

    public List<T> Query(RectangleF bounds)
    {
        List<T> result = new List<T>();
        root.Query(bounds, result);
        return result;
    }
}

public class QuadtreeNode<T>
{
    private RectangleF bounds;
    private List<T> data;
    private QuadtreeNode<T>[] children;

    public QuadtreeNode(RectangleF bounds)
    {
        this.bounds = bounds;
        data = new List<T>();
        children = new QuadtreeNode<T>[4];
    }

    private bool IsLeaf()
    {
        return children[0] == null;
    }

    private void Split()
    {
        float halfWidth = bounds.Width / 2f;
        float halfHeight = bounds.Height / 2f;
        float x = bounds.X;
        float y = bounds.Y;

        children[0] = new QuadtreeNode<T>(new RectangleF(x, y, halfWidth, halfHeight));
        children[1] = new QuadtreeNode<T>(new RectangleF(x + halfWidth, y, halfWidth, halfHeight));
        children[2] = new QuadtreeNode<T>(new RectangleF(x + halfWidth, y + halfHeight, halfWidth, halfHeight));
        children[3] = new QuadtreeNode<T>(new RectangleF(x, y + halfHeight, halfWidth, halfHeight));
    }

    public void Insert(T data, RectangleF bounds)
    {
        if (!this.bounds.IntersectsWith(bounds))
            return;

        if (IsLeaf())
        {
            this.data.Add(data);

            if (this.data.Count > 10)
            {
                Split();
                foreach (T item in this.data)
                {
                    foreach (QuadtreeNode<T> child in children)
                    {
                        child.Insert(item, bounds);
                    }
                }
                this.data.Clear();
            }
        }
        else
        {
            foreach (QuadtreeNode<T> child in children)
            {
                child.Insert(data, bounds);
            }
        }
    }

    public void Query(RectangleF bounds, List<T> result)
    {
        if (!this.bounds.IntersectsWith(bounds))
            return;

        foreach (T item in data)
        {
            if (bounds.Contains((RectangleF)item))
            {
                result.Add(item);
            }
        }

        if (!IsLeaf())
        {
            foreach (QuadtreeNode<T> child in children)
            {
                child.Query(bounds, result);
            }
        }
    }
}

上面的实现中，Quadtree类是四叉树的主要类，它包含了一个QuadtreeNode类的实例作为根节点。Insert方法用于将数据插入到四叉树中，Query方法用于查询指定区域内的数据。

QuadtreeNode类是四叉树的节点类，它包含了一个矩形区域bounds、一个存储数据的列表data和四个子节点children。Insert方法用于将数据插入到节点中，Query方法用于查询指定区域内的数据。

在Insert方法中，当节点为叶子节点且数据量超过10时，会将节点拆分成四个子节点，并将原来的数据重新插入到子节点中。在Query方法中，对于每个节点，会先判断它的区域是否与指定区域相交，如果相交则遍历该节点的数据列表，将符合指定区域的数据添加到结果列表中，然后递归遍历其子节点。

使用时，可以先创建一个Quadtree实例，然后通过Insert方法将数据插入到四叉树中，最后通过Query方法查询指定区域内的数据。例如：

Quadtree<RectangleF> quadtree = new Quadtree<RectangleF>(new RectangleF(0f, 0f, 100f, 100f));
quadtree.Insert(new RectangleF(10f, 10f, 20f, 20f));
quadtree.Insert(new RectangleF(30f, 30f, 10f, 10f));
List<RectangleF> result = quadtree.Query(new RectangleF(0f, 0f, 50f, 50f));

上面的代码创建了一个包含0~100的矩形区域的四叉树，插入了两个矩形，然后查询了左上角50x50的区域内的数据，最终result应包含一个矩形。