直线首尾连接-四叉树版

你有种再说一遍

dcl1214 发表于 2024-8-10 08:28
你知道啥叫相同项？而且数据库提供sql语句处理这种，我只是用lisp的最简单方法实现了这个，类似这种的数 ...

你说说什么是相同项?点集能是相同项?能容差查询?
它用啥构成?Map?树?查询的时间复杂度是多少?

说了半天cad缓存就是八叉树了

dcl1214

你有种再说一遍 发表于 2024-8-10 10:01
你说说什么是相同项?
点集能是相同项?能容差查询?
它用啥构成?Map?树?

加载vlx后输入swxl测试一下速度

你有种再说一遍

dcl1214 发表于 2024-8-10 10:12
加载vlx后输入swxl测试一下速度

要等楼主测它的图才行,而且电脑配置也不同,他另一个帖子10w线的原生ssget特化之后有700ms,用四叉树反而更高,因为是涵盖了构造时间,要1500ms

橡皮

dcl1214 发表于 2024-8-10 10:12
加载vlx后输入swxl测试一下速度

我想知道里边做那哪些操作，只是简单得找和拾取得线相连接的线吗？如果只是简单得找连接线为啥要1秒甚至几秒啊

你有种再说一遍

我知道你写的慢在哪里了,每个点都生成了矩形去选择一次,
其实无碰撞的可以直接跳过.
同一台电脑的十万随机图元的四叉树碰撞187ms,
SAP算法74ms,如果加上多线程,估计能压缩到20ms左右,
SAP就是对包围盒进行排序,因为有序数组是区间判断的,
划分区间之后在区间进行多线程.

而你四叉树时间怎么那么多呢?因为你是采用递归.
在数据量巨大的时候,把开辟栈帧的时间也要考虑进去,
写到200ms我就算你及格了.

dcl1214

橡皮 发表于 2024-8-10 16:56
我想知道里边做那哪些操作，只是简单得找和拾取得线相连接的线吗？如果只是简单得找连接线为啥要1秒甚至 ...

我的疑问是四叉树能满足的为啥二叉树不能满足，非要纠结速度，那我就随便修改一句代码，然后上传，你测试速度，我电脑测试是0.06秒，你自己计算提速了多少倍，由于150万个图形对象超过了10M了，论坛不让上传，你自己将复制复制10次左右

我这个代码还有很大的提速空间，这个代码是信手拈来的，由于我工作上用不到这个代码，需要源码就自己反编译，支持你反编译

dcl1214

你有种再说一遍 发表于 2024-8-10 10:01
你说说什么是相同项?点集能是相同项?能容差查询?
它用啥构成?Map?树?查询的时间复杂度是多少?

点集为啥没有容差？
select * from points where px > x1 and px < x2 and py < y1  and py < y2

你有种再说一遍

dcl1214 发表于 2024-8-10 20:54
点集为啥没有容差？
select * from points where px > x1 and px < x2 and py < y1  and py < y2

如果cad用的是map,就不能容差的,也就是没有O(1)了,
二叉树之所以不能满足就是因为它是二维图元啊,
X二叉了,Y怎么办?Z怎么办?
他们也要二叉,是不是就是八叉了.
所以你能分析出来cad就是八叉树O(log8(n))了没.

你的单点链式选择是60ms,然后扩展到全图链条看看,
也就是无论如何你的函数都要调用10w+,
所以你的时间没有随着规模提高而提高就已经有问题了,
lisp开辟栈帧的时间都不止60ms...
一个图元两个点,两次选择,选择是log4(n),
时间复杂度2n*log4(n),
也就是时间会随着图元量增加而倍增,你就是没有感受到这个,我第一次觉得居然有比四叉树还快的大规模筛选就是这个案例.


G大测试你的Lisp代码19w图元是4.4s,一半也是2.2s.
要么你的fas新代码存在原理改变.
不要觉得60ms快,c#还是2ms,仍然处理10w图元太慢了.
我的74ms是全图碰撞的.


不要觉得sql就快,sql从来不考虑cache miss的.

yupeng_dyp

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

用这个代码屏幕内的图元少一点还好，测试十万图元，十分钟过去了还没选出来……

yupeng_dyp

dcl1214 发表于 2024-8-10 20:49
我的疑问是四叉树能满足的为啥二叉树不能满足，非要纠结速度，那我就随便修改一句代码，然后上传，你测试 ...

不好意，用你前面的代码测试确实十多分钟过去也没有选出来，不过用后面发的这个 SWXL.VLX 测试19万线图元确实在 0.06 秒左右