设为首页收藏本站CAD论坛CAD教程CAD下载明经币充值
切换到宽版

明经CAD社区

 找回密码
 注册

QQ登录

只需一步，快速开始

搜索
明经CAD社区»社区 › 开发篇 › AutoCAD.net/VB.net/C# 编程技术 › 直线首尾连接-四叉树版
12345下一页
返回列表 发新帖
查看: 2434|回复: 45

[【IFoxCAD】] 直线首尾连接-四叉树版

[复制链接]
wang2006zhi
发表于 2024-8-6 12:23:50 | 显示全部楼层 |阅读模式
本帖最后由 wang2006zhi 于 2024-8-14 13:27 编辑

[CommandMethod("tt2")]
public void Tt2()
{
    using var tr = new DBTrans();
    var fil = OpFilter.Build(x => x.Dxf(0) == "LINE");
    if (!Env.Editor.SelEnts(out List<Line> lines, fil: fil))
        return;
    var treeRoot = new QuadTree<CadEntity>(AppX.InfoRect);
    foreach (var line in lines)
    {
        if (line is null)
            return;
        var cadEnt = new CadEntity(line, line.GeometricExtents.GetRect());
        treeRoot.Insert(cadEnt);
    }

    while (true)
    {
        var sw = Stopwatch.StartNew();
        if (!Env.Editor.SelEnt(out Line line))
            return;
        var cadEnt = new CadEntity(line, line.GeometricExtents.GetRect());
        var linkIds = new List<Line>();
        DfS(cadEnt, ref linkIds);
        if (!linkIds.Any())
            continue;
        linkIds.ForEach(ent =>
        {
            using (ent.ForWrite())
            {
                ent!.ColorIndex = ent.ColorIndex == 1 ? 2 : 1;
                ent.Draw();
            }
        });
        sw.Stop();
        Env.Editor.WriteMessage("\n TT2用时{0}毫秒", sw.Elapsed.TotalMilliseconds);
    }

    void DfS(CadEntity cadEnt, ref List<Line> linkIds)
    {
        var cadEnts = treeRoot.Query(cadEnt.Expand(0));
        if (!cadEnts.Any())
            return;
        foreach (CadEntity item in cadEnts)
        {
            if (cadEnt.Equals(item))
                continue;
            var lineA = (Line)cadEnt.Entity;
            var lineB = (Line)item.Entity;
            if (linkIds.Contains(lineB))
                continue;
            if (IsLink(lineA, lineB))
            {
                linkIds.Add(lineB);
                DfS(item, ref linkIds);
            }
        }
    }

    bool IsLink(Line lineA, Line lineB)
    {
        var tol = new Tolerance(5, 50);
        if (lineA.StartPoint.IsEqualTo(lineB.StartPoint, tol)
            || lineA.StartPoint.IsEqualTo(lineB.EndPoint, tol)
            || lineA.EndPoint.IsEqualTo(lineB.StartPoint, tol)
            || lineA.EndPoint.IsEqualTo(lineB.EndPoint, tol)
           )
            return true;
        return false;
    }
}
private class CadEntity(Entity ent, Rect box) : QuadEntity(box)
{
    public readonly Entity Entity = ent;

    //这里加入其他字段
public int CompareTo(CadEntity? other)
    {
        if (other == null)
            return -1;
        return GetHashCode() ^ other.GetHashCode();
    }

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


本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？注册

x
回复

使用道具 举报

dcl1214
发表于 2024-8-7 14:18:26 | 显示全部楼层
本帖最后由 dcl1214 于 2024-8-7 14:44 编辑

①找直线首尾相连还可以用【相同项分组】
②为啥找首尾相连叫四叉树？
③数据库提供了函数：快速查找树形结构
小声说一下，以下这个代码可以对抗反编译
  1. (DEFUN C:DD
  2.             (/ a b c dxf ent ents-all ents-rems        ents-ssget pts pts2 rc ents
  3.              ss)
  4.   (SETQ RC 0.05)                        ;这里设定容差
  5.   (SETQ ENT (CAR (ENTSEL)))
  6.   (SETQ ENTS-REMS NIL)
  7.   (SETQ ENTS-ALL NIL)
  8.   (SETQ ENTS (LIST ENT))
  9.   (WHILE (SETQ A (CAR ENTS))
  10.     (setq dxf nil)
  11.     (setq pts nil)
  12.     (SETQ ENTS-REMS (CONS A ENTS-REMS))
  13.     (SETQ DXF (ENTGET A))
  14.     (SETQ PTS
  15.            (MAPCAR 'CDR
  16.                    (VL-REMOVE-IF-NOT
  17.                      (FUNCTION (LAMBDA (B) (MEMBER (CAR B) (LIST 10 11))))
  18.                      DXF
  19.                    )
  20.            )
  21.     )
  22.     (SETQ PTS (LIST (CAR PTS) (LAST PTS)))
  23.     (WHILE (SETQ B (CAR PTS))
  24.       (setq ss nil)
  25.       (setq ENTS-SSGET nil)
  26.       (and
  27.         rc
  28.         (progn
  29.           (SETQ        SS
  30.                  (ssget        "x"
  31.                         (list (cons -4 "<or")
  32.                               (cons -4 "<and")
  33.                               (cons -4 ">,>,*")
  34.                               (cons 10 (MAPCAR '- B (LIST RC RC 0)))
  35.                               (cons -4 "<,<,*")
  36.                               (cons 10
  37.                                     (MAPCAR '+ B (LIST RC RC 0))
  38.                               )
  39.                               (cons -4 "and>")
  40.                               (cons -4 "<and")
  41.                               (cons -4 ">,>,*")
  42.                               (cons 11 (MAPCAR '- B (LIST RC RC 0)))
  43.                               (cons -4 "<,<,*")
  44.                               (cons 11
  45.                                     (MAPCAR '+ B (LIST RC RC 0))
  46.                               )
  47.                               (cons -4 "and>")
  48.                               (cons -4 "or>")
  49.                         )
  50.                  )
  51.           )
  52.           (and ss
  53.                (progn
  54.                  (SETQ ENTS-SSGET
  55.                         (vl-remove-if
  56.                           (function listp)
  57.                           (mapcar (function cadr) (ssnamex SS))
  58.                         )
  59.                  )
  60.                  (SETQ SS NIL)
  61.                  (while        (setq c (car ENTS-SSGET))
  62.                    (setq dxf nil)
  63.                    (setq PTS2 nil)
  64.                    (if (MEMBER C ENTS-REMS)
  65.                      ()
  66.                      (progn
  67.                        (setq dxf (entget c))
  68.                        (SETQ PTS2
  69.                               (MAPCAR
  70.                                 'CDR
  71.                                 (VL-REMOVE-IF-NOT
  72.                                   (FUNCTION
  73.                                     (LAMBDA (B) (MEMBER (CAR B) (LIST 10 11)))
  74.                                   )
  75.                                   DXF
  76.                                 )
  77.                               )
  78.                        )
  79.                        (setq PTS2 (list (car PTS2) (last PTS2)))
  80.                        (if (vl-some (function (lambda (d)
  81.                                                 (<= (distance d b) rc)
  82.                                               )
  83.                                     )
  84.                                     pts2
  85.                            )
  86.                          (if (member c ents)
  87.                            ()
  88.                            (setq ents (append ents (list c)))
  89.                          )
  90.                        )
  91.                      )
  92.                    )
  93.                    (setq ENTS-SSGET (cdr ENTS-SSGET))
  94.                  )
  95.                )
  96.           )
  97.         )
  98.       )
  99.       (SETQ PTS (CDR PTS))
  100.     )
  101.     (SETQ ENTS-ALL (CONS A ENTS-ALL))
  102.     (SETQ ENTS (CDR ENTS))
  103.   )
  104.   (and
  105.     ENTS-ALL
  106.     (progn
  107.       (MAPCAR (FUNCTION
  108.                 (LAMBDA (A) (VLA-PUT-COLOR (VLAX-ENAME->VLA-OBJECT A) 1))
  109.               )
  110.               ENTS-ALL
  111.       )
  112.       (REDRAW)
  113.     )
  114.   )
  115. )


回复 支持 1 反对 0

使用道具 举报

你有种再说一遍
发表于 2024-8-12 15:39:28 | 显示全部楼层
本帖最后由 你有种再说一遍 于 2024-8-12 20:57 编辑
dcl1214 发表于 2024-8-12 15:10
既然你提到了高频查询，这就是数据库的优势了，数据库支持索引法，以及树结构查询，你要查询一根直线的关 ...

计算机没有迷信的,
数据库并没有神奇的能力可以给你瞬间返回,
数据库无非也是Map,二分,多叉树结构,
每种查询都有相应的时间复杂度.

真正的问题不是上面,因为大家都是多叉树,
真正的问题是ssget的执行步骤:
1,进入lisp解析器.
2,进入选择集条件解析器,拆分条件.
3,进入界面显示缓冲区.
4,进入八叉树.
5,再过滤其他条件.
6,聚合元素.
还存在各种边界检查的成本...
如果一次60ms,那么10w次是非常巨大的消耗.

我们多叉树就是二级索引.
这就是为什么我们自己构建四叉树,比自带的树还快.
因为可以减少边界检查,数值类型替换,减少栈帧等加速方案.
即使如此,每次选择仍然要2ms,如果10w次就是200秒.

有序数组比多叉树还要快很多,
CPU对于顺序访问比起跳跃访问是有各种优化的,
例如缓存预读,分支流水线技术.
这就是我为什么经常diss lisp的链表问题,它将导致大量的cache miss.
这里可以看见什么是CPU友好,什么是内存友好,什么是磁盘友好.
这就是为什么高频查询做有序数组更好,因为这是CPU密集任务.
尤其是图形学上面,渲染和缓存命中是比任何一种数据库优化技术还注重性能.
同时有序数组是窗口搜索,线性速度,
也就是n*log(n),比2n*log4(n)快多了

多线程存在锁粒度/伪共享/上下文切换的问题,
并非你单纯认为的能并行查询那么简单,
尤其是数据库讲究取舍,不会像图形学那么极限,
行式数据库和列式数据库的优缺点就非常能说明问题,
你觉得数据库有魅力,
是因为lisp难以自行实现上面的代码,
这就封堵了你对于后面知识点的获取,
例如volatile关键字,内存屏障,锁粒度,并发容器等等...

多线程重点是对数据切割,
能够利用多个核心的寄存器实现并行,
并非无脑使用超越核心数的线程数,
因为它将被转为虚拟线程,然后反复切换线程上下文,
造成大量浪费没必要的时间.

你可以去看看十亿行天文台数据挑战,SQL版本的方案是非常慢的...
写代码总是更灵活的,更能写出一个比cad自身还快的方案.
不然就只会调用cad了...
回复 支持 反对

使用道具 举报

Bao_lai
发表于 2024-8-6 14:12:32 | 显示全部楼层
用了IFox库么？
回复 支持 反对

使用道具 举报

taiwanfox
发表于 2024-8-7 10:58:16 | 显示全部楼层
好東西，謝謝分享，感謝!!!
回复 支持 反对

使用道具 举报

MZ_li
发表于 2024-8-7 14:51:15 | 显示全部楼层
dcl1214 发表于 2024-8-7 14:18
①找直线首尾相连还可以用【相同项分组】
②为啥找首尾相连叫四叉树？
③数据库提供了函数：快速查找树形 ...

很强
回复 支持 反对

使用道具 举报

你有种再说一遍
发表于 2024-8-8 23:11:00 | 显示全部楼层
本帖最后由 你有种再说一遍 于 2024-8-9 00:21 编辑

dcl1214 发表于 2024-8-7 14:18
①找直线首尾相连还可以用【相同项分组】
②为啥找首尾相连叫四叉树？
③数据库提供了函数：快速查找树形 ...



四叉树就是你代码上面的ssget,用来快速筛选.
在c#用四叉树更多是为了避开ssget高低版本的选择差异(低版本无法选择视口外)和扩展到多线程并行化.
与其面临bug不如直接自己实现的思想,有时候放弃使用cad的API其实很有意思.


数据分组的优化思路:
基本上都是MapReduce,也就是先分区,再并行处理每个分区查找共点,最后合并.

数据结构上面选型:
其实如果仅仅是一次性遍历,不如用空间哈希网格,
因为四叉树插入十万图元要200ms,如果不是和其他功能共用最好也不单独做,或者把它缓存起来...
还有更快的方式应该是制作邻接表,
但是你们都在疯狂ssget...

回复 支持 反对

使用道具 举报

dcl1214
发表于 2024-8-9 16:17:37 | 显示全部楼层
你有种再说一遍 发表于 2024-8-8 23:11
dcl1214 发表于 2024-8-7 14:18
①找直线首尾相连还可以用【相同项分组】
②为啥找首尾相连叫四叉树？

相同项分组，无需ssget顺延
回复 支持 反对

使用道具 举报

你有种再说一遍
发表于 2024-8-9 19:00:54 | 显示全部楼层
本帖最后由 你有种再说一遍 于 2024-8-9 19:38 编辑
dcl1214 发表于 2024-8-9 16:17
相同项分组，无需ssget顺延

数数时间复杂度就知道了,
你的代码很难在十万图元跑到2秒内吧.
三个while,
第一个用来做堆O(n),
第二个是图元点集O(n*m),m为点数,直线取2.
第三个是搜索邻近实体,也就是O(n*m*i)你这里的i还是ssget"x"它的条件过滤不是O(1)因为桌子缓存八叉树,所以当它是四叉树O(log4(n)),
并且你还用了mapcar,vl-remove-if又增加了多项(j,k).
平均期望是O(n*m*log4(n)+j+k),最坏O(n^3).

c#的是:
第三个平均期望O(n*m*log4(n)),最坏O(n^3).
还要加入构造四叉树时间.

光看平均好像差不多,
但是lisp是链表不是动态数组,循环还没有break.

c#除了时间复杂度之外的加速方案,
例如把四叉树从double改为float,构造树时间直接快了一倍,搜索树也是,还可以并行搜索,控制缓存命中等等.

回复 支持 反对

使用道具 举报

dcl1214
发表于 2024-8-10 08:28:53 | 显示全部楼层
本帖最后由 dcl1214 于 2024-8-10 08:34 编辑
你有种再说一遍 发表于 2024-8-9 19:00
数数时间复杂度就知道了,
你的代码很难在十万图元跑到2秒内吧.
三个while,

你知道啥叫相同项？而且数据库提供sql语句处理这种，我只是用lisp的最简单方法实现了这个，类似这种的数据分析，都是信手拈来，要时间和效率，不要用lisp，其他语言开启多线程速度快很多（lisp发送直线的dxf祖玛10 11的值即可）

上面发的演示里面，每一个所谓周边的图形线条都是首尾不封闭的，建议所有分堆的图形首尾全封闭测试
回复 支持 反对

使用道具 举报

dcl1214
发表于 2024-8-10 08:55:41 | 显示全部楼层
https://blog.51cto.com/u_16099298/10998682
https://blog.csdn.net/w15558056319/article/details/122046916
能否有启发？
回复 支持 反对

使用道具 举报

12345下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码，在未取得本站及作者授权的情况下，不得用于商业用途

GMT+8, 2024-11-25 06:33 , Processed in 0.181152 second(s), 25 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表