社区 › AutoLISP/Visual LISP 编程技术 › 分治策略在查找最近点问题中的应用一例

vectra 发表于 2015-1-31 19:48:27

分治策略在查找最近点问题中的应用一例

本帖最后由 vectra 于 2015-1-31 20:10 编辑

问题提出见原贴 http://bbs.mjtd.com/thread-112884-1-1.html

逐一检测的时间复杂度是O(n^2)，当n较大时，时间开销不能接受。

采用分治方法，先将对象按X坐标排序，并对对象进行分组，每次只对在X坐标正负指定间距内的对象逐一检测，时间复杂度接近O（n）


(defun stop-watch-start(/)
(setq *stop-watch-start* (getvar "millisecs"))
)


(defun stop-watch-elapse (/)
(- (getvar "millisecs") *stop-watch-start*)
)

(defun report-time-consuming (msg)
(princ
    (strcat "\n" msg " (" (itoa (stop-watch-elapse)) " ms)")
)
(stop-watch-start)
)

(defun sort-point-ent-pair (pep)
(setq
;;;    pep (vl-sort pep '(lambda (e1 e2) (< (caddar e1) (caddar e2))))
;;;pep (vl-sort pep '(lambda (e1 e2) (< (cadar e1) (cadar e2))))
    pep
   (vl-sort pep '(lambda (e1 e2) (< (caar e1) (caar e2))))
)
pep
)


(defun find-closest-bruteforce (pep1 pep2 / tmp)
(setq tmp pep1)
(while pep2
    (while tmp
      (if (<= (distance (caar tmp) (caar pep2)) *gap*)
(vla-put-color (vlax-ename->vla-object (cadar tmp)) 1)
      )
      (setq tmp (cdr tmp))
    )
    (setq tmppep1
    pep2 (cdr pep2)
    )
)
)


(defun get-point-ent-pair (ent / dxf)
(setq dxf (entget ent))
(cond
    ((= "TEXT" (cdr (assoc 0 dxf)))
   (setq pep1 (cons (list (cdr (assoc 10 dxf)) ent) pep1))
    )
    ((= "LINE" (cdr (assoc 0 dxf)))
   (setq pep2
      (cons
      (list
    (mapcar
      '(lambda (e) (/ e 2.0))
      (mapcar '+ (cdr (assoc 10 dxf)) (cdr (assoc 11 dxf)))
    )
    ent
      )
      pep2
      )
   )
    )
)
)


(defun get-test-data ()
(setqss    (ssget '((0 . "LINE,TEXT")))
i   0
*gap* 50.0
)
(stop-watch-start)

(repeat (sslength ss)
    (get-point-ent-pair (ssname ss i))
    (setq i (1+ i))
)
(report-time-consuming (strcat "构建点实体表 " (itoa (sslength ss)) "个对象"))
)


(defun c:tt (/ i pep1 pep2 ss)

(get-test-data)

(stop-watch-start)

(vla-startundomark
    (vla-get-activedocument (vlax-get-acad-object))
)
(find-closest-bruteforce pep1 pep2)
(vla-endundomark
    (vla-get-activedocument (vlax-get-acad-object))
)
(report-time-consuming "两次循环")

(princ)
)


(defun c:tt2 (/ cur i pep1 pep2 rh1 rh2 ss tmp)

(get-test-data)

(setqpep1 (sort-point-ent-pair pep1)
pep2 (sort-point-ent-pair pep2)
)
(report-time-consuming "排序")


(vla-startundomark
    (vla-get-activedocument (vlax-get-acad-object))
)
(while (and pep1 pep2)
    ;; 取线段表中第一个元素为游标
    (setq cur(caar pep2)
    rh2(list (car pep2))
    pep2 (cdr pep2)
    tmppep1
    )

    ;; 将游标附近X坐标差值在*gap*范围内的线段归集到rh2
    (while (andpep2
    (<= (abs (- (car (caar pep2)) (car cur))) *gap*)
   )
      (setq rh2   (cons (car pep2) rh2)
      pep2 (cdr pep2)
      )
    )
    ;; 将游标附近X坐标差值在*gap*范围内的文字归集到rh1
    (while tmp
      (if (<= (abs (- (car (caar tmp)) (car cur))) *gap*)
(setq rh1 (cons (car tmp) rh1))
(if (< (car (caar tmp)) (car cur))
    (setq pep1 (cdr pep1))
    (setq tmp nil)
)
      )
      (setq tmp (cdr tmp))
    )

    (if(and rh1 rh2)
      (find-closest-bruteforce rh1 rh2)
    )

    (while rh1
      (setq pep1 (cdr pep1)
      rh1   (cdr rh1)
      )
    )
)
(vla-endundomark
    (vla-get-activedocument (vlax-get-acad-object))
)
(report-time-consuming "完成符合条件的对象标记")


(princ)
)


命令: tt
构建点实体表 9202个对象 (297 ms)
两次循环 (34093 ms)

命令:TT2
构建点实体表 9202个对象 (140 ms)
排序 (31 ms)
完成符合条件的对象标记 (766 ms)

命令: tt2
构建点实体表 31598个对象 (563 ms)
排序 (109 ms)
完成符合条件的对象标记 (2719 ms)

命令:TT2
构建点实体表 46010个对象 (1907 ms)
排序 (203 ms)
完成符合条件的对象标记 (5781 ms)

命令:TT2
构建点实体表 55212个对象 (2266 ms)
排序 (250 ms)
完成符合条件的对象标记 (6281 ms)

通过测试发现，E3 1230V2上每秒可处理近1万个对象。

革天明 发表于 2015-1-31 22:01:23

顶一个，算法确实对效率有很大影响

bzhjl 发表于 2015-2-1 00:17:50

很赞，支持一个

ljxkm 发表于 2015-2-1 10:40:13

确实很实用，请问一下“millisecs”是什么变量

masterlong 发表于 2015-2-1 19:19:49

提点个人意见
如有冒犯楼主勿怪

就原求助帖的要求而言
我认为楼主的方法可能还不是最合适的
昨天看此贴时
总感觉楼主的思路绕了弯
今天测试了一把
测试对比结果放在下贴

我的方法是直接以线段中点
构建ssget 'cp的 cp-polist、filter-list
再逐一检测选择集图元是否满足要求

个人感觉楼主的程序
或许还能在以下几个方面优化
1.
开始的点对构建
直接按line、text分别获取选择集
cond判别是要走流程的
2.
仅以x排序不合适
应同时以x、y排序
3.
mapcar、lambda的应用
纯粹个人感觉啊
它们能让程序看起来很简洁
但并不能减少代码执行的时间
需要反复调用的功能
还是做成子函数比较合适

masterlong 发表于 2015-2-1 19:21:37

●●●●简单线字关系●●●●数量较少————————————————直线27606，文字共27606，改色13932

◆vectra◆
命令: tt2
构建点实体表 55212个对象 (2750 ms)
排序 (531 ms)
完成符合条件的对象标记 (6484 ms)
|
程序总耗时 9506 毫秒

◆masterlong◆
命令: tt
【以直线搜文字】
|
程序总耗时 9829 毫秒



●●●●简单线字关系●●●●数量较多（9倍）—————————直线248454，文字共248454，改色125388

◆vectra◆
命令: tt2
构建点实体表 496908个对象 (43875 ms)
排序 (7250 ms)
完成符合条件的对象标记 (167218 ms)
|
程序总耗时 219453 毫秒

◆masterlong◆
命令: tt
【以直线搜文字】
|
程序总耗时 98938 毫秒





●●●●复杂线字关系●●●●数量较少————————————————直线37249，文字共46010，改色9159

◆vectra◆
命令: tt2
构建点实体表 83259个对象 (4750 ms)
排序 (1109 ms)
完成符合条件的对象标记 (12687 ms)
|
程序总耗时 18703 毫秒

◆masterlong◆
命令: tt
【以直线搜文字】
|
程序总耗时 11500 毫秒



●●●●复杂线字关系●●●●数量较多（6倍）—————————直线223494，文字共276060，改色54954

◆vectra◆
命令: tt2
构建点实体表 499554个对象 (82031 ms)
排序 (7750 ms)
完成符合条件的对象标记 (158406 ms)
|
程序总耗时 249218 毫秒

◆masterlong◆
命令: tt
【以直线搜文字】
|
程序总耗时 141172 毫秒

masterlong 发表于 2015-2-1 19:32:33

vectra 发表于 2015-2-1 20:15:51

框选法核心还是空间数据索引、分治等应用，只不过是CAD内置功能，代码实现是dll级别的，效率高lisp 不知道N倍。

加入对Y的分治可以进一步提高速度，只是代码会更加复杂。复杂的代码，可靠性难保证。

框选法最大的问题是对视口范围依存度很高，比如视口不显示的对象无法处理，当处理区域缩放比率过小时，选择结果不可预测。这会导致实际应用中产生不期望的结果或性能损失。

楼上可以试下下面这个图，不要更改缩放比率运行tt，时间明显比一个合理的绽放比率时要长许多倍。。

masterlong 发表于 2015-2-1 20:45:52

你说得对
框选法有较大的局限性
而纯数学的方法会比较稳定

在两者之间如何取舍
编程中我也经常为之纠结

llsheng_73 发表于 2015-2-2 19:45:13

如果能通过数学方法解决，尽可能不要依赖CAD本身的功能，虽然我们离不开CAD，但并不妨碍用数学方法解决一些问题

查看完整版本: 分治策略在查找最近点问题中的应用一例