SLdesign V3.0对实体最小面积包容盒的探索
本帖最后由 尘缘一生 于 2025-9-29 22:39 编辑鉴于这个问题的重要性，费点功夫对其测试研究，
请移步以下两技术贴，对照
http://bbs.mjtd.com/thread-172161-1-1.html
http://bbs.mjtd.com/thread-107647-1-1.html
高飞鸟大师的，点表扫描，当然好，那么反过来，有时候我们需要求点的时候，就要用到。
说明：LEE MAC 的程序较慢并写得很难理解，但支持的实体多，那么慢的原因呢，是实体旋转循环取得包容盒，记录角度以便后续用的问题，那么对于旋转180度，并分容差小，造成的，对于180值得推敲，90度是否可以，由于时间问题，没有进行大量测试，另外，对于没有旋转的实体，并没有筛选用正常包容盒部分作，从而不在用这部分执行；另外，对于复制实体，然后删除，我也颇有看法，不复制，采取最后转回来角度，岂不更好吗？当然，这些都值得高手改进吧。
黄大师的哪，速度快，但我测试对标注，一些块不支持
为此，基于LEE MAC的程序进行改写如下（分部）：
;最小面积包围盒------(一级)----
;参数 obj enam 实体 实体名
;返回实体四角点表，分别为：1：左下 2：右下 3：右上 4：左上
(defun sl:ent4pt (obj / an ba bb bm cn cv mb pr 2p 4p)
(if (not pr) (setq pr 0.01)) ;0-1取值
(if (= (type obj) 'ENAME) (setq obj (vlax-ename->vla-object obj)))
(vla-copy obj)
(setq obj (vlax-ename->vla-object (entlast)))
(setq bb (slget-enbox obj))
(setq pr (* pr pi)
cn (mapcar '(lambda (x y) (* (+ x y) 0.5)) (car bb) (cadr bb))
cv (vlax-3d-point cn)
bm (* (- (caadr bb) (caar bb)) (- (cadadr bb) (cadar bb)))
mb (cons 0.0 bb)
an 0
)
(while (< (setq an (+ an pr)) pi)
(vla-rotate obj cv pr)
(setq bb (slget-enbox obj) ba (* (- (caadr bb) (caar bb)) (- (cadadr bb) (cadar bb))))
(if (< ba bm) (setq bm ba mb (cons an bb)))
)
(vla-delete obj)
(setq 2p (cdr mb) 4p (list (list (caar 2p) (cadar 2p)) (list (caadr 2p) (cadar 2p)) (list (caadr 2p) (cadadr 2p)) (list (caar 2p) (cadadr 2p)))
an (- (car mb))
m (list (list (cos an) (sin (- an)) 0.0) (list (sin an) (cos an) 0.0) (list 0.0 0.0 1.0))
cn (mapcar '- cn (mat:mxv m cn))
)
(mapcar (function (lambda (x) (mapcar '+ (mat:mxv m x) cn))) 4p)
)
本帖最后由 你有种再说一遍 于 2025-9-29 17:29 编辑
牛逼确实牛逼,复杂也确实复杂...
最小面积包围盒 = 凸包的最小包围盒;
因为Lisp求凸包麻烦导致要多次旋转采样,只能说这样也想得到也是厉害.
不过添加了多次复制造成效率下降.
其实这个东西可以做得非常快,毕竟OBB包围盒已经被研究很透彻了.
我的:
先求凸包,再通过点乘求左下角旋转轴点minPt,
然后把全部点集绕它旋转,得到右上角的点maxPt.
=>其中一条母边的包围盒.
循环每条边,得到全部包围盒,排序得到最小面积那个.
你会发现
1,可以处理每种图元,曲线采样点集就行.圆形直接AABB得了.
2,点集求凸包用分治法是最快的.
3,凸包的边数限制旋转次数,和你的不断旋转形成效率差异.
4,每个包围盒计算相互不影响,线程细粒度很小=并行高效.
https://www.cnblogs.com/JJBox/p/14284847.html 你有种再说一遍 发表于 2025-9-29 01:16
牛逼确实牛逼,复杂也确实复杂...
最小面积包围盒 = 凸包的最小包围盒;
因为Lisp求凸包麻烦导致要多次旋转 ...
我也多次打开过你的页面，无奈，我只会点lisp。
已知点表的话，就没啥问题了，关键是反过来，要取点的时候，一个问题的两个方面。
感谢分享。 牛逼确实牛逼,复杂也确实复杂... 最近也在研究、测试最小包围盒,说点自己的感受。
楼柱的程序简便清晰，和LEE MAC大师的方法差不多，这个方法最保险，求外框次数多比较慢。
大海@tryhi的二分法求外框次数少速度快，但测试有的复杂的图形或选择集不准确。http://bbs.mjtd.com/thread-172161-1-1.html
借鉴大海的二分法，我尝试采用n分法，速度没怎么减少，精度也没问题，但测试出来也并不是n越大就越准确，跟所选对象复杂情况有关，可能因为最小面积跟角度变量没有很明显的规律。
@Gu_xl的方法对于算样条曲线的最小包围框效果很好。http://bbs.mjtd.com/forum.php?mod=viewthread&tid=189529&fromuid=7329538
高飞鸟大师的经测试求有样条曲线的情况效果很好，但不知为什么有的图形会出错，“; 错误: 参数值错误: AcDbCurve 61”，程序太长了还没仔细读完。
不知道还有没有其他速度快又准确的办法？ 需要遗传算法和二分法，遗传算法求旋转某个角度范围下最小值，二分法继续在这个范围内求最小值。
这个算法其实是有bug的存在的，遗传算法的前提是包围盒的变化趋势的是连续的，也就是角度X和包围盒的面积Y的曲线是处处可导曲线，不存在某个点是突变的。
如果某个点是突变的，且正好是最小值，那遗传算法就有可能得出的只是局部最小值
简单来说，得出的最小值肯定是局部最小值，不一定是最小值。 尘缘一生 发表于 2025-9-29 05:55
我也多次打开过你的页面，无奈，我只会点lisp。
已知点表的话，就没啥问题了，关键是反过来，要取点的时 ...
高飞鸟也写过凸包
http://bbs.mjtd.com/thread-56069-1-1.html
页:
[1]