直线首尾连接-四叉树版

wang2006zhi · 发表于 2024-8-6 12:23:50

本帖最后由 wang2006zhi 于 2025-2-14 12:03 编辑

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

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

gzxl · 发表于 2025-2-16 00:47:29

以像皮的图。我写的结果是：

以直线连接容差 0.05m 测试
共采集 131154 条直线，用时 32 毫秒
共有 131154 条直线参与即将连接，用时 78 毫秒
全图直线连接(含绘制多段线)用时 563 毫秒

您们是多少毫秒。

dcl1214 · 发表于 2024-8-7 14:18:26

本帖最后由 dcl1214 于 2024-8-7 14:44 编辑

①找直线首尾相连还可以用【相同项分组】
②为啥找首尾相连叫四叉树？
③数据库提供了函数：快速查找树形结构
小声说一下，以下这个代码可以对抗反编译

(DEFUN C:DD
(/ a b c dxf ent ents-all ents-rems ents-ssget pts pts2 rc ents
ss)
(SETQ RC 0.05) ;这里设定容差
(SETQ ENT (CAR (ENTSEL)))
(SETQ ENTS-REMS NIL)
(SETQ ENTS-ALL NIL)
(SETQ ENTS (LIST ENT))
(WHILE (SETQ A (CAR ENTS))
(setq dxf nil)
(setq pts nil)
(SETQ ENTS-REMS (CONS A ENTS-REMS))
(SETQ DXF (ENTGET A))
(SETQ PTS
(MAPCAR 'CDR
(VL-REMOVE-IF-NOT
(FUNCTION (LAMBDA (B) (MEMBER (CAR B) (LIST 10 11))))
DXF
)
)
)
(SETQ PTS (LIST (CAR PTS) (LAST PTS)))
(WHILE (SETQ B (CAR PTS))
(setq ss nil)
(setq ENTS-SSGET nil)
(and
rc
(progn
(SETQ SS
(ssget "x"
(list (cons -4 "<or")
(cons -4 "<and")
(cons -4 ">,>,*")
(cons 10 (MAPCAR '- B (LIST RC RC 0)))
(cons -4 "<,<,*")
(cons 10
(MAPCAR '+ B (LIST RC RC 0))
)
(cons -4 "and>")
(cons -4 "<and")
(cons -4 ">,>,*")
(cons 11 (MAPCAR '- B (LIST RC RC 0)))
(cons -4 "<,<,*")
(cons 11
(MAPCAR '+ B (LIST RC RC 0))
)
(cons -4 "and>")
(cons -4 "or>")
)
)
)
(and ss
(progn
(SETQ ENTS-SSGET
(vl-remove-if
(function listp)
(mapcar (function cadr) (ssnamex SS))
)
)
(SETQ SS NIL)
(while (setq c (car ENTS-SSGET))
(setq dxf nil)
(setq PTS2 nil)
(if (MEMBER C ENTS-REMS)
()
(progn
(setq dxf (entget c))
(SETQ PTS2
(MAPCAR
'CDR
(VL-REMOVE-IF-NOT
(FUNCTION
(LAMBDA (B) (MEMBER (CAR B) (LIST 10 11)))
)
DXF
)
)
)
(setq PTS2 (list (car PTS2) (last PTS2)))
(if (vl-some (function (lambda (d)
(<= (distance d b) rc)
)
)
pts2
)
(if (member c ents)
()
(setq ents (append ents (list c)))
)
)
)
)
(setq ENTS-SSGET (cdr ENTS-SSGET))
)
)
)
)
)
(SETQ PTS (CDR PTS))
)
(SETQ ENTS-ALL (CONS A ENTS-ALL))
(SETQ ENTS (CDR ENTS))
)
(and
ENTS-ALL
(progn
(MAPCAR (FUNCTION
(LAMBDA (A) (VLA-PUT-COLOR (VLAX-ENAME->VLA-OBJECT A) 1))
)
ENTS-ALL
)
(REDRAW)
)
)
)

(DEFUN C:DD 
            (/ a b c dxf ent ents-all ents-rems        ents-ssget pts pts2 rc ents 
             ss) 
  (SETQ RC 0.05)                        ;这里设定容差 
  (SETQ ENT (CAR (ENTSEL))) 
  (SETQ ENTS-REMS NIL) 
  (SETQ ENTS-ALL NIL) 
  (SETQ ENTS (LIST ENT)) 
  (WHILE (SETQ A (CAR ENTS)) 
    (setq dxf nil) 
    (setq pts nil) 
    (SETQ ENTS-REMS (CONS A ENTS-REMS)) 
    (SETQ DXF (ENTGET A)) 
    (SETQ PTS 
           (MAPCAR 'CDR 
                   (VL-REMOVE-IF-NOT 
                     (FUNCTION (LAMBDA (B) (MEMBER (CAR B) (LIST 10 11)))) 
                     DXF 
                   ) 
           ) 
    ) 
    (SETQ PTS (LIST (CAR PTS) (LAST PTS))) 
    (WHILE (SETQ B (CAR PTS)) 
      (setq ss nil) 
      (setq ENTS-SSGET nil) 
      (and 
        rc 
        (progn 
          (SETQ        SS 
                 (ssget        "x" 
                        (list (cons -4 "<or") 
                              (cons -4 "<and") 
                              (cons -4 ">,>,*") 
                              (cons 10 (MAPCAR '- B (LIST RC RC 0))) 
                              (cons -4 "<,<,*") 
                              (cons 10 
                                    (MAPCAR '+ B (LIST RC RC 0)) 
                              ) 
                              (cons -4 "and>") 
                              (cons -4 "<and") 
                              (cons -4 ">,>,*") 
                              (cons 11 (MAPCAR '- B (LIST RC RC 0))) 
                              (cons -4 "<,<,*") 
                              (cons 11 
                                    (MAPCAR '+ B (LIST RC RC 0)) 
                              ) 
                              (cons -4 "and>") 
                              (cons -4 "or>") 
                        ) 
                 ) 
          ) 
          (and ss 
               (progn 
                 (SETQ ENTS-SSGET 
                        (vl-remove-if 
                          (function listp) 
                          (mapcar (function cadr) (ssnamex SS)) 
                        ) 
                 ) 
                 (SETQ SS NIL) 
                 (while        (setq c (car ENTS-SSGET)) 
                   (setq dxf nil) 
                   (setq PTS2 nil) 
                   (if (MEMBER C ENTS-REMS) 
                     () 
                     (progn 
                       (setq dxf (entget c)) 
                       (SETQ PTS2 
                              (MAPCAR 
                                'CDR 
                                (VL-REMOVE-IF-NOT 
                                  (FUNCTION 
                                    (LAMBDA (B) (MEMBER (CAR B) (LIST 10 11))) 
                                  ) 
                                  DXF 
                                ) 
                              ) 
                       ) 
                       (setq PTS2 (list (car PTS2) (last PTS2))) 
                       (if (vl-some (function (lambda (d) 
                                                (<= (distance d b) rc) 
                                              ) 
                                    ) 
                                    pts2 
                           ) 
                         (if (member c ents) 
                           () 
                           (setq ents (append ents (list c))) 
                         ) 
                       ) 
                     ) 
                   ) 
                   (setq ENTS-SSGET (cdr ENTS-SSGET)) 
                 ) 
               ) 
          ) 
        ) 
      ) 
      (SETQ PTS (CDR PTS)) 
    ) 
    (SETQ ENTS-ALL (CONS A ENTS-ALL)) 
    (SETQ ENTS (CDR ENTS)) 
  ) 
  (and 
    ENTS-ALL 
    (progn 
      (MAPCAR (FUNCTION 
                (LAMBDA (A) (VLA-PUT-COLOR (VLAX-ENAME->VLA-OBJECT A) 1)) 
              ) 
              ENTS-ALL 
      ) 
      (REDRAW) 
    ) 
  ) 
)

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
能否有启发？

账号		自动登录	找回密码
密码			注册

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

本帖子中包含更多资源

浏览过的版块