lisp能否实现四叉树算法？

dcl1214

你有种再说一遍 发表于 2024-3-13 16:40
要把优化进行到底,想想导航软件要是20秒出结果,那你也不用了,所以太长时间的操作只能是玩具,图算法不就是 ...

地图导航的时候，你从起点到终点，就一条数据，我说的四万是不同的起点和终点，单线程共计耗时20秒，仔细用脑想想

地图导航的方法可能更加简单了，比如说，你从北京到上海，那么可以在程序里面先导航省份到省份，因为省份到省份就几个高速路口，然后进入到省份的高速路口以后，再次调用城市的出入口，意思是可以区块化导航，该省略的节点信息可以省略掉，只用关键节点作为寻址

dcl1214

(defun c:zdlj (/     a           b         dxf   dxf2  ents  ents2 es    jb
               jb2   jb-ks jb-pt jdcds l     old   old-cdr     p
               p2    ss
              )
        ;最短路径
  (vl-catch-all-apply 'load (list (findfile "zdlj.vlx")))
                                        ;声明引用zdlj.vlx这个模块
  (vl-catch-all-apply 'vl-doc-import (list "zdlj")) ;声明引用函数
  (SETQ JDCDS NIL)
  (SETQ ES NIL)
  (setq jb-pt nil)
  (SETQ SS (SSGET))
  (and ss(setq        ents (vl-remove-if
               (function listp)
               (mapcar (function cadr) (ssnamex SS))
             )
  ))
  (setq jb-ks nil)
  (while (setq a (car ents))
    (setq dxf nil)
    (setq jb nil)
    (setq p nil)
    (setq ents2 nil)
    (setq dxf (entget a))
    (setq jb (cdr (assoc 5 dxf)))
    (setq p (cdr (assoc 10 dxf)))
    (setq ents2 (cdr ents))
    (while (setq b (car ents2))
      (setq dxf2 nil)
      (setq jb2 nil)
      (setq p2 nil)
      (setq l nil)
      (setq old nil)
      (setq old-cdr nil)
      (setq dxf2 (entget B))
      (setq jb2 (cdr (assoc 5 dxf2)))
      (setq p2 (cdr (assoc 10 dxf2)))
      (SETQ L (DISTANCE P P2))
      (SETQ L (VL-PRINC-TO-STRING L))
      (setq old (assoc jb jb-ks));建立索引
      (setq old-cdr (cdr old))
      (setq old-cdr (cons (CONS (cons JB JB2) L) old-cdr))
      (setq jb-ks (vl-remove old jb-ks))
      (setq jb-ks (cons (cons jb old-cdr) jb-ks)) ;建立数据库索引
      (setq ents2 (cdr ents2))
    )
    (setq jb-pt (cons (cons jb p) jb-pt)) ;建立数据库索引
    (setq ents (cdr ents))
  )
  (setq
    jb-ks
     (mapcar
       (function
         (lambda (a)
           (cons
             (car a)
             (vl-sort (cdr a)
                      (function (lambda (x y) (< (cdr x) (cdr y))))
             )
           )
         )
       )
       jb-ks
     )
  )
  (setq jb-ks (reverse jb-ks))
  (mapcar (function (lambda (a / e1 e2 p1 p2)
                      (setq e1 (car a))
                      (setq e2 (cdr (car (car (cdr a)))))
                      (setq p1 (cdr (assoc e1 jb-pt))) ;启用索引
                      (setq p2 (cdr (assoc e2 jb-pt))) ;启用索引
                      (and p1
                           p2
                           (vla-addLine
                             (vla-Get-ModelSpace
                               (vla-get-ActiveDocument
                                 (vlax-get-acad-object)
                               )
                             )
                             (vlax-3D-Point p1)
                             (vlax-3D-Point p2)
                           )
                      )
                    )
          )
          jb-ks
  )
)

Gu_xl

我觉得根据楼主题意，既然是在AutoCAD 的图上，那我们首要就是要充分利用AutoCAD本身的功能来实现目标，而不是去讨论算法什么的，这不是它的强项！下面是实现按半径查找代码，不管图上有多少个点，速度都很快！

1. ;;参数 pt 位置点坐标
   
2. ;;     jd 查找半径
   
3. (defun gxl-sel-SSgetByPoint (pt jd / px py px0 px1 py0 py1 ss pz rtn e)
   
4.   (setq  px  (car pt)
   
5.   px0 (- px jd)
   
6.   px1 (+ px jd)
   
7.   py  (cadr pt)
   
8.   py0 (- py jd)
   
9.   py1 (+ py jd)
   
10.   pz 1e99
    
11.   )
    
12. 
    
13.   (setq  ss
    
14.    (ssget  "x"
    
15.     (list '(0 . "point")
    
16.           '(-4 . "<and")
    
17.           '(-4 . ">=,>=,<>")
    
18.           (list 10 px0 py0 pz)
    
19.           '(-4 . "<=,<=,<>")
    
20.           (list 10 px1 py1 pz)
    
21.           '(-4 . "and>")
    
22.     )
    
23.    )
    
24.   )
    
25.   (if ss
    
26.     (progn
    
27.       (repeat (setq n (sslength ss))
    
28.   (if (<= (distance (list (car pt) (cadr pt)) (cdr (assoc 10 (entget (setq e (ssname ss (setq n (1- n)))))))) jd)
    
29.     (setq rtn (cons e rtn))
    
30.     )
    
31.   )
    
32.       )
    
33.   )
    
34.   ;;颜色变红提示
    
35.   (foreach e rtn (entmod (append (entget e) '((62 . 1)))))
    
36.   ;;返回选中点图元名列表
    
37.   rtn
    
38. )
    
39. ;;测试
    
40. (defun c:tt (/ pt jd)
    
41.   (setq rtn (gxl-sel-SSgetByPoint (setq pt (getpoint "\n位置点:")) (setq jd (getdist pt "\n半径:"))))
    
42.   (command "circle" "_non" pt jd)
    
43.   (princ (strcat "\n选中" (itoa (length rtn)) "个点."))
    
44.   (princ)
    
45.   )

;;参数 pt 位置点坐标<br /> ;;     jd 查找半径<br /> (defun gxl-sel-SSgetByPoint (pt jd / px py px0 px1 py0 py1 ss pz rtn e)<br />   (setq  px  (car pt)<br />   px0 (- px jd)<br />   px1 (+ px jd)<br />   py  (cadr pt)<br />   py0 (- py jd)<br />   py1 (+ py jd)<br />   pz 1e99<br />   )<br /> <br />   (setq  ss<br />    (ssget  "x"<br />     (list '(0 . "point")<br />           '(-4 . "<and")<br />           '(-4 . ">=,>=,<>")<br />           (list 10 px0 py0 pz)<br />           '(-4 . "<=,<=,<>")<br />           (list 10 px1 py1 pz)<br />           '(-4 . "and>")<br />     )<br />    )<br />   )<br />   (if ss<br />     (progn<br />       (repeat (setq n (sslength ss))<br />   (if (<= (distance (list (car pt) (cadr pt)) (cdr (assoc 10 (entget (setq e (ssname ss (setq n (1- n)))))))) jd)<br />     (setq rtn (cons e rtn))<br />     )<br />   )<br />       )<br />   )<br />   ;;颜色变红提示<br />   (foreach e rtn (entmod (append (entget e) '((62 . 1)))))<br />   ;;返回选中点图元名列表<br />   rtn<br /> )<br /> ;;测试<br /> (defun c:tt (/ pt jd)<br />   (setq rtn (gxl-sel-SSgetByPoint (setq pt (getpoint "\n位置点:")) (setq jd (getdist pt "\n半径:"))))<br />   (command "circle" "_non" pt jd)<br />   (princ (strcat "\n选中" (itoa (length rtn)) "个点."))<br />   (princ)<br />   )

你有种再说一遍

dcl1214 发表于 2024-3-14 12:30
地图导航的时候，你从起点到终点，就一条数据，我说的四万是不同的起点和终点，单线程共计耗时20秒，仔细 ...

那你试试double改float能快多少

20060510412

Gu_xl 发表于 2024-3-14 16:09
我觉得根据楼主题意，既然是在AutoCAD 的图上，那我们首要就是要充分利用AutoCAD本身的功能来实现目标，而 ...

顾版好，其实我本来的目的，是想找出距离某多段线特定距离范围内的点。

本来想的是对多段线进行偏移，使用形成的封闭区域再配合ssget，进行筛选。但是该方法的弊端，就是有时候多段线偏移之后无法形成有效的封闭区域。

全部遍历，根据每个点到多段线的距离进行筛选，效率又不高，所以才想到能否用四叉树的算法。

Gu_xl

20060510412 发表于 2024-3-14 19:09
顾版好，其实我本来的目的，是想找出距离某多段线特定距离范围内的点。

本来想的是对多段线进行偏移， ...

先按直线包围框用(ssget "x" )方法选出点，然后再逐点判断距离，可以大大减小计算量。

20060510412

Gu_xl 发表于 2024-3-15 08:54
先按直线包围框用(ssget "x" )方法选出点，然后再逐点判断距离，可以大大减小计算量。

谢谢顾版，目前用lisp的话，应该只能通过ssget的方式，减小计算量。
肯定比全部遍历要高效得多。

guosheyang

多段线偏移之后无法形成有效的封闭区域 的情况     应该是偏移距离过大  造成自相交了   将偏移距离减小些就可以

20060510412

guosheyang 发表于 2024-3-16 12:59
多段线偏移之后无法形成有效的封闭区域 的情况     应该是偏移距离过大  造成自相交了   将偏移距离减小些 ...

是的，所以说偏移多段线的方法不通用。

还是取最小包围盒，更通用一些。

dcl1214

你有种再说一遍 发表于 2024-3-14 16:14
那你试试double改float能快多少

跟这个没关系的，路径计算一定是先找到路径，最后计算，而不是一边找路径，一边计算