魔改系列-4填充边界算法和外轮廓边界算法
本帖最后由 你有种再说一遍 于 2024-3-9 19:25 编辑cad的bo算法它本质上是填充算法.填充算法只有两种,一种叫种子填充算法,一种叫扫描线算法,而查找封闭区也是同一个问题.
长期以来,我都觉得cad的bo太慢了,所以我一直想对其重写,试过很多算法,之前博客的左旋和染色,发现有缺陷.
左旋法的缺点,"囙"字,一直左旋也得到"凹",要引入广度优先算法和深度优先算法(不好).而且无法分析孤岛.染色法也一样,遇到多节点岔路时候存在相同问题.
这样的话,"图节点"算法需要抛弃了,所以我们需要使用扫描线算法.
它能算多个分离的:口 口 口
也能算合并的:口二口二口
也能算孤岛的:囙回
它真的很快,不需要并行都能秒出全图所有封闭区,是一些PCB软件的基本功能.
全部流程:
第一步, 消重
第二步, 循环剪枝
第三步, 横扫,竖扫,并组
第四步, 模拟填充,分析面积提取外边界
开始分析:
我先说核心,第三步,横扫:
扫描线算法的本质是横轴求交点,排序交点具备有序性,有序性可以做什么?可以进行对边配对.
0x01,什么叫对边配对?面域(封闭区域)等于一个人,一颗子弹从前胸进入必然从后背穿出,因此面域交点必然是两两配对的.
0x02,因为有0x01的性质,一条横向参照线就是子弹,和这行每个图元求交点,交点们x排序后,按照xa-xb,xc-xd,xe-xf画线,然后不断修改xline.Y+=0.1,接着求交再画下一次的线,这就是模拟填充算法.
0x03,那么封闭区求法怎么才能不跟填充一样密集计算0.1步进呢?如何降低运算量?
图形:□▽,如果在minX位置横切一刀会得到了3个交点(奇数),□△同理.这上下两刀算一个面域,会浪费时间不是吗?
所以要算中点,在中间横切一刀就是最简单的!中点的目的就是为了利用y进行步进,而不是0.1步进.但是中间横切一刀得到的交点们,也可能存在端点(你故意画个小三角呢),因此你还需要求交点之后剔除同一行扫描图元的端点们,并且进行交点排序消重(重叠图元问题).
0x04,并组,获得填充封闭区:
上面求到交点有什么用?交点是没啥用的(除了模拟填充),但是交点击中的图元有用.
图形:口,横扫交点分别是ab(左右).竖扫是cd(下上).
交点的图元需要有一个面域链表,这样才能加入对边.
class Bo{
ObjectId id;
List<ObjectId> Link;//面域环表
}
boEntityA.Link.Add(boEntityB);
boEntityB.Link=boEntityA.Link;
这个Link(a+b)虽然在一个面域内,但此时拐点没关联啊?它们无法闭环得到一个封闭区呀.因此需要引入竖扫得到Link(c+d).
横扫和竖扫(可以并行的,因为它是一行一列分别求交,这个特性使得它运算非常快)
横扫每组头尾点分别搜一次竖扫的头尾点,把竖扫的Link加入过来,这就是拐点关联了,也就是完成了封闭区查找!!
拐点是可能存在多个(外边界问题),但是竖扫也需要排序消重点,因此是具备唯一性,保证了填充边界的正确.
外边界问题:
图形L\7,这样横扫有abc三个交点呢,是奇数.
答案是:看一次cad的填充,最后交点再生成的一个虚拟点成为偶数,然后填充0宽边界(挺变态的,我们也可以不按照cad做法,只填充前面部分,所以扫描线算法是失去旋转性的)
填充边界就是谁先连线就谁先封闭.而外边界分析,只能查关联点的时候进行面积比较,留下大的部分.
全部封闭区:
有没有想过,xa-xb,xc-xd,xe-xf...这个操作并不是全部封闭区?只是刚开始树立了一个间隔填充算法给你?
不然你试试五芒星,会发现星星中间没有填充也是面域哦.因此填充边界组成的边界仍可能具备闭环性.
因此我们还需要xb-xc,xd-xe..看看它们是否具备闭环关系.
第二步:
图形:口口_|,这样横切一刀时候,发现末尾多了一个交点,并且影响判断,这样图形就是多了分支,因此需要剪枝:可以看见有一个节点悬空,进行循环删除.删除之后就只有"口口"了(连_也删了哦)
第一步:
其实不需要消重,因为消重也是求交,扫描线也是求交,扫完之后剔除重复交点就好了.
但是写都写了,保留这个图元消重算法吧:
获取选区图元进行两两求交.
无交点:可能是无限个,需要端点判断,判断后有交点则进入有交点环节.
有交点:打断全部图元,直断选择一边保留即可.
重合情况:
a:直线重合:包围盒完全相同,直线删剩一条.
部分重合就计算端点--
b:曲线重合:包围盒完全相同,采样份>3,逐一比较,完全一致就删剩一条.
部分重合就计算端点--
(为什么要>3,因为样条曲线3点和圆弧3点的包围盒和采样是一致的,但是图形不一致)
曲线重合不需要判断长度一样(因为耗时)只需要通过曲线定份函数得到很多采样点,排序,两个点集一一对应,就是满足重合性也满足长度一致性.(还可以用simd指令优化速度).
部分重合计算端点--如果a1端点和b线碰撞&&b1端点和a线碰撞,则可能存在直断(曲线凸起就不重合),或者a2&&b2端点条件.两线两点碰撞之后,获取两条中间段,我们再对中间段曲线采样分析,是否保留...
全图两两求交时间太慢,还记得我上一文章的快速碰撞方法吗?然后再进行碰撞组内的两两比较.
在ifox上面有个curve.ToCompositeCurve3d()函数的对象可以求曲线交点,打断它们得到碎线.
顺带一提,转为这个cc3d求交也很快(因为模拟填充是0.1步进所以我知道).
不管你这一步怎么做,都得出全部无碰撞碎线在内存里面.
我来猜想一下cad的bo为什么慢?
你会看见bo命令是需要可见即可得的.
遇到块裁剪边界它会打开显示,而不是块表获取图元运算,这说明了这是它在利用界面缓存进行种子填充算法,不断利用种子生长逼近边界.
然后当前可见屏幕部分可能导致块裁剪部分重叠,打开了每个块边界进行重绘,再进行布尔,这一步是需要把当前画面像素全部复制一次比较的.
鉴于实现太复杂了,有些人喜欢看代码,那就看在我博客这里看吧
https://www.cnblogs.com/JJBox/p/12571436.html#_label7
二惊还是那么无敌是多么的寂寞 sieben 发表于 2024-3-27 10:35
感谢大佬分享！我到你博客宝贝代码，还少JoinBoxAcad命名空间空间的代码，大佬有在其他地方贴出来吗？或者 ...
电脑坏掉了,没修,都是手机复制粘贴gitee的片段出来...
CurveInfo只是rect+id...而且我代码貌似没有写得比概念吻合,所以概念才是最重要的 你有种再说一遍 发表于 2024-3-27 20:00
电脑坏掉了,没修,都是手机复制粘贴gitee的片段出来...
CurveInfo只是rect+id...而且我代码貌似没有写得 ...
就如大佬你说的，概念太复杂，有人（又笨又懒的我）喜欢看代码；
感谢大佬的回复，后面再多到大佬的博客学习！ 怎么办，我就第一句看懂了 伊江痕 发表于 2024-3-5 09:59
怎么办，我就第一句看懂了
怎么办，我就看懂你说的了，哈哈
怎么办我只能看懂评论区的..哼哼 思路不错，学习了 看了两遍还是没看懂... 又看了一遍，懂了第二句话了。 哎 字都认识 没有配图，差评