查找相同的种子集-四叉树示例

你有种再说一遍

dcl1214 发表于 2024-8-21 07:22
我们用go语言很多年了

go还不够,图形学不能绕过SIMD

wang2006zhi

你有种再说一遍 发表于 2024-8-19 21:21
并行必然多线程...去搜搜吧

这个么
Parallel.ForEach(list,e =>{});

wang2006zhi

采用线程查找计算相同样本集合，，与插块（费时较多）

[CommandMethod("W_TKPL")]
    public static void BlockSame()
    {
        using var tr = new DBTrans();

        if (!Env.Editor.GetSelRect(out Rect selRec))
            return;
        //过滤块实体
        var fil = OpFilter.Build(e => e.Dxf(0) != "INSERT");
        if (!Env.Editor.SelEnts(out List<Entity> ents, selRec.GetPointCollection(), fil))
            return;
        //选取种子集
        if (!Env.Editor.GetEnts(out List<Entity> entsTemp, msg: "请选择要基准集:", fil: fil))
            return;
        // 种子
        var ceSeed = new CadEntity(entsTemp[0].ObjectId, entsTemp[0].GetRect());
        // 样本集
        var oneGrop = new List<CadEntity>();
        foreach (var ent in entsTemp)
        {
            var cadEnt = new CadEntity(ent.ObjectId, ent.GetRect());
            cadEnt.IsUsed = true;
            oneGrop.Add(cadEnt);
        }
        
        //构造种子集
        var cesSeed = new List<CadEntity>();
        //构造四叉树
        var treeRoot = new QuadTree<CadEntity>(AppX.InfoRect);
        //获取四叉树数据及种子集
        for (int i = ents.Count - 1; i >= 0; i--)
        {
            var ent = ents;
            var cadEnt = new CadEntity(ent.ObjectId, ent.GetRect())
            {
                IsUsed = false,
            };
            if (cadEnt.IsSameEnt(ceSeed))
                cesSeed.Add(cadEnt);
            treeRoot.Insert(cadEnt);
        }
        
        //线程任务查找相同种子集合
        Task<List<List<CadEntity>>> runTask = Task.Run(() => cesSeed.FindGroup(ceSeed,treeRoot,oneGrop));
        var result = runTask.Result;
        InsertBlocks(result);
        Env.Editor.WriteMessage($"\n 已完成{result.Count}个块添加");
        
        void InsertBlocks(List<List<CadEntity>> list)
        {
            // 样本集块
            var btrId = entsTemp.MakeBlock("HesiBlk_" + DateTime.Now.ToString("yyyyMMdd_HHmmss"));
            var max = list.Count;
            //创建一个CAD进度条
            var pm = new ProgressMeter();
            //添加提示语言
            pm.Start($"正在插入{max}图块...");
            //设置总进度
            pm.SetLimit(max);
            for (int i = max - 1; i >= 0; i--)
            {
                pm.MeterProgress();
                var oneSameEs = list;
                if (oneSameEs == null || !oneSameEs.Any())
                    return;
                var pt = GetCesRect(oneSameEs).CenterPoint.Point3d();
                var bId = DBTrans.GetTop(btrId.Database).CurrentSpace.InsertBlock(pt, btrId);
                if (bId.GetObject<BlockReference>() is not { } brf)
                    return;
                brf.Layer = "0";
                brf.Draw();
                oneSameEs.ForEach(x => x.ObjectId.GetObject<Entity>()?.ForWrite(e => e.Erase(true)));
            }
            pm.Stop();
        }
    }
   
    /// <summary>
    /// 查找相同样本
    /// </summary>
    /// <param name="cesTemp">种子集</param>
    /// <param name="ceSeed">参考种子</param>
    /// <param name="treeRoot">四叉树数据</param>
    /// <param name="oneGrop">样本集</param>
    /// <returns></returns>
    static List<List<CadEntity>> FindGroup(this List<CadEntity> cesTemp,
        CadEntity ceSeed,
        QuadTree<CadEntity> treeRoot,
        List<CadEntity> oneGrop)
    {
       //样本集一起外包。。相比与每个实体两点构造两个外包搜索快
        var oRect = oneGrop.GetCesRect();
        // 样本集相同的集
        var oneSameGropTemp = new List<List<CadEntity>>(){oneGrop};
        //遍历所有种子集合，不可避免的多重循环，小循环写在最外层相比与内部节约时间
        for (int i = cesTemp.Count - 1; i >= 0; i--)
        {
            //临时种子与种子相对关系
            var vec = cesTemp.CenterPoint - ceSeed.CenterPoint;
            var nRect = new Rect(oRect.MinPoint + vec, oRect.MaxPoint + vec);
            // 用相对外包搜索实体
            var cesSearchTemp = treeRoot.Query(nRect.Expand(2), QuadTreeSelectMode.Contains);
            if (!cesSearchTemp.Any())
                continue;
            //临时样本集
            var oneGropTemp = new List<CadEntity>();
            //过滤掉与样本集不同的实体
            //遍历样本集
            for (int k = oneGrop.Count - 1; k >= 0; k--)
            {
                var ceK = oneGrop[k];
                //遍历搜索集中的可能实体
                for (int j = cesSearchTemp.Count - 1; j >= 0; j--)
                {
                    var ceJ = cesSearchTemp[j];
                    if (!ceJ.IsUsed && ceJ.IsSameEnt(ceK))
                    {
                        oneGropTemp.Add(ceJ);
                        ceJ.IsUsed = true;
                    }
                }
            }
            // 与种子集数目相同时看为一组
            if (oneGropTemp.Count != oneGrop.Count)
                continue;
            oneSameGropTemp.Add(oneGropTemp);
        }
        return oneSameGropTemp;
    }
   
    /// <summary>
    /// 获取集合的边界
    /// </summary>
    /// <param name="ces">四叉树数据集</param>
    /// <returns></returns>
    private static Rect GetCesRect(this List<CadEntity> ces)
    {
        var xMin = ces.Min(x => x.X);
        var yMin = ces.Min(x => x.Y);
        var tMax = ces.Max(x => x.Top);
        var rMax = ces.Max(x => x.Right);
        return new Rect(xMin, yMin, rMax, tMax);
    }