XDGE几何库应用(29)--平面点集外接最小面积矩形

st788796 · 发表于 2014-11-4 13:49:19

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

本帖最后由 st788796 于 2014-11-4 13:51 编辑

函数见 http://bbs.xdcad.net/thread-676796-1-1.html

;;逆时针凸包点集
(defun XD::Pnts:MinRectang (pts / _pnt->2d marea ptl tan
v1 p1 p2 p3 ydir rec lst
area box v2 i
)
(defun _drawbox (pts col /)
(apply 'xdrx_grdraw
(cons
col
(cons 1
(list (car pts)
(mapcar '+ (car pts) (cadr pts))
(apply 'mapcar (cons '+ pts))
(mapcar '+ (car pts) (caddr pts))
(car pts)
)
)
)
)
)
(defun _pnt->2d (p) (list (car p) (cadr p)))
(if (<= (length pts) 2)
pts
(progn
(setq pts (xdrx_points_gethull pts) ;_2007+
pts (mapcar '(lambda (x) (_pnt->2d x)) pts)
marea 1e328
ptl pts
tan (/ pi 2)
v1 (mapcar '- (cadr pts) (car pts))
i 0
)
(while (and
(> (length ptl) 2)
(< (xdrx_vector_angle
v1
(setq v2 (mapcar '- (cadr ptl) (car ptl)))
)
tan
)
)
(setq ydir (xdrx_vector_product
(xdrx_vector_normalize (xdrx_vector_perpvector v2))
(abs (xdrx_point_dist2line
(caddr ptl)
(car ptl)
(cadr ptl)
)
)
)
rec (xdge::constructor "kBoundBlock2d" (car ptl) v2 ydir);_以一个边为 x轴，第三个点构造斜向bound
)
(foreach x pts
(xdge::setpropertyvalue rec "extend" x);_把所有点加入 boundblock,自动扩充
)
(setq lst (xdge::getpropertyvalue rec "get");_boundblock 信息，基点、x轴向量、y轴向量
area (* (xdrx_vector_length (cadr lst));_边长
(xdrx_vector_length (caddr lst));_边长
)
)
(_drawbox lst (setq i (1+ i)))
(princ "\nColor ")
(princ i)
(princ " Rectang Area = ")
(princ (rtos area 2 5))
(if (< area marea)
(setq marea area
box lst
)
)
(setq ptl (cdr ptl))
)
(xdge::free)
(list (car box)
(mapcar '+ (car box) (cadr box))
(apply 'mapcar (cons '+ box))
(mapcar '+ (car box) (caddr box))
)
)
)
)
(defun c:tt (/ pts)
(setq
pts (XD::pnts:minrectang
(mapcar '(lambda (x) (xdrx_getpropertyvalue x "position"))
(xdrx_pickset->ents (ssget '((0 . "point"))))
)
)
)
;;(apply 'xdrx_polyline_make (cons t pts))
(princ)
)

;;逆时针凸包点集 
(defun XD::Pnts:MinRectang (pts          /        _pnt->2d    marea ptl        tan 
                            v1          p1        p2    p3    ydir  rec        lst 
                            area  box        v2 i 
                           ) 
  (defun _drawbox (pts col /) 
    (apply 'xdrx_grdraw 
           (cons 
             col 
             (cons 1 
                   (list (car pts) 
                         (mapcar '+ (car pts) (cadr pts)) 
                         (apply 'mapcar (cons '+ pts)) 
                         (mapcar '+ (car pts) (caddr pts)) 
                         (car pts) 
                   ) 
             ) 
           ) 
    ) 
  ) 
  (defun _pnt->2d (p) (list (car p) (cadr p))) 
  (if (<= (length pts) 2) 
    pts 
    (progn 
      (setq pts          (xdrx_points_gethull pts) ;_2007+ 
            pts          (mapcar '(lambda (x) (_pnt->2d x)) pts) 
            marea 1e328 
            ptl          pts 
            tan          (/ pi 2) 
            v1          (mapcar '- (cadr pts) (car pts)) 
            i 0 
      ) 
      (while (and 
               (> (length ptl) 2) 
               (< (xdrx_vector_angle 
                    v1 
                    (setq v2 (mapcar '- (cadr ptl) (car ptl))) 
                  ) 
                  tan 
               ) 
             ) 
        (setq ydir (xdrx_vector_product 
                     (xdrx_vector_normalize (xdrx_vector_perpvector v2)) 
                     (abs (xdrx_point_dist2line 
                            (caddr ptl) 
                            (car ptl) 
                            (cadr ptl) 
                          ) 
                     ) 
                   ) 
              rec  (xdge::constructor "kBoundBlock2d" (car ptl) v2 ydir);_以一个边为 x轴，第三个点构造斜向bound 
        ) 
        (foreach x pts 
          (xdge::setpropertyvalue rec "extend" x);_把所有点加入 boundblock,自动扩充 
        ) 
        (setq lst  (xdge::getpropertyvalue rec "get");_boundblock 信息，基点、x轴向量、y轴向量 
              area (* (xdrx_vector_length (cadr lst));_边长 
                      (xdrx_vector_length (caddr lst));_边长 
                   ) 
        ) 
        (_drawbox lst (setq i (1+ i))) 
        (princ "\nColor ") 
        (princ i) 
        (princ " Rectang Area = ") 
        (princ (rtos area 2 5)) 
        (if (< area marea) 
          (setq        marea area 
                box   lst 
          ) 
        ) 
        (setq ptl (cdr ptl)) 
      ) 
      (xdge::free) 
      (list (car box) 
            (mapcar '+ (car box) (cadr box)) 
            (apply 'mapcar (cons '+ box)) 
            (mapcar '+ (car box) (caddr box)) 
      ) 
    ) 
  ) 
) 
(defun c:tt (/ pts) 
  (setq 
    pts        (XD::pnts:minrectang 
          (mapcar '(lambda (x) (xdrx_getpropertyvalue x "position")) 
                  (xdrx_pickset->ents (ssget '((0 . "point")))) 
          ) 
        ) 
  ) 
  ;;(apply 'xdrx_polyline_make (cons t pts)) 
  (princ) 
)

newer · 发表于 2014-11-4 20:52:08

本帖最后由 newer 于 2014-11-4 20:53 编辑

这个可高级，代码还那么短，去掉那些显示修饰的代码部分，也就2，30行吧，能给讲讲算法的思路吗？

st788796 · 发表于 2014-11-4 21:09:22

本帖最后由 st788796 于 2014-11-4 21:12 编辑

newer 发表于 2014-11-4 20:52
这个可高级，代码还那么短，去掉那些显示修饰的代码部分，也就2，30行吧，能给讲讲算法的思路吗？

旋转卡壳方法在网上和算法与数据库论坛都有很多介绍，不再多述，这个方法中以一条边作为矩形的所在边去构造一个点集的盒子，在 AcGe 库中用 BoundBlock2d 简化这个构造矩形方法，初始 BoundBlock2d 如图中虚线所示，然后用 foreach 语句将其他点 extend 进 boundblock2d 后，最终形成外面实线框，算完第一条边然后算第二个 ... 比较下面积哪个最小，记录下来

逆时针方向点集可以保证用边计算垂向量时始终指向凸包内部

AcGeBoundBlock2d/3d 详细介绍可以参考
http://bbs.xdcad.net/forum.php?mod=viewthread&tid=676122&ctid=26

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

[教学] XDGE几何库应用(29)--平面点集外接最小面积矩形

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

本帖被以下淘专辑推荐:

浏览过的版块