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

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.SelIds(out List<ObjectId> ids, selRec.GetPointCollection(), fil))
        return;
    //选取种子集
    if (!Env.Editor.GetEnts(out List<Entity> entsTemp, msg: "请选择要基准集:", fil: fil))
        return;

    //种子集四叉树数据
    var oneGrop = new List<CadEntity>();
    for (int i = entsTemp.Count - 1; i >= 0; i--)
    {
        var ent = entsTemp;
        var cadEnt = new CadEntity(ent.ObjectId, ent.GetRect());
        oneGrop.Add(cadEnt);
    }
    // 种子集外包
    var rectStart = oneGrop.GetCesRect();
    // 参考种子
    var ceSeed = oneGrop[0];
    // 种子集相同的类似集
    var oneSameGrop = new List<List<CadEntity>> { oneGrop };

    //创建一个CAD进度条
    using var pm = new ProgressMeter();
    //添加提示语言
    pm.Start($"正在构建{ids.Count}条四叉树数据...");
    //设置总进度
    pm.SetLimit(ids.Count);
    //构造四叉树数据
    var treeRoot = new QuadTree<CadEntity>(AppX.InfoRect);
    //参考种子集
    var cesSeed = new List<CadEntity>();

    for (int i = ids.Count - 1; i >= 0; i--)
    {
        pm.MeterProgress();
        var id = ids;
        var ent = id.GetObject<Entity>();
        if (ent==null)
            continue;
        var cadEnt = new CadEntity(id, ent.GetRect())
        {
            IsUsed = false,
            IsSeed = false
        };
        if (ceSeed.IsSameEnt(cadEnt))
        {
            cadEnt.IsSeed = true;
            cesSeed.Add(cadEnt);
        }
        treeRoot.Insert(cadEnt);
    }
    pm.Stop();
   
    // #region 原始方案
    // //查找相同种子集
    // treeRoot.ForEach(nodes =>
    // {
    //     foreach (var ceTemp in nodes.Contents)
    //     {
    //         if (!ceTemp.IsGetRect(out Rect recTemp,ceSeed,rectStart))
    //             continue;
    //         // 用相对外包搜索实体
    //         var oneGropTemp = treeRoot.Query(recTemp.Expand(10), QuadTreeSelectMode.Contains);
    //         if (!oneGropTemp.Any())
    //             continue;
    //         //过滤掉与种子集不同的实体
    //         var cesSearchTemp = new List<CadEntity>();
    //         foreach (var ceOld in oneGrop)
    //         {
    //             foreach (var ceNew in oneGropTemp)
    //             {
    //                 if (!ceNew.IsUsed && ceNew.IsSameEnt(ceOld))
    //                     cesSearchTemp.Add(ceNew);
    //             }
    //         }
    //
    //         // 与种子集数目相同时看为一组
    //         if (cesSearchTemp.Count != oneGrop.Count)
    //             continue;
    //         var oneSame = new List<CadEntity>();
    //         foreach (var ce in cesSearchTemp)
    //         {
    //             oneSame.Add(ce);
    //             ce.IsUsed = true;
    //         }
    //         oneSameGrop.Add(oneSame);
    //     }
    //     return
    //         false;
    // });
    // #endregion

    #region 新方案
   
    //添加提示语言
    pm.Start($"正在查找{cesSeed.Count}条可能相同的数据...");
    //设置总进度
    pm.SetLimit(cesSeed.Count);
    //根据种子ceSeed查找相同种子集
    for (int i = cesSeed.Count - 1; i >= 0; i--)
    {
        pm.MeterProgress();
        var ceTemp = cesSeed;
        if (!ceTemp.IsGetRect(out Rect recTemp, ceSeed, rectStart))
            continue;
        // 用相对外包搜索实体
        var oneGropTemp = treeRoot.Query(recTemp.Expand(10), QuadTreeSelectMode.Contains);
        if (!oneGropTemp.Any())
            continue;
        //过滤掉与种子集不同的实体
        //与种子集可能相同的集
        var cesSearchTemp = new List<CadEntity>();
        for (int j = oneGrop.Count - 1; j >= 0; j--)
        {
            var ceOld = oneGrop[j];
            for (int k = oneGropTemp.Count - 1; k >= 0; k--)
            {
                var ceNew = oneGropTemp[k];
                if (!ceNew.IsUsed && ceNew.IsSameEnt(ceOld))
                    cesSearchTemp.Add(ceNew);
            }
        }
        
        // 与种子集数目相同时看为一组
        if (cesSearchTemp.Count != oneGrop.Count)
            continue;
        var oneSame = new List<CadEntity>();
        foreach (var ce in cesSearchTemp)
        {
            oneSame.Add(ce);
            ce.IsUsed = true;
        }
        oneSameGrop.Add(oneSame);
    }
    pm.Stop();

    #endregion
   

    //  种子集块
    var blkName = "HesiBlk_" + DateTime.Now.ToString("yyyyMMdd_HHmmss");
    var btrId = entsTemp.MakeBlock(blkName);
    //插入块并删除相似集
    //添加提示语言
    pm.Start($"正在插入{oneSameGrop.Count}个图块...");
    //设置总进度
    pm.SetLimit(oneSameGrop.Count);
    oneSameGrop.ForEach(oneSameEs =>
    {
        pm.MeterProgress();
        var pt = GetCesRect(oneSameEs).CenterPoint.Point3d();
        var bId = tr.CurrentSpace.InsertBlock(pt.Ucs2Wcs(), btrId);
        if (bId.GetObject<Entity>() is not BlockReference brf)
            return;
        brf.Layer = "0";
        brf.Draw();
        oneSameEs.ForEach(x => x.ObjectId.GetObject<Entity>()?.ForWrite(e => e.Erase(true)));
    });
    pm.Stop();
   
    Env.Editor.WriteMessage($"\n共插入{oneSameGrop.Count}个图块！");
}

private class CadEntity(ObjectId objectId, Rect box) : QuadEntity(box)
{
    /// <summary>
    /// ObjectId
    /// </summary>
    public readonly ObjectId ObjectId = objectId;

    /// <summary>
    /// 是否已经用过
    /// </summary>
    public bool IsUsed;

    /// <summary>
    /// 是否种子
    /// </summary>
    public bool IsSeed;

    /// <summary>
    /// 大小比对
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public int CompareTo(CadEntity? other)
    {
        if (other == null)
            return -1;
        return GetHashCode() ^ other.GetHashCode();
    }

    public override int GetHashCode()
    {
        return (base.GetHashCode(), objectId.GetHashCode()).GetHashCode();
    }

    /// <summary>
    /// 判断外包大小是否相等
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    private bool IsSameSize(CadEntity other)
    {
        if (ObjectId.Equals(other.ObjectId))
            return false;
        if (Width.IsEqual(other.Width) && Height.IsEqual(other.Height))
            return true;
        return false;
    }

    /// <summary>
    /// 判断两实体是否相同
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public bool IsSameEnt(CadEntity other)
    {
        if (!IsSameSize(other))
            return false;
        var entL = ObjectId.GetObject<Entity>();
        var entR = other.ObjectId.GetObject<Entity>();
        if (entR != null && entL != null && entL.IsSameEnt(entR))
            return true;
        return false;
    }
}
/// <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);
}


/// <summary>
/// 根据nRect中的某一个种子nCe是否成功获取到新的相对Rect
/// </summary>
/// <param name="nCe">种子</param>
/// <param name="nRect">新得的Rect</param>
/// <param name="oCe">原始种子</param>
/// <param name="oRect">原始Rect</param>
/// <returns></returns>
private static bool IsGetRect(this CadEntity nCe, out Rect nRect, CadEntity oCe, Rect oRect)
{
    nRect = oRect;
    if (!nCe.IsSeed)
        return false;
    if (nCe.IsUsed)
        return false;
    var vec = nCe.CenterPoint - oCe.CenterPoint;
    nRect = new Rect(oRect.MinPoint + vec, oRect.MaxPoint + vec);
    return true;
}

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

你有种再说一遍

dcl1214 发表于 2024-8-20 10:18
Lisp没法多线程，但是，lisp可以借助其他语言多线程，lisp将整个dwg上传上去，服务器端启动多线程，比如说1 ...

多线程要注意很多东西的,
基本需要推翻原本的单线程方案的众多想法,
着重注意锁粒度/cache miss/偷懒线程等等,
如果是发送文件这种多线程还在IO密集,
而图形学上面的处理才是CPU密集计算,
可谓是性能的两道线,
还是换到c#/c++干吧,不然还是缺少适当的训练.
别的不说,难道处理十万图元不想跑到毫秒级吗?

dcl1214

Lisp没法多线程，但是，lisp可以借助其他语言多线程，lisp将整个dwg上传上去，服务器端启动多线程，比如说100个人同时上传dwg，服务器端每个dwg启动10个线程，瞬间就是200个线程跑，负责将100个用户的dwg分析并返回给lisp，我们经常做类似的开发，我们客户都是集团的，下属很多分公司同时请求服务器，lisp只是负责发送dxf或者是数据，或者是dwg，都可以，具体看如何开发了

软件的注册授权，也顺带就做好了，非法用户，不返回数据给lisp

dcl1214

直线端点在相同点上，根据这个直接分组即可

几年前随手写的代码 相同项分组 - AutoLISP/Visual LISP 编程技术 - AutoCAD论坛 - 明经CAD社区 - Powered by Discuz! (mjtd.com)


如果直线端点处有误差，构建数据的时候加容差即可，这个代码是随便写的，应该还能提速300%甚至更高

liuhe

能不能改改 代码的背景色，这是编译器，弄个深色背景啥都看不清楚

wang2006zhi

dcl1214 发表于 2024-8-19 12:59
直线端点在相同点上，根据这个直接分组即可

几年前随手写的代码 相同项分组 - AutoLISP/Visual LISP 编 ...

种子集随意。。不一定线相连，可以任意实体

你有种再说一遍

没看到速度有什么差异啊,怎么不去想并行化呢?

wang2006zhi

你有种再说一遍 发表于 2024-8-19 19:41
没看到速度有什么差异啊,怎么不去想并行化呢?

不知道并行是否你口中的多线程，还不会，最好来一段Demo

你有种再说一遍

wang2006zhi 发表于 2024-8-19 21:02
不知道并行是否你口中的多线程，还不会，最好来一段Demo

并行必然多线程...去搜搜吧

dcl1214

你有种再说一遍 发表于 2024-8-20 18:12
多线程要注意很多东西的,
基本需要推翻原本的单线程方案的众多想法,
着重注意锁粒度/cache miss/偷懒线 ...

我们用go语言很多年了