038集——quadtree（CAD—C#二次开发入门）

效果如下：

using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using Application = Autodesk.AutoCAD.ApplicationServices.Application;
using System.Runtime.CompilerServices;
using Autodesk.AutoCAD.Runtime;
using Autodesk.AutoCAD.GraphicsInterface;
using System.Drawing;
using Autodesk.AutoCAD.Colors;
namespace AcTools
{

        public class QuadTreeDemo
        {
        [CommandMethod("xx")]
        public static void treedemo()
            {
                 //四叉树用于存储平面物体的位置数据，并根据位置选定指定对象，随机画8000个圆，圆心在(100,100)到（800，800）之间。 
                 //用户指定一个点，选定这个点附近200范围内所有的圆并高亮显示。
                Document dm = Z.doc;
                Random rand = new Random();
                List<Circle> cirs = new List<Circle>();
                //做八千个小圆
                for (int i = 0; i < 8000; i++)
                {
                    Point3d cent = new Point3d(100+ rand.NextDouble() * 800, 100+rand.NextDouble() * 800, 0);
                    Circle cir = new Circle(cent, Vector3d.ZAxis, 1);
                    cir.Radius = 1 + (rand.NextDouble() * (10 - 1));//[1到10)的随机数
                cir.ColorIndex = rand.Next(255);
                cirs.Add(cir);
                }
                Extents3d ext = new Extents3d();
                cirs.ForEach(c => ext.AddExtents(c.GeometricExtents));
                //new 四叉树，把小圆添加到四叉树里，ext是四叉树的整个范围
                QuadTreeNode<Circle> qtree = new QuadTreeNode<Circle>(ext);
                for (int i = 0; i < cirs.Count; i++)
                {
                //添加了圆心和圆的四个象限点并延伸一定距离。所有满足条件的都会选中。
                qtree.AddNode(cirs[i].Center, cirs[i]);
                //qtree.AddNode(new Point3d(cirs[i].GetPointAtParameter(0).X + 400, cirs[i].GetPointAtParameter(0).Y + 300, 0), cirs[i]);
                //qtree.AddNode(new Point3d(cirs[i].GetPointAtParameter(Math.PI / 2).X + 400, cirs[i].GetPointAtParameter(Math.PI / 2).Y + 400, 0), cirs[i]);
                //qtree.AddNode(cirs[i].GeometricExtents.MinPoint , cirs[i]);//包围盒的两个点
                //包围盒最大的的x增大200，相当于这个圆的包围盒最大点的x右移200，如果在指定范围，那么选中，如果右移200不到范围，或超出范围，那么不选中，所以图中会有两个区域被选中
                qtree.AddNode(new Point3d(cirs[i].GeometricExtents.MaxPoint.X+200, cirs[i].GeometricExtents.MaxPoint.Y,0), cirs[i]);
               
            }

                //把圆添加到数据库
                using (Transaction tr = dm.Database.TransactionManager.StartTransaction())
                {
                    BlockTable bt = (BlockTable)tr.GetObject(dm.Database.BlockTableId, OpenMode.ForRead);
                    BlockTableRecord btr = (BlockTableRecord)tr.GetObject(bt[BlockTableRecord.ModelSpace], OpenMode.ForWrite);
                    for (int i = 0; i < cirs.Count; i++)
                    {
                        cirs[i].SetDatabaseDefaults();
                        btr.AppendEntity(cirs[i]);
                        tr.AddNewlyCreatedDBObject(cirs[i], true);
                    }
                    tr.Commit();
                }

                ViewTableRecord acView = new ViewTableRecord();
                acView.Height = 1000;
                acView.Width = 1000;
                acView.CenterPoint = new Point2d(500, 500);
                dm.Editor.SetCurrentView(acView);

                //任选一点
                PromptPointResult ppr = dm.Editor.GetPoint("选择一点");
                if (ppr.Status == PromptStatus.OK)
                {
                    Point3d pt = ppr.Value;
                    // 查找这个点周围50范围内的对象 
                    List<Circle> cirsref = qtree.GetNodeRecRange(pt, 50);
                //亮显这些圆
                Z.db.AddCircleModeSpace(pt, 50);
                    cirsref.ForEach(c => c.Highlight());
                }

                /*
                 * 四叉树里可以添加任何对象，比如线，文字，块参照，甚至序号，啥都行，
                 * 只要把对象和点对应上，就是用点来表示这个对象的位置，
                 * 如果一个对象不能用一个点来完全表示他的位置。那么重复添加这个对象，并设置多个点
                 * 比如一个直线的两个端点，或者一条曲线上等分的若干个点。一个文字的四个角点，等等。
                 * 请自由发挥。
                 */

            }
        }

        public class QuadTreeLeaf<T>
        {
            private Point3d pos;
            private T refObject;

            public QuadTreeLeaf(Point3d pos, T obj)
            {
                this.pos = pos;
                refObject = obj;
            }

            public T LeafObject
            {
                get
                {
                    return refObject;
                }
            }

            public Point3d Pos
            {
                get { return pos; }
                set { pos = value; }
            }
        }
        /// <summary>
        /// 四叉树节点
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public class QuadTreeNode<T>
        {
            /// <summary>
            /// 节点拥有的叶子节点
            /// </summary>
            public List<QuadTreeLeaf<T>> items;
            /// <summary>
            /// 节点拥有的分支
            /// </summary>
            public QuadTreeNode<T>[] branch;
            /// <summary>
            /// 节点空间最大容量，受minSize影响
            /// </summary>
            protected int maxItems;
            /// <summary>
            /// 节点空间分割的最小大小（最小宽度，高度）
            /// </summary>
            protected double minSize;

            public const double TOLERANCE = 0.00001f;
            /// <summary>
            /// 节点的空间
            /// </summary>
            //public Rect bounds;
            public Extents3d ext;


            public QuadTreeNode(Extents3d ext, int 每级最多存储数量 = 4, double minSize = -1)
            {
                this.ext = ext;
                //bounds = new Rect(ext.MinPoint.X, ext.MinPoint.Y, ext.MaxPoint.X - ext.MinPoint.X, ext.MinPoint.Y - ext.MinPoint.Y);

                maxItems = 每级最多存储数量;
                this.minSize = minSize;
                items = new List<QuadTreeLeaf<T>>();

            }
            public bool HasChildren()
            {
                if (branch != null)
                    return true;
                else
                    return false;
            }

            /// <summary>
            /// 将节点空间分割4份
            /// </summary>
            protected void Split()
            {
                if (minSize != -1)
                {
                    if ((ext.MaxPoint.X - ext.MinPoint.X) <= minSize && (ext.MaxPoint.Y - ext.MinPoint.Y) <= minSize)
                    {
                        return;
                    }
                }
                var ext4 = ext.Split4();

                branch = new QuadTreeNode<T>[4];
                for (int i = 0; i < 4; i++)
                {
                    branch[i] = new QuadTreeNode<T>(ext4[i], maxItems, minSize);
                }

                foreach (var item in items)
                {
                    AddNode(item);
                }

                items.Clear();
            }

            /// <summary>
            /// 根据坐标获得相应的子空间
            /// </summary>
            /// <param name="pos"></param>
            /// <returns></returns>
            protected QuadTreeNode<T> GetChild(Point3d pos)
            {
                if (ext.Contains(pos))
                {
                    if (branch != null)
                    {
                        for (int i = 0; i < branch.Length; i++)
                            if (branch[i].ext.Contains(pos))
                                return branch[i].GetChild(pos);

                    }
                    else
                        return this;
                }
                return null;
            }
            /// <summary>
            /// 增加叶子节点数据
            /// </summary>
            /// <param name="leaf"></param>
            /// <returns></returns>
            private bool AddNode(QuadTreeLeaf<T> leaf)
            {
                if (branch is null)
                {
                    this.items.Add(leaf);

                    if (this.items.Count > maxItems) Split();
                    return true;
                }
                else
                {
                    QuadTreeNode<T> node = GetChild(leaf.Pos);
                    if (node != null)
                    {
                        return node.AddNode(leaf);
                    }
                }
                return false;
            }
            public bool AddNode(Point3d pos, T obj)
            {
                return AddNode(new QuadTreeLeaf<T>(pos, obj));
            }

            /// <summary>
            /// 可以是空间任意位置，只是根据这个位置找到所在的空间去删除对象
            /// </summary>
            /// <param name="pos"></param>
            /// <param name="obj"></param>
            /// <returns></returns>
            public bool RemoveNode(Point3d pt, T obj)
            {
                if (branch is null)
                {
                    for (int i = 0; i < items.Count; i++)
                    {
                        QuadTreeLeaf<T> qtl = items[i];
                        if (qtl.LeafObject.Equals(obj))
                        {
                            items.RemoveAt(i);
                            return true;
                        }
                    }
                }
                else
                {
                    QuadTreeNode<T> node = GetChild(pt);
                    if (node != null)
                    {
                        return node.RemoveNode(pt, obj);
                    }
                }
                return false;
            }
            public int GetNode(Extents3d ext, ref List<T> nodes)
            {
                Point2d p0 = new Point2d(ext.MinPoint.X, ext.MinPoint.Y);
                Vector3d vt = ext.MaxPoint - ext.MinPoint;
                //Rect rect = new Rect(p0, new Point2d(vt.X, vt.Y));
                if (branch is null)
                {
                    foreach (QuadTreeLeaf<T> item in items)
                    {
                        if (ext.Contains(item.Pos))
                        {
                            nodes.Add(item.LeafObject);
                        }
                    }
                }
                else
                {
                    for (int i = 0; i < branch.Length; i++)
                    {
                        if (branch[i].ext.Overlaps(ext))
                            branch[i].GetNode(ext, ref nodes);
                    }
                }
                return nodes.Count;
            }
            public List<T> GetNode(Extents3d ext)
            {
                List<T> nodes = new List<T>();
                GetNode(ext, ref nodes);
                return nodes;
            }
            /// <summary>
            /// 根据坐标得到坐标附近节点的数据
            /// </summary>
            /// <param name="pos"></param>
            /// <param name="ShortestDistance">离坐标最短距离</param>
            /// <param name="list"></param>
            /// <returns></returns>
            public int GetNodeRecRange(Point3d pos, double ShortestDistance, ref List<T> list)
            {
                double distance;
                if (branch is null)
                {
                    foreach (QuadTreeLeaf<T> leaf in items)
                    {
                        distance = (pos - leaf.Pos).Length;

                        if (distance < ShortestDistance)
                        {
                            list.Add(leaf.LeafObject);
                        }
                    }
                }
                else
                {
                    for (int i = 0; i < branch.Length; i++)
                    {
                        double childDistance = branch[i].ext.PointToExtentsDistance(pos);
                        if (childDistance < ShortestDistance * ShortestDistance)
                        {
                            branch[i].GetNodeRecRange(pos, ShortestDistance, ref list);
                        }
                    }
                }
                return list.Count;
            }
            public List<T> GetNodeRecRange(Point3d pos, double ShortestDistance)
            {
                List<T> list = new List<T>();
                int n = GetNodeRecRange(pos, ShortestDistance, ref list);
                return list;
            }
        }

        public static class EX
        {
            public static List<Extents3d> Split4(this Extents3d ext)
            {
                var x1 = ext.MinPoint.X;
                var x2 = ext.MaxPoint.X;
                var y1 = ext.MinPoint.Y;
                var y2 = ext.MaxPoint.Y;
                var xm = x2 / 2 + x1 / 2;
                var ym = y2 / 2 + y1 / 2;
                Extents3d ext1 = new Extents3d(new Point3d(x1, y1, 0), new Point3d(xm, ym, 0));
                Extents3d ext2 = new Extents3d(new Point3d(x1, ym, 0), new Point3d(xm, y2, 0));
                Extents3d ext3 = new Extents3d(new Point3d(xm, ym, 0), new Point3d(x2, y2, 0));
                Extents3d ext4 = new Extents3d(new Point3d(xm, y1, 0), new Point3d(x2, ym, 0));

                return [ext1, ext2, ext3, ext4];
            }
            public static bool Contains(this Extents3d ext, Point3d pt)
            {
                return pt.X >= ext.MinPoint.X && pt.X <= ext.MaxPoint.X && pt.Y >= ext.MinPoint.Y && pt.Y <= ext.MaxPoint.Y;

            }
            public static bool Overlaps(this Extents3d ext, Extents3d other)
            {
                return other.MaxPoint.X > ext.MinPoint.X && other.MinPoint.X < ext.MaxPoint.X
                    && other.MaxPoint.Y > ext.MinPoint.Y && other.MinPoint.Y < ext.MaxPoint.Y;
            }
            public static Point3d PointToNormalized(Extents3d rectangle, Point3d point)
            {
                return new Point3d(
                    InverseLerp(rectangle.MinPoint.X, rectangle.MinPoint.X, point.X),
                    InverseLerp(rectangle.MinPoint.X, rectangle.MaxPoint.Y, point.Y),
                    0);
            }
            public static double PointToExtentsDistance(this Extents3d ext, Point3d pos)
            {
                double xdisance;
                double ydisance;

                if (ext.MinPoint.X <= pos.X && pos.X <= ext.MaxPoint.X)
                {
                    xdisance = 0;
                }
                else
                {
                    xdisance = Math.Min((Math.Abs(pos.X - ext.MaxPoint.X)), Math.Abs(pos.X - ext.MinPoint.X));
                }

                if (ext.MinPoint.Y <= pos.Y && pos.Y <= ext.MaxPoint.Y)
                {
                    ydisance = 0;
                }
                else
                {
                    ydisance = Math.Min(Math.Abs(pos.Y - ext.MaxPoint.Y), Math.Abs(pos.Y - ext.MinPoint.Y));
                }

                return xdisance * xdisance + ydisance * ydisance;
            }
            public static double InverseLerp(double a, double b, double value)
            {
                if (a != b)
                {
                    return Clamp01((value - a) / (b - a));
                }

                return 0f;
            }
            public static double Lerp(double a, double b, double t)
            {
                return a + (b - a) * Clamp01(t);
            }
            public static double Clamp01(double value)
            {
                if (value < 0)
                {
                    return 0;
                }

                if (value > 1)
                {
                    return 1;
                }

                return value;
            }

        }
}