任意角度或UCS下的物体包围盒

yaokui25 · 发表于 2024-6-20 19:45:36

你有种再说一遍发表于 2024-6-20 19:42
随便去百度抄抄不就有了吗

好的,我去试试

yaokui25 · 发表于 2024-6-20 19:52:09

highflybird 发表于 2024-6-20 19:09
我应该有个计算物体最小面积的包围盒程序。你搜索一下看看。

版主说的是这个?
http://bbs.mjtd.com/thread-66618-1-1.html

highflybird · 发表于 2024-6-20 19:54:30

yaokui25 发表于 2024-6-20 19:52
版主说的是这个?
http://bbs.mjtd.com/thread-66618-1-1.html

不是，是下面的帖子：
最小包围盒和最大距离点对
http://bbs.mjtd.com/thread-81308-1-1.html

yaokui25 · 发表于 2024-6-20 19:57:06

highflybird 发表于 2024-6-20 19:54
不是，是下面的帖子：
最小包围盒和最大距离点对
http://bbs.mjtd.com/thread-81308-1-1.html

好的,谢谢版主
回头好好研究一下

恐怕难度相当大

czb203 · 发表于 2024-6-20 21:58:38

你有种再说一遍发表于 2024-6-20 19:42
随便去百度抄抄不就有了吗

那拜托您来一个

guosheyang · 发表于 2024-6-20 23:21:53

感谢高大师的分享！

尘缘一生 · 发表于 2024-6-20 23:59:32

本帖最后由尘缘一生于 2024-6-21 05:55 编辑

highflybird 发表于 2024-6-20 19:09
我应该有个计算物体最小面积的包围盒程序。你搜索一下看看。

我组织了下子，测试，

1：本贴取得角度办法较快，但面积不是最小的包容:
2：从前 minarearectangle 函数办法较慢，但面积是最小的包容

;;;--------------------------
;;; 功能: 旋转点
;;; 输入: 点p，角度ang
;;; 输出: 中点位置
;;;-------------------------
(defun geo:rotbyangle (p ang / c s)
(setq c (cos ang))
(setq s (sin ang))
(list
(- (* c (car p)) (* s (cadr p)))
(+ (* s (car p)) (* c (cadr p)))
)
)
;;;------------------------
;;; 功能: 沿某一个方向的点集的包围盒
;;; 输入: pts--点集
;;; ang--方向与x轴夹角
;;; 输出: 包围盒点(wcs)
;;;--------------------------
(defun geo:getboxbyset (pts ang / pmin pmax)
(setq pts (mapcar (function (lambda (p) (geo:rotbyangle p (- ang)))) pts))
(setq pmin (apply 'mapcar (cons 'min pts)))
(setq pmax (apply 'mapcar (cons 'max pts)))
(mapcar
(function (lambda (p) (geo:rotbyangle p ang)))
(list
(list (car pmin) (cadr pmin))
(list (car pmax) (cadr pmin))
(list (car pmax) (cadr pmax))
(list (car pmin) (cadr pmax))
)
)
)
;点积(内积):p1p2 p1p3是否垂直，垂直为0;锐角为正，钝角为负 By Highflybird
;;定义向量的点积函数(向量A投影在向量B上的长度，但是它还要乘上B的长度)
(defun dot (p1 p2 p3 / x1 y1)
(setq x1 (car p1)
y1 (cadr p1)
)
(+ (* (- (car p2) x1) (- (car p3) x1))
(* (- (cadr p2) y1) (- (cadr p3) y1))
)
)
;;叉积(外积) By Highflybird
;;1 三角形之倍面积
;;2 p1 p2 p3 逆时针为正。
;;3 三点共线为0
(defun det (p1 p2 p3 / x2 y2)
(setq x2 (car p2) y2 (cadr p2))
(- (* (- x2 (car p3)) (- y2 (cadr p1))) (* (- x2 (car p1)) (- y2 (cadr p3))))
)
;;;========================================
;;;求凸壳直径的参数
;;;参数：逆时针的凸壳 h-------注意逆时针!!!
;;;返回值: (pair ang maxd) ((p1 p2) 角度、直径) modify qq:15290049
;;;========================================
(defun max-ang-distance (h / d m maxd p pair ang q u v w)
(setq q (cdr (append h h (list (car h))))) ;构造一个首尾循环的凸集,且起始点为凸壳的第二点
(setq maxd 0.0) ;初始化最小距离为0
(foreach u h ;依次检查凸壳的边
(setq v (car q)) ;循环集的第一点
(setq w (cadr q)) ;循环集的第二点
(setq m (sl:mid v w)) ;这两点的中点
(while (> (dot m u v) 0.0) ;如果夹角小于90度（即点积大于0）
(setq q (cdr q)) ;循环集推进
(setq v (car q)) ;取下一点
(setq w (cadr q)) ;下下一点
(setq m (sl:mid v w)) ;这两点的中点
)
(setq d (distance u v)) ;计算这时的最大距离
(if (> d maxd) ;如果大于前面的最大距离
(setq maxd d ;就替换前面的最大距离
pair (list u v) ;并记录这对点
)
)
)
(setq ang (angle (car pair) (cadr pair))) ;modify qq:15290049
(list pair ang maxd) ;返回这对点和角度、最大距离 ;modify qq:15290049
)
;;;==================
;;;graham扫描法求逆时针凸包
;;;==================
(defun graham-scan (plis / hullpt maxxpt sortpt p q)
(if (< (length plis) 3) ;3点以下
plis ;是本集合
(progn
(setq maxxpt (assoc (apply 'max (mapcar 'car plis)) plis)) ;最右边的点
(setq sortpt (sort-by-angle-distance plis maxxpt)) ;分类点集
(setq hullpt (list (cadr sortpt) maxxpt)) ;开始的两点
(foreach n (cddr sortpt) ;从第3点开始
(setq hullpt (cons n hullpt)) ;把pi加入到凸集
(setq p (cadr hullpt)) ;pi-1
(setq q (caddr hullpt)) ;pi-2
(while (and q (> (det n p q) -1e-6)) ;如果左转
(setq hullpt (cons n (cddr hullpt))) ;删除pi-1点
(setq p (cadr hullpt)) ;得到新的pi-1点
(setq q (caddr hullpt)) ;得到新的pi-2点
)
)
(reverse hullpt) ;返回凸集
)
)
)
;;求中点函数-------(一级)------
(defun sl:mid (p1 p2)
(list (* (+ (car p1) (car p2)) 0.5) (* (+ (cadr p1) (cadr p2)) 0.5))
)
;;;以某点为基点，按照角度和距离分类点集
(defun sort-by-angle-distance (plis pt / )
(vl-sort plis
(function
(lambda (e1 e2 / ang1 ang2 )
(setq ang1 (angle pt e1))
(setq ang2 (angle pt e2))
(if (= ang1 ang2)
(< (distance pt e1) (distance pt e2))
(< ang1 ang2)
)
)
)
)
)
;;以下测试用（函数）---
;点表生成多段线--------(一级)-------
;线宽=nil，线宽为0 ;是否闭合=nil，不闭合 ;图层=nil，为当前图层 ;颜色=nil，为当前图层颜色 ;线型比例=nil，为1
;(slch:lwpolyline 点表是否闭合线宽图层颜色线型比例)
;(slch:lwpolyline (list (1 2) (2 3)) T 2 "中心线" 6 5)
(defun slch:lwpolyline (lst dxf70 plwid lay lwplcol lwplbili)
(entmake
(append
(list
'(0 . "LWPOLYLINE")
'(100 . "AcDbEntity")
'(100 . "AcDbPolyline")
(cons 90 (length lst)) ;点表
(if (= dxf70 T)
(cons 70 1) ;闭合与不闭合
(cons 70 0)
)
(if plwid
(cons 43 plwid) ;线宽
(cons 43 0)
)
(if lay
(cons 8 lay) ;图层
(cons 8 (getvar "CLAYER"))
)
(if lwplcol
(cons 62 lwplcol) ;颜色
(cons 62 256)
)
(if lwplbili
(cons 48 lwplbili) ;线型比例
(cons 48 (* 0.01 (getvar "DIMLFAC")))
)
)
(mapcar '(lambda (pt) (cons 10 pt)) lst)
)
)
)
;;测试主程序1--
;;结果：耗时较快
(defun c:tt (/ plis sel t0 ang)
(setq t0 (getvar "MILLISECS"))
(setq plis (Graham-scan (getpt (ssget)))) ;construct the CCW Hull of this set.
(setq ang (cadr (max-ang-distance plis))) ;modify qq:15290049
(setq plis (geo:getboxbyset plis ang)) ;qq:15290049
(slch:lwpolyline plis t nil nil nil nil)
(prompt (strcat "耗时" (rtos (/ (- (getvar "MILLISECS") t0) 1000.) 2 5) "秒"))
(princ)
)
;;测试主程序2--
;;结果：耗时较慢
(defun c:tt1 (/ plis sel t0 ang)
(setq t0 (getvar "MILLISECS"))
(setq plis (Graham-scan (getpt (ssget)))) ;construct the CCW Hull of this set.
(if (or (< (length plis) 3) (and (>= (length plis) 3) (<= (dot (car plis) (cadr plis) (caddr plis)) 0.0)))
(setq plis (reverse plis))
)
(setq plis (car (minarearectangle plis))) ;这是高飞大师的，最小面积包容较慢
(slch:lwpolyline plis t nil nil nil nil)
(prompt (strcat "耗时" (rtos (/ (- (getvar "MILLISECS") t0) 1000.) 2 5) "秒"))
(princ)
)

;;;-------------------------- 
;;; 功能: 旋转点 
;;; 输入: 点p，角度ang   
;;; 输出: 中点位置       
;;;------------------------- 
(defun geo:rotbyangle (p ang / c s) 
  (setq c (cos ang)) 
  (setq s (sin ang)) 
  (list 
    (- (* c (car p)) (* s (cadr p))) 
    (+ (* s (car p)) (* c (cadr p))) 
  ) 
) 
;;;------------------------ 
;;; 功能: 沿某一个方向的点集的包围盒    
;;; 输入: pts--点集      
;;; ang--方向与x轴夹角    
;;; 输出: 包围盒点(wcs) 
;;;-------------------------- 
(defun geo:getboxbyset (pts ang / pmin pmax) 
  (setq pts (mapcar (function (lambda (p) (geo:rotbyangle p (- ang)))) pts)) 
  (setq pmin (apply 'mapcar (cons 'min pts))) 
  (setq pmax (apply 'mapcar (cons 'max pts))) 
  (mapcar 
    (function (lambda (p) (geo:rotbyangle p ang))) 
    (list 
      (list (car pmin) (cadr pmin)) 
      (list (car pmax) (cadr pmin)) 
      (list (car pmax) (cadr pmax)) 
      (list (car pmin) (cadr pmax)) 
    ) 
  ) 
) 
;点积(内积):p1p2 p1p3是否垂直，垂直为0;锐角为正，钝角为负 By Highflybird 
;;定义向量的点积函数(向量A投影在向量B上的长度，但是它还要乘上B的长度) 
(defun dot (p1 p2 p3 / x1 y1) 
  (setq  x1 (car p1) 
    y1 (cadr p1) 
  ) 
  (+ (* (- (car p2) x1) (- (car p3) x1)) 
    (* (- (cadr p2) y1) (- (cadr p3) y1)) 
  ) 
) 
;;叉积(外积) By Highflybird 
;;1 三角形之倍面积 
;;2 p1 p2 p3 逆时针为正。 
;;3 三点共线为0 
(defun det (p1 p2 p3 / x2 y2) 
  (setq  x2 (car p2) y2 (cadr p2)) 
  (- (* (- x2 (car p3)) (- y2 (cadr p1))) (* (- x2 (car p1)) (- y2 (cadr p3)))) 
) 
;;;======================================== 
;;;求凸壳直径的参数       
;;;参数：逆时针的凸壳 h-------注意逆时针!!! 
;;;返回值: (pair ang maxd) ((p1 p2) 角度、直径) modify qq:15290049 
;;;======================================== 
(defun max-ang-distance (h / d m maxd p pair ang q u v w) 
  (setq q (cdr (append h h (list (car h)))))        ;构造一个首尾循环的凸集,且起始点为凸壳的第二点 
  (setq maxd 0.0)              ;初始化最小距离为0 
  (foreach u h                ;依次检查凸壳的边 
    (setq v (car q))              ;循环集的第一点 
    (setq w (cadr q))              ;循环集的第二点 
    (setq m (sl:mid v w))            ;这两点的中点 
    (while (> (dot m u v) 0.0)      ;如果夹角小于90度（即点积大于0） 
      (setq q (cdr q))              ;循环集推进 
      (setq v (car q))              ;取下一点 
      (setq w (cadr q))              ;下下一点 
      (setq m (sl:mid v w))        ;这两点的中点 
    ) 
    (setq d (distance u v))            ;计算这时的最大距离 
    (if  (> d maxd)              ;如果大于前面的最大距离 
      (setq maxd d              ;就替换前面的最大距离 
        pair (list u v)          ;并记录这对点 
      ) 
    ) 
  ) 
  (setq ang (angle (car pair) (cadr pair))) ;modify qq:15290049 
  (list pair ang maxd)              ;返回这对点和角度、最大距离 ;modify qq:15290049 
) 
;;;================== 
;;;graham扫描法求逆时针凸包 
;;;================== 
(defun graham-scan (plis / hullpt maxxpt sortpt p q) 
  (if (< (length plis) 3)            ;3点以下 
    plis                ;是本集合 
    (progn 
      (setq maxxpt (assoc (apply 'max (mapcar 'car plis)) plis))  ;最右边的点 
      (setq sortpt (sort-by-angle-distance plis maxxpt))     ;分类点集 
      (setq hullpt (list (cadr sortpt) maxxpt))        ;开始的两点       
      (foreach n (cddr sortpt)            ;从第3点开始 
        (setq hullpt (cons n hullpt))          ;把pi加入到凸集 
        (setq p (cadr hullpt))            ;pi-1 
        (setq q (caddr hullpt))            ;pi-2 
        (while (and q (> (det n p q) -1e-6))         ;如果左转 
          (setq hullpt (cons n (cddr hullpt)))         ;删除pi-1点 
          (setq p (cadr hullpt))          ;得到新的pi-1点 
          (setq q (caddr hullpt))          ;得到新的pi-2点 
        ) 
      ) 
      (reverse hullpt)              ;返回凸集 
    ) 
  ) 
) 
;;求中点函数-------(一级)------ 
(defun sl:mid (p1 p2) 
  (list (* (+ (car p1) (car p2)) 0.5) (* (+ (cadr p1) (cadr p2)) 0.5)) 
) 
;;;以某点为基点，按照角度和距离分类点集 
(defun sort-by-angle-distance (plis pt / ) 
  (vl-sort plis 
    (function 
      (lambda (e1 e2 / ang1 ang2 ) 
        (setq ang1 (angle pt e1)) 
        (setq ang2 (angle pt e2)) 
        (if (= ang1 ang2) 
          (< (distance pt e1) (distance pt e2)) 
          (< ang1 ang2) 
        ) 
      ) 
    ) 
  ) 
) 
;;以下测试用（函数）--- 
 
 
;点表生成多段线--------(一级)------- 
;线宽=nil，线宽为0  ;是否闭合=nil，不闭合 ;图层=nil，为当前图层 ;颜色=nil，为当前图层颜色  ;线型比例=nil，为1 
;(slch:lwpolyline 点表 是否闭合 线宽 图层 颜色 线型比例) 
;(slch:lwpolyline (list (1 2) (2 3)) T 2 "中心线" 6 5) 
(defun slch:lwpolyline (lst dxf70 plwid lay lwplcol lwplbili) 
  (entmake 
    (append 
      (list 
        '(0 . "LWPOLYLINE") 
        '(100 . "AcDbEntity") 
        '(100 . "AcDbPolyline") 
        (cons 90 (length lst)) ;点表 
        (if (= dxf70 T) 
          (cons 70 1)  ;闭合与不闭合 
          (cons 70 0) 
        ) 
        (if plwid 
          (cons 43 plwid)      ;线宽 
          (cons 43 0) 
        ) 
        (if lay 
          (cons 8 lay) ;图层 
          (cons 8 (getvar "CLAYER")) 
        ) 
        (if lwplcol 
          (cons 62 lwplcol)    ;颜色 
          (cons 62 256) 
        ) 
        (if lwplbili 
          (cons 48 lwplbili)   ;线型比例 
          (cons 48 (* 0.01 (getvar "DIMLFAC"))) 
        ) 
      ) 
      (mapcar '(lambda (pt) (cons 10 pt)) lst) 
    ) 
  ) 
) 
;;测试主程序1-- 
;;结果：耗时较快 
(defun c:tt (/ plis sel t0 ang) 
  (setq t0 (getvar "MILLISECS")) 
  (setq plis (Graham-scan (getpt (ssget))))        ;construct the CCW Hull of this set. 
  (setq ang (cadr (max-ang-distance plis))) ;modify qq:15290049 
  (setq plis (geo:getboxbyset plis ang))      ;qq:15290049 
  (slch:lwpolyline plis t nil nil nil nil) 
  (prompt (strcat "耗时" (rtos (/ (- (getvar "MILLISECS") t0) 1000.) 2 5) "秒")) 
  (princ) 
) 
;;测试主程序2-- 
;;结果：耗时较慢 
(defun c:tt1 (/ plis sel t0 ang) 
  (setq t0 (getvar "MILLISECS")) 
  (setq plis (Graham-scan (getpt (ssget))))        ;construct the CCW Hull of this set. 
  (if (or (< (length plis) 3) (and (>= (length plis) 3) (<= (dot (car plis) (cadr plis) (caddr plis)) 0.0))) 
    (setq plis (reverse plis)) 
  ) 
  (setq plis (car (minarearectangle plis))) ;这是高飞大师的，最小面积包容较慢 
  (slch:lwpolyline plis t nil nil nil nil) 
  (prompt (strcat "耗时" (rtos (/ (- (getvar "MILLISECS") t0) 1000.) 2 5) "秒")) 
  (princ) 
)

highflybird · 发表于 2024-6-21 00:04:45

尘缘一生发表于 2024-6-20 23:59
我组织了下子，测试，
取得角度办法较快，从前

这两个目的不一样。一个是求最小的包围盒，一个是求指定角度下的包围盒。

尘缘一生 · 发表于 2024-6-21 05:58:16

highflybird 发表于 2024-6-21 00:04
这两个目的不一样。一个是求最小的包围盒，一个是求指定角度下的包围盒。

嗯，高大师，那么面积最小时候这个角度求出来的函数，能组织个，就可以加快速度了不是？因为面积最小时候的凸包，用的多。

highflybird · 发表于 2024-6-21 14:01:43

尘缘一生发表于 2024-6-21 05:58
嗯，高大师，那么面积最小时候这个角度求出来的函数，能组织个，就可以加快速度了不是？因为面积最小时候 ...

求最小面积的时候要用到凸包的。

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

[【高飞鸟】] 任意角度或UCS下的物体包围盒

本帖子中包含更多资源