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

vectra

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

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

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

1. (defun stop-watch-start  (/)
   
2.   (setq *stop-watch-start* (getvar "millisecs"))
   
3. )
   
4. 
   
5. 
   
6. (defun stop-watch-elapse (/)
   
7.   (- (getvar "millisecs") *stop-watch-start*)
   
8. )
   
9. 
   
10. (defun report-time-consuming (msg)
    
11.   (princ
    
12.     (strcat "\n" msg " (" (itoa (stop-watch-elapse)) " ms)")
    
13.   )
    
14.   (stop-watch-start)
    
15. )
    
16. 
    
17. (defun sort-point-ent-pair (pep)
    
18.   (setq
    
19. ;;;    pep (vl-sort pep '(lambda (e1 e2) (< (caddar e1) (caddar e2))))
    
20. ;;;  pep (vl-sort pep '(lambda (e1 e2) (< (cadar e1) (cadar e2))))
    
21.     pep
    
22.      (vl-sort pep '(lambda (e1 e2) (< (caar e1) (caar e2))))
    
23.   )
    
24.   pep
    
25. )
    
26. 
    
27. 
    
28. (defun find-closest-bruteforce (pep1 pep2 / tmp)
    
29.   (setq tmp pep1)
    
30.   (while pep2
    
31.     (while tmp
    
32.       (if (<= (distance (caar tmp) (caar pep2)) *gap*)
    
33.   (vla-put-color (vlax-ename->vla-object (cadar tmp)) 1)
    
34.       )
    
35.       (setq tmp (cdr tmp))
    
36.     )
    
37.     (setq tmp  pep1
    
38.     pep2 (cdr pep2)
    
39.     )
    
40.   )
    
41. )
    
42. 
    
43. 
    
44. (defun get-point-ent-pair (ent / dxf)
    
45.   (setq dxf (entget ent))
    
46.   (cond
    
47.     ((= "TEXT" (cdr (assoc 0 dxf)))
    
48.      (setq pep1 (cons (list (cdr (assoc 10 dxf)) ent) pep1))
    
49.     )
    
50.     ((= "LINE" (cdr (assoc 0 dxf)))
    
51.      (setq pep2
    
52.       (cons
    
53.         (list
    
54.     (mapcar
    
55.       '(lambda (e) (/ e 2.0))
    
56.       (mapcar '+ (cdr (assoc 10 dxf)) (cdr (assoc 11 dxf)))
    
57.     )
    
58.     ent
    
59.         )
    
60.         pep2
    
61.       )
    
62.      )
    
63.     )
    
64.   )
    
65. )
    
66. 
    
67. 
    
68. (defun get-test-data ()
    
69.   (setq  ss    (ssget '((0 . "LINE,TEXT")))
    
70.   i     0
    
71.   *gap* 50.0
    
72.   )
    
73.   (stop-watch-start)
    
74. 
    
75.   (repeat (sslength ss)
    
76.     (get-point-ent-pair (ssname ss i))
    
77.     (setq i (1+ i))
    
78.   )
    
79.   (report-time-consuming (strcat "构建点实体表 " (itoa (sslength ss)) "个对象"))
    
80. )
    
81. 
    
82. 
    
83. (defun c:tt (/ i pep1 pep2 ss)
    
84. 
    
85.   (get-test-data)
    
86. 
    
87.   (stop-watch-start)
    
88. 
    
89.   (vla-startundomark
    
90.     (vla-get-activedocument (vlax-get-acad-object))
    
91.   )
    
92.   (find-closest-bruteforce pep1 pep2)
    
93.   (vla-endundomark
    
94.     (vla-get-activedocument (vlax-get-acad-object))
    
95.   )
    
96.   (report-time-consuming "两次循环")
    
97. 
    
98.   (princ)
    
99. )
    
100. 
     
101. 
     
102. (defun c:tt2 (/ cur i pep1 pep2 rh1 rh2 ss tmp)
     
103. 
     
104.   (get-test-data)
     
105. 
     
106.   (setq  pep1 (sort-point-ent-pair pep1)
     
107.   pep2 (sort-point-ent-pair pep2)
     
108.   )
     
109.   (report-time-consuming "排序")
     
110. 
     
111. 
     
112.   (vla-startundomark
     
113.     (vla-get-activedocument (vlax-get-acad-object))
     
114.   )
     
115.   (while (and pep1 pep2)
     
116.     ;; 取线段表中第一个元素为游标
     
117.     (setq cur  (caar pep2)
     
118.     rh2  (list (car pep2))
     
119.     pep2 (cdr pep2)
     
120.     tmp  pep1
     
121.     )
     
122. 
     
123.     ;; 将游标附近X坐标差值在*gap*范围内的线段归集到rh2
     
124.     (while (and  pep2
     
125.     (<= (abs (- (car (caar pep2)) (car cur))) *gap*)
     
126.      )
     
127.       (setq rh2   (cons (car pep2) rh2)
     
128.       pep2 (cdr pep2)
     
129.       )
     
130.     )
     
131.     ;; 将游标附近X坐标差值在*gap*范围内的文字归集到rh1
     
132.     (while tmp
     
133.       (if (<= (abs (- (car (caar tmp)) (car cur))) *gap*)
     
134.   (setq rh1 (cons (car tmp) rh1))
     
135.   (if (< (car (caar tmp)) (car cur))
     
136.     (setq pep1 (cdr pep1))
     
137.     (setq tmp nil)
     
138.   )
     
139.       )
     
140.       (setq tmp (cdr tmp))
     
141.     )
     
142. 
     
143.     (if  (and rh1 rh2)
     
144.       (find-closest-bruteforce rh1 rh2)
     
145.     )
     
146. 
     
147.     (while rh1
     
148.       (setq pep1 (cdr pep1)
     
149.       rh1   (cdr rh1)
     
150.       )
     
151.     )
     
152.   )
     
153.   (vla-endundomark
     
154.     (vla-get-activedocument (vlax-get-acad-object))
     
155.   )
     
156.   (report-time-consuming "完成符合条件的对象标记")
     
157. 
     
158. 
     
159.   (princ)
     
160. )

(defun stop-watch-start  (/)<br />   (setq *stop-watch-start* (getvar "millisecs"))<br /> )<br /> <br /> <br /> (defun stop-watch-elapse (/)<br />   (- (getvar "millisecs") *stop-watch-start*)<br /> )<br /> <br /> (defun report-time-consuming (msg)<br />   (princ<br />     (strcat "\n" msg " (" (itoa (stop-watch-elapse)) " ms)")<br />   )<br />   (stop-watch-start)<br /> )<br /> <br /> (defun sort-point-ent-pair (pep)<br />   (setq<br /> ;;;    pep (vl-sort pep '(lambda (e1 e2) (< (caddar e1) (caddar e2))))<br /> ;;;  pep (vl-sort pep '(lambda (e1 e2) (< (cadar e1) (cadar e2))))<br />     pep<br />      (vl-sort pep '(lambda (e1 e2) (< (caar e1) (caar e2))))<br />   )<br />   pep<br /> )<br /> <br /> <br /> (defun find-closest-bruteforce (pep1 pep2 / tmp)<br />   (setq tmp pep1)<br />   (while pep2<br />     (while tmp<br />       (if (<= (distance (caar tmp) (caar pep2)) *gap*)<br />   (vla-put-color (vlax-ename->vla-object (cadar tmp)) 1)<br />       )<br />       (setq tmp (cdr tmp))<br />     )<br />     (setq tmp  pep1<br />     pep2 (cdr pep2)<br />     )<br />   )<br /> )<br /> <br /> <br /> (defun get-point-ent-pair (ent / dxf)<br />   (setq dxf (entget ent))<br />   (cond<br />     ((= "TEXT" (cdr (assoc 0 dxf)))<br />      (setq pep1 (cons (list (cdr (assoc 10 dxf)) ent) pep1))<br />     )<br />     ((= "LINE" (cdr (assoc 0 dxf)))<br />      (setq pep2<br />       (cons<br />         (list<br />     (mapcar<br />       '(lambda (e) (/ e 2.0))<br />       (mapcar '+ (cdr (assoc 10 dxf)) (cdr (assoc 11 dxf)))<br />     )<br />     ent<br />         )<br />         pep2<br />       )<br />      )<br />     )<br />   )<br /> )<br /> <br /> <br /> (defun get-test-data ()<br />   (setq  ss    (ssget '((0 . "LINE,TEXT")))<br />   i     0<br />   *gap* 50.0<br />   )<br />   (stop-watch-start)<br /> <br />   (repeat (sslength ss)<br />     (get-point-ent-pair (ssname ss i))<br />     (setq i (1+ i))<br />   )<br />   (report-time-consuming (strcat "构建点实体表 " (itoa (sslength ss)) "个对象"))<br /> )<br /> <br /> <br /> (defun c:tt (/ i pep1 pep2 ss)<br /> <br />   (get-test-data)<br /> <br />   (stop-watch-start)<br /> <br />   (vla-startundomark<br />     (vla-get-activedocument (vlax-get-acad-object))<br />   )<br />   (find-closest-bruteforce pep1 pep2)<br />   (vla-endundomark<br />     (vla-get-activedocument (vlax-get-acad-object))<br />   )<br />   (report-time-consuming "两次循环")<br /> <br />   (princ)<br /> )<br /> <br /> <br /> (defun c:tt2 (/ cur i pep1 pep2 rh1 rh2 ss tmp)<br /> <br />   (get-test-data)<br /> <br />   (setq  pep1 (sort-point-ent-pair pep1)<br />   pep2 (sort-point-ent-pair pep2)<br />   )<br />   (report-time-consuming "排序")<br /> <br /> <br />   (vla-startundomark<br />     (vla-get-activedocument (vlax-get-acad-object))<br />   )<br />   (while (and pep1 pep2)<br />     ;; 取线段表中第一个元素为游标<br />     (setq cur  (caar pep2)<br />     rh2  (list (car pep2))<br />     pep2 (cdr pep2)<br />     tmp  pep1<br />     )<br /> <br />     ;; 将游标附近X坐标差值在*gap*范围内的线段归集到rh2<br />     (while (and  pep2<br />     (<= (abs (- (car (caar pep2)) (car cur))) *gap*)<br />      )<br />       (setq rh2   (cons (car pep2) rh2)<br />       pep2 (cdr pep2)<br />       )<br />     )<br />     ;; 将游标附近X坐标差值在*gap*范围内的文字归集到rh1<br />     (while tmp<br />       (if (<= (abs (- (car (caar tmp)) (car cur))) *gap*)<br />   (setq rh1 (cons (car tmp) rh1))<br />   (if (< (car (caar tmp)) (car cur))<br />     (setq pep1 (cdr pep1))<br />     (setq tmp nil)<br />   )<br />       )<br />       (setq tmp (cdr tmp))<br />     )<br /> <br />     (if  (and rh1 rh2)<br />       (find-closest-bruteforce rh1 rh2)<br />     )<br /> <br />     (while rh1<br />       (setq pep1 (cdr pep1)<br />       rh1   (cdr rh1)<br />       )<br />     )<br />   )<br />   (vla-endundomark<br />     (vla-get-activedocument (vlax-get-acad-object))<br />   )<br />   (report-time-consuming "完成符合条件的对象标记")<br /> <br /> <br />   (princ)<br /> )

命令: 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万个对象。

革天明

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

bzhjl

很赞，支持一个

ljxkm

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

masterlong

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

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

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

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

masterlong

●●●●简单线字关系●●●●数量较少————————————————直线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

vectra

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

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

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

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

masterlong

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

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

llsheng_73

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