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;elsereturn 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);}elsereturn 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;}}
}