O-tree表示法

aimisiyou · 发表于 2020-10-12 16:03:08

本帖最后由 aimisiyou 于 2020-10-12 16:33 编辑

(defun c:tt()
(setq rlst '(
(1 5.3 5.1)
(2 7.4 6.5)
(3 3.3 10.3)
(4 8.5 4.6)
(5 9.2 6.2)
(6 7.4 6.9)
(7 4.4 11.4)
(8 14.4 3.6)
(9 9.2 5.6)
))
(setq area_sum (apply '+ (mapcar '(lambda (x) (* (cadr x) (caddr x))) rlst)))
(setq n (length rlst) xmax (max (apply 'max (mapcar 'cadr rlst)) (apply 'max (mapcar 'caddr rlst))))
(defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (NN)
  (fix (* NN (rnd)))
)
(defun tfun (n)
(setq lst '(-1) i 1 flag t)
(while (and flag (< i n))
  (setq sum (apply '+ lst))
  (if (= sum 0)
   (setq lst (cons -1 lst))
      (if (= sum (- i n))
            (progn
                  (setq flag nil)
                        (repeat (- n i)
                           (setq lst (cons 1 lst))
                        )
               )
               (if (= (rem (rnd_n 1000) 2) 1)
                     (setq lst (cons -1 lst))
                     (setq lst (cons 1 lst))
               )
            )
      )
      (setq i (+ i 1))
)
(mapcar '(lambda (x) (/ (1+ x) 2)) (reverse lst))
)
(defun qfun(n)
(setq vlst nil)
(repeat n
(setq vlst (cons (rnd_n 1000) vlst))
)
(mapcar '(lambda (y) (if (= (rem (rnd_n 1000) 2) 1)  y (* -1 y))) (mapcar '1+ (vl-sort-i vlst '<)))
)
(setq tlst (tfun (* 2 n)) qlst (qfun n) j 0 dblst (list (list 0 0 (* n xmax))) pt '(0 0))
(foreach en tlst
(if (= en 0)
   (progn
      (setq jnum (nth j qlst))
      (setq rect_now (list (nth (- (abs jnum) 1) rlst)))
   (if (< jnum 0)
      (setq newrect (list (caddr rect_now) (cadr rect_now))))
            (setq newrect (list (cadr rect_now) (caddr rect_now))))
   )
      (command "rectang" pt (car newrect) (car newrect) (polar pt 0 10))
      更新顶部轮廓线dblst
   (setq pt (list (+ (car pt) (car newrect)) (cadr pt)))
   (setq j (+ j 1))
   )
   (progn
      从pt水平坐标往左沿顶部轮廓线dblst退回水平一段
      更新pt坐标
   )
)
)
)

aimisiyou · 发表于 2020-10-12 19:33:47

本帖最后由 aimisiyou 于 2020-10-12 19:36 编辑

终于大功告成！！！
(defun c:tt()
(setvar "osmode" 0)
(setq rlst '(
(1 5.3 5.1)
(2 7.4 6.5)
(3 3.3 10.3)
(4 8.5 4.6)
(5 9.2 6.2)
(6 7.4 6.9)
(7 4.4 11.4)
(8 14.4 3.6)
(9 9.2 5.6)
))
(setq area_sum (apply '+ (mapcar '(lambda (x) (* (cadr x) (caddr x))) rlst)))
(setq n (length rlst) xmax (max (apply 'max (mapcar 'cadr rlst)) (apply 'max (mapcar 'caddr rlst))))
(defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (NN)
  (fix (* NN (rnd)))
)
(defun tfun (n)
(setq lst '(-1) i 1 flag t)
(while (and flag (< i n))
  (setq sum (apply '+ lst))
  (if (= sum 0)
   (setq lst (cons -1 lst))
      (if (= sum (- i n))
            (progn
                  (setq flag nil)
                        (repeat (- n i)
                           (setq lst (cons 1 lst))
                        )
               )
               (if (= (rem (rnd_n 1000) 2) 1)
                     (setq lst (cons -1 lst))
                     (setq lst (cons 1 lst))
               )
            )
      )
      (setq i (+ i 1))
)
(mapcar '(lambda (x) (/ (1+ x) 2)) (reverse lst))
)
(defun qfun(n)
(setq vlst nil)
(repeat n
(setq vlst (cons (rnd_n 1000) vlst))
)
(mapcar '(lambda (y) (if (= (rem (rnd_n 1000) 2) 1)  y (* -1 y))) (mapcar '1+ (vl-sort-i vlst '<)))
)
(setq tlst (tfun (* 2 n)) qlst (qfun n) j 0 dblst (list (list 0 0 (* n xmax))) pt '(0 0))
(foreach en tlst
(if (= en 0)
   (progn
            (setq jnum (nth j qlst))
      (setq rect_now (nth (- (abs jnum) 1) rlst))
               (if (< jnum 0)
                  (setq newrect (list (caddr rect_now) (cadr rect_now)))
            (setq newrect (list (cadr rect_now) (caddr rect_now)))
               )
      (setq vflst (car (vl-remove nil (mapcar '(lambda (x) (if (= (car pt)(car x)) x nil)) dblst))))
      (setq vvflst (vl-remove nil (mapcar '(lambda (x) (if (< (car x)  (+ (car pt) (car newrect))) x nil))(member vflst dblst))))
      (setq ymax (cadr (car (vl-sort vvflst '(lambda (ea eb) (> (cadr ea) (cadr eb)))))) ptlst (last vvflst))
      (if (< (+ ymax (cadr newrect)) (cadr pt))
                  (progn
                     (setq pt (list  (car pt)  (- (cadr pt) (cadr newrect))))
            (command "rectang" pt "d" (car newrect) (cadr newrect) (polar pt 0 10))
                        )
                        (progn
                        (setq pt (list (car pt) ymax))
            (command "rectang" pt "d" (car newrect) (cadr newrect) (polar pt 0 10))
                        )
               )
      (foreach ee vvflst
               (setq dblst (vl-remove ee dblst))
      )
      (if (= (+ (car ptlst) (cadr ptlst)) (+ (car pt) (car newrect)))
            (setq dblst (cons (list (car pt) (+ (cadr pt)(cadr newrect)) (car newrect)) dblst))
                  (setq dblst (cons (list (+ (car pt) (car newrect)) (cadr ptlst) (- (+ (car ptlst) (caddr ptlst)) (car newrect))) (cons (list (car pt) (+ (cadr pt)(cadr newrect)) (car newrect)) dblst)))
            )
               (setq dblst (vl-sort dblst '(lambda (ea eb) (< (car ea) (car eb)))))
               (setq pt (polar pt 0 (car newrect)))
               (setq j (+ j 1))
         )
         (progn
            (setq vflst (car (vl-remove nil (mapcar '(lambda (x) (if (= (car pt)(+ (car x) (caddr x))) x nil))  dblst))))
               (setq pt (list (car vflst) (cadr vflst)))
         )
)
  )
)

aimisiyou · 发表于 2020-10-12 19:38:04

接下来就是思考如何对图形进行调整，得到利用率较高的排版。

aimisiyou · 发表于 2020-10-12 23:17:06

本帖最后由 aimisiyou 于 2020-10-12 23:20 编辑

(setq rlst '(
(1 400 230)
(2 400 160)
(3 340 130)
(4 246 100)
(5 350 100)
(6 170 110)
(7 220 120)
(8 420 280)
(9 330 220)
(10 290 170)
(11 230 200)
(12 210 170)
(13 260 150)
(14 180 160)
(15 200 180)
(16 245 160)
(17 210 200)
(18 220 140)
(19 250 170)
(20 300 300)
(21 350 320)
(22 320 280)
(23 165 150)
))
面积利用率达到98.0204%。

aimisiyou · 发表于 2020-10-13 14:07:09

本帖最后由 aimisiyou 于 2020-10-13 14:09 编辑

紧置布置才是最终目标。

aimisiyou · 发表于 2020-11-1 16:29:55

关于利用率的优化一直没有好的方向。初步想法是参考平面寻最优点的思路，即对应任意平面一点（此处为（T，Q）），都有对应得函数值（此处为面积利用率）。先随机生成N个点和对应的函数值，采用萤火虫算法进行优化。

aimisiyou · 发表于 2020-11-1 16:38:25

如何表示两个不同的T的差异值？
如（0 0 1 1）和（0 1 0 1）

aimisiyou · 发表于 2020-11-16 07:48:50

本帖最后由 aimisiyou 于 2020-11-16 07:57 编辑

(defun drawrect()
(setvar "osmode" 0)
(setq ens (ssget '((0 . "LWPOLYLINE"))) n (sslength ens) i 0 vlst nil)
(while (< i n)
(setq lst (vlax-safearray->list (vlax-variant-value (vlax-get-property (vlax-ename->vla-object (ssname ens i)) 'Coordinates))))
(setq vlst (cons (list (abs (- (+ (car lst) (cadddr lst)) (+ (cadr lst) (caddr lst))))
                           (abs (- (+ (car lst) (last  lst)) (+ (cadr lst) (cadr (reverse lst)))))
                                       )
                                 vlst
                              )
      )
(setq i (+ i 1))
)
(setq lst (vl-sort (mapcar '(lambda (x) (if (> (car x) (cadr x)) x (reverse x))) vlst) '(lambda (ea eb) (> (car ea) (car eb)))))
(setq pt '(0 0))
(foreach en lst
(command "rectang" pt "d" (car en) (cadr en) (setq pt (polar pt (/ pi 2) (cadr en))))
)
)
(drawrect)

aimisiyou · 发表于 2020-11-16 14:03:10

(setq vlst '(
(1 119 378)
(2 133 336)
(3 140 161)
(4 49 119)
(5 119 175)
(6 140 406)
(7 140 497)
(8 119 196)
(9 182 371)
(10 119 294)
(11 119 161)
(12 119 266)
(13 119 336)
(14 119 126)
(15 182 203)
(16 182 203)
(17 84 119)
(18 133 294)
(19 182 350)
(20 140 315)
(21 133 315)
(22 133 560)
(23 133 140)
(24 133 175)
(25 133 231)
(26 133 315)
(27 98 182)
(28 210 210)
(29 126 378)
(30 119 182)
(31 119 119)
(32 119 357)
(33 84 119)
))
(setq pt '(0 0))
(setvar "osmode" 0)
(foreach en vlst
(command "rectang" pt "d" (cadr en) (caddr en) (polar pt 0 (caddr en)))
(setq pt (polar pt (/ pi 2) (caddr en)))
)

aimisiyou · 发表于 2020-11-25 16:04:12

本帖最后由 aimisiyou 于 2020-11-25 16:58 编辑

考虑采用另一种表示形式来描述布局图。如果可以通过表示法快速的得到水平最大距离和垂直最大距离，则外接矩形框的长宽也就确定了。如图，可知水平最长路径为L-->1-->2-->3-->R,竖直方向最长路径为B-->1-->4-->T.可知模块1即在水平最长路径上，又在竖直方向最长路径上，后续优化方案有四种：1、将竖直最长路径上水平长度小于模块1的与1模块交换位置（这样最长竖直路径不变，但最长水平路径缩小，外框矩形面积变小）；2、将水平最长路径上竖直宽度小于模块1的与模块1交换位置（这样最长水平路径不变，但最长竖直路径缩小，外框矩形面积变小）；3、模块1旋转90度；4、将模块1与其他模块交换位置。

aimisiyou · 发表于 2020-11-27 12:34:35

按照DBL表示法，每个节点（模块）至少有四条连线（1上左、2上右，3右下、右上），特殊节点除外，但竖直或水平方向有间隔的就无法正确表示。如
图中模块2和模块4的关系表示（与一般情况不符）。

aimisiyou · 发表于 2020-11-27 12:50:49

本帖最后由 aimisiyou 于 2020-11-27 13:07 编辑

按照左下紧置原则，结合角模块思路，可以得到一一对应的表示法。
如图对应的表示为'（（1 L B）（2 1 B）（3 2 B）(4 L 3)）.
从关系图中可以轻松求出最长水平距离和最长竖直距离，即
最长水平距离vl=max{L<--4,L<--1<--2<--3}
最长竖直距离vb=max{B<--1,B<--2，B<--3<--4}

aimisiyou · 发表于 2020-11-27 13:19:22

本帖最后由 aimisiyou 于 2020-11-27 13:24 编辑

图形对应的表示为'(
(0  L  B)
(1  L  0)
(2  1  0)
(3  2  0)
(4  3  0)
(5  L  1)
(6  5  3)
(7  0  B)
(8  0  7)
(9  0  8)
(10  0  9)
(11  8  7)
)

aimisiyou · 发表于 2020-11-27 13:21:18

本帖最后由 aimisiyou 于 2020-11-27 13:22 编辑

对比DBL表示，数据存贮更节俭了。

aimisiyou · 发表于 2020-11-27 15:43:13

本帖最后由 aimisiyou 于 2020-11-27 16:04 编辑

第一步，如何判断表示是否合法。如图（5 4 1）显然不符合左下紧置要求，正确应为（5 2 1）.

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

[研讨] O-tree表示法