直线首尾连接-四叉树版
本帖最后由 wang2006zhi 于 2025-2-14 12:03 编辑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();
}
}
本帖最后由 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)
)
)
)
本帖最后由 你有种再说一遍 于 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了...
用了IFox库么？ 好東西，謝謝分享，感謝!!! dcl1214 发表于 2024-8-7 14:18
①找直线首尾相连还可以用【相同项分组】
②为啥找首尾相连叫四叉树？
③数据库提供了函数：快速查找树形 ...
很强 本帖最后由 你有种再说一遍 于 2024-8-9 00:21 编辑
dcl1214 发表于 2024-8-7 14:18
①找直线首尾相连还可以用【相同项分组】
②为啥找首尾相连叫四叉树？
③数据库提供了函数：快速查找树形 ...
四叉树就是你代码上面的ssget,用来快速筛选.
在c#用四叉树更多是为了避开ssget高低版本的选择差异(低版本无法选择视口外)和扩展到多线程并行化.
与其面临bug不如直接自己实现的思想,有时候放弃使用cad的API其实很有意思.
数据分组的优化思路:
基本上都是MapReduce,也就是先分区,再并行处理每个分区查找共点,最后合并.
数据结构上面选型:
其实如果仅仅是一次性遍历,不如用空间哈希网格,
因为四叉树插入十万图元要200ms,如果不是和其他功能共用最好也不单独做,或者把它缓存起来...
还有更快的方式应该是制作邻接表,
但是你们都在疯狂ssget...
你有种再说一遍 发表于 2024-8-8 23:11
dcl1214 发表于 2024-8-7 14:18
①找直线首尾相连还可以用【相同项分组】
②为啥找首尾相连叫四叉树？
相同项分组，无需ssget顺延 本帖最后由 你有种再说一遍 于 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:34 编辑
你有种再说一遍 发表于 2024-8-9 19:00
数数时间复杂度就知道了,
你的代码很难在十万图元跑到2秒内吧.
三个while,
你知道啥叫相同项？而且数据库提供sql语句处理这种，我只是用lisp的最简单方法实现了这个，类似这种的数据分析，都是信手拈来，要时间和效率，不要用lisp，其他语言开启多线程速度快很多（lisp发送直线的dxf祖玛10 11的值即可）
上面发的演示里面，每一个所谓周边的图形线条都是首尾不封闭的，建议所有分堆的图形首尾全封闭测试
https://blog.51cto.com/u_16099298/10998682
https://blog.csdn.net/w15558056319/article/details/122046916
能否有启发？