[讨论]：大家多讨论一下有关计算几何的算法，写出一些函数来，我先来两个：求凸集、凹

xiao_longxin · 发表于 2006-4-22 20:17:15

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

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

×

其中用到了很多通用函数，请这里下载
http://p4.xdcad.net/forum/showthread.php?s=&threadid=547917

求得逆时针多边形凸点的顶点序号

;;By Longxin 明经通道 2006.03
;;求得逆时针多边形凸点的顶点序号
;;参数：
;;多边形图元名或者多边形坐标例表
;;返回：凸点的顶点序号
(defun dbx_tudian (ename / plist tu_list n i gd)
(if (= (type ename) 'ENAME)
(setq plist (coords ename)) ;如果参数为图元名则取得多边形的顶点坐标
(progn
(setq plist ename)
)
)
(if (not (PlineCCW plist))
(setq plist (reverse plist)) ;如果多边形不为逆时针则反向
)
;;注意，此多边形必须是逆时针的!!!!!!!
;;依次判断多边形顶点的凹凸性,如为凹点则依次记录其在多边形中的序号到AO_LIST中
;;逆时针时，当点Pi+1在线Pi-1--Pi右则时为凹点，在左则或线上时为凸点
(setq n (length plist))
(if (= n 3)
(setq tu_list plist);;如果为三角形，则全为凸点
(progn;;参数大于三个坐标点
(setq gd (pntonline (nth (- n 2) plist)
(nth (- n 1) plist)
(nth 0 plist)
5
)
)
(if (or (> gd
0
)
(= gd 0)
)
(setq tu_list (append tu_list (list (- n 1))))
)
(setq n (length plist)
gd (pntonline (nth (- n 1) plist)
(nth 0 plist)
(nth 1 plist)
5
)
)
(if (or (> gd
0
)
(= gd 0)
)
(setq tu_list (append tu_list (list 0)))
)
(setq i 2)
(repeat (- n 2)
(setq gd (pntonline (nth (- i 2) plist)
(nth (- i 1) plist)
(nth i plist)
5
)
)
(if (or (> gd
0
)
(= gd 0)
)
(setq tu_list (append tu_list (list (- i 1))))
)
(setq i (1+ i))
)
;;end依次判断多边形顶点的凹凸性
);;end 参数大于三个坐标点
)
tu_list
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;(defun c:test ()
;;(setq ename (car (entsel)))
;;(setq plist (coords ename) ;取得多边形的顶点坐标
;; n (length plist)
;;)
;;(if (not (PlineCCW ename))
;; (setq plist (reverse plist)) ;如果多边形不为逆时针则反向
;; )
;;求得多边形凹点的集合
;; (setq ao_list (dbx_tudian plist))
;;)

;;By Longxin 明经通道 2006.03 
;;求得逆时针多边形凸点的顶点序号 
;;参数： 
;;多边形图元名或者多边形坐标例表 
;;返回：凸点的顶点序号 
(defun dbx_tudian (ename / plist tu_list n i gd) 
  (if (= (type ename) 'ENAME) 
    (setq plist (coords ename))                ;如果参数为图元名则取得多边形的顶点坐标 
    (progn 
      (setq plist ename) 
    ) 
  ) 
  (if (not (PlineCCW plist)) 
    (setq plist (reverse plist))        ;如果多边形不为逆时针则反向 
  ) 
  ;;注意，此多边形必须是逆时针的!!!!!!! 
  ;;依次判断多边形顶点的凹凸性,如为凹点则依次记录其在多边形中的序号到AO_LIST中 
  ;;逆时针时，当点Pi+1在线Pi-1--Pi右则时为凹点，在左则或线上时为凸点 
  (setq n (length plist)) 
  (if (= n 3) 
    (setq tu_list plist);;如果为三角形，则全为凸点 
    (progn;;参数大于三个坐标点 
      (setq gd (pntonline (nth (- n 2) plist) 
                          (nth (- n 1) plist) 
                          (nth 0 plist) 
                          5 
               ) 
      ) 
 
      (if (or (> gd 
                 0 
              ) 
              (= gd 0) 
          ) 
        (setq tu_list (append tu_list (list (- n 1)))) 
      ) 
 
      (setq n  (length plist) 
            gd (pntonline (nth (- n 1) plist) 
                          (nth 0 plist) 
                          (nth 1 plist) 
                          5 
               ) 
      ) 
 
      (if (or (> gd 
                 0 
              ) 
              (= gd 0) 
          ) 
        (setq tu_list (append tu_list (list 0))) 
      ) 
 
      (setq i 2) 
      (repeat (- n 2) 
        (setq gd (pntonline (nth (- i 2) plist) 
                            (nth (- i 1) plist) 
                            (nth i plist) 
                            5 
                 ) 
        ) 
        (if (or        (> gd 
                   0 
                ) 
                (= gd 0) 
            ) 
          (setq tu_list (append tu_list (list (- i 1)))) 
        ) 
        (setq i (1+ i)) 
      ) 
      ;;end依次判断多边形顶点的凹凸性 
    );;end 参数大于三个坐标点 
  ) 
  tu_list 
) 
 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
;;(defun c:test () 
;;(setq ename (car (entsel))) 
;;(setq        plist (coords ename)                ;取得多边形的顶点坐标 
;;        n     (length plist) 
;;) 
;;(if (not (PlineCCW ename)) 
;;   (setq plist (reverse plist))        ;如果多边形不为逆时针则反向 
;; ) 
;;求得多边形凹点的集合 
;; (setq ao_list (dbx_tudian plist)) 
 
;;)

求得逆时针多边形凹点的顶点序号

;;By Longxin 明经通道 2006.03
;;求得逆时针多边形凹点的顶点序号
;;参数：
;;多边形图元名或者多边形坐标例表
;;返回：凹点的顶点序号
(defun dbx_aodian (ename / plist ao_list n i)
(if (= (type ename) 'ENAME)
(setq plist (coords ename)) ;如果参数为图元名则取得多边形的顶点坐标
(progn
(setq plist ename)
)
)
(if (not (PlineCCW plist))
(setq plist (reverse plist)) ;如果多边形不为逆时针则反向
)
;;注意，此多边形必须是逆时针的!!!!!!!
;;依次判断多边形顶点的凹凸性,如为凹点则依次记录其在多边形中的序号到AO_LIST中
;;逆时针时，当点Pi+1在线Pi-1--Pi右则时为凹点，在左则或线上时为凸点
(setq n (length plist))
(if (< (pntonline (nth (- n 2) plist)
(nth (- n 1) plist)
(nth 0 plist)
5
)
0
)
(setq ao_list (append ao_list (list (- n 1))))
)
(if (< (pntonline (nth (- n 1) plist)
(nth 0 plist)
(nth 1 plist)
5
)
0
)
(setq ao_list (append ao_list (list 0)))
)
(setq i 2)
(repeat (- n 2)
(if (< (pntonline (nth (- i 2) plist)
(nth (- i 1) plist)
(nth i plist)
5
)
0
)
(setq ao_list (append ao_list (list (- i 1))))
)
(setq i (1+ i))
)
;;end依次判断多边形顶点的凹凸性
ao_list
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;(defun c:test ()
;;(setq ename (car (entsel)))
;;(setq plist (coords ename) ;取得多边形的顶点坐标
;; n (length plist)
;;)
;;(if (not (PlineCCW ename))
;; (setq plist (reverse plist)) ;如果多边形不为逆时针则反向
;; )
;;求得多边形凹点的集合
;; (setq ao_list (dbx_aodian plist))
;;)

;;By Longxin 明经通道 2006.03 
;;求得逆时针多边形凹点的顶点序号 
;;参数： 
;;多边形图元名或者多边形坐标例表 
;;返回：凹点的顶点序号 
(defun dbx_aodian (ename / plist ao_list n i) 
  (if (= (type ename) 'ENAME) 
    (setq plist (coords ename))                ;如果参数为图元名则取得多边形的顶点坐标 
    (progn 
      (setq plist ename) 
    ) 
  ) 
  (if (not (PlineCCW plist)) 
    (setq plist (reverse plist))        ;如果多边形不为逆时针则反向 
  ) 
  ;;注意，此多边形必须是逆时针的!!!!!!! 
  ;;依次判断多边形顶点的凹凸性,如为凹点则依次记录其在多边形中的序号到AO_LIST中 
  ;;逆时针时，当点Pi+1在线Pi-1--Pi右则时为凹点，在左则或线上时为凸点 
  (setq n (length plist)) 
  (if (< (pntonline (nth (- n 2) plist) 
                    (nth (- n 1) plist) 
                    (nth 0 plist) 
                    5 
         ) 
         0 
      ) 
    (setq ao_list (append ao_list (list (- n 1)))) 
  ) 
  (if (< (pntonline (nth (- n 1) plist) 
                    (nth 0 plist) 
                    (nth 1 plist) 
                    5 
         ) 
         0 
      ) 
    (setq ao_list (append ao_list (list 0))) 
  ) 
  (setq i 2) 
  (repeat (- n 2) 
    (if        (< (pntonline (nth (- i 2) plist) 
                      (nth (- i 1) plist) 
                      (nth i plist) 
                      5 
           ) 
           0 
        ) 
      (setq ao_list (append ao_list (list (- i 1)))) 
    ) 
    (setq i (1+ i)) 
  ) 
  ;;end依次判断多边形顶点的凹凸性 
  ao_list 
) 
 
 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
;;(defun c:test () 
;;(setq ename (car (entsel))) 
;;(setq        plist (coords ename)                ;取得多边形的顶点坐标 
;;        n     (length plist) 
;;) 
;;(if (not (PlineCCW ename)) 
;;   (setq plist (reverse plist))        ;如果多边形不为逆时针则反向 
;; ) 
;;求得多边形凹点的集合 
;; (setq ao_list (dbx_aodian plist)) 
 
;;)

求多边形的凸壳

;;(defun c:test ()
;; (dbx_tuke (car (entsel)))
;;)
;;By Longxin 明经通道 2006.03
;;参数：多边形图元名或者多边形坐标例表
;;返回：多边形坐标例表
(defun dbx_tuke (ename / n j plist tuke_list tu_list)
(if (= (type ename) 'ENAME)
(setq plist (coords ename)) ;如果参数为图元名则取得多边形的顶点坐标
(progn
(setq plist ename)
)
)
(setq n (length plist)) ;求得多边形顶点个数
(if (not (PlineCCW ename))
(setq plist (reverse plist)) ;如果多边形不为逆时针则反向
)
(setq tu_list (dbx_tudian plist)
j (length tu_list) ;求得多边形的凸点的个数
)
(if (= j n)
(setq tuke_list plist) ;如果凸点个数与多边形顶点数相等，则些多边形为凸多边形，其核是其本身
(setq tuke_list (dbx_tuke_1 plist tu_list)) ;否则要进一步处理
)
;;(makepline tuke_list 1 0 nil)
)
;;;;
(defun dbx_tuke_1
(plist tu_list / pd0 pd1 pd2 pd3
i j n p k temp1 ddxh ddxh+1
pt
)
(setq pd1 t
pd0 t
)
(while pd1
(if pd0
(setq plist (dbx_tuke_2 plist tu_list))
)
;循环删除凹点，组成新多边形，直到组成凸多边形
(setq n (length plist)
i 0
pd2 t
)
(while pd2 ;检测j点是否在PI--PI+1边的右边(j>i<n)
(setq ddxh i
ddxh+1 (+ i 1)
)
(if (= ddxh+1 n)
(setq ddxh+1 0)
)
(setq j (+ i 2)
pd3 t
)
(while pd3
(setq temp1 (pntonline (nth ddxh plist)
(nth ddxh+1 plist)
(nth j plist)
5
)
)
(if (< temp1 0)
(progn ;如果顶点J点在边PI--PI+1右边，
(setq k (+ i 1))
(repeat (- j i 1) ;则删除i与J之间的顶点，组成新的多边形,
(setq temp1 (nth k plist)
plist (vl-remove temp1 plist)
)
)
;;重新检测多边形各顶点的凹凸性
(setq temp1 (length plist)) ;多边形顶点个数
(setq tu_list (dbx_tudian plist) ;求得多边形的凸点的序号
k (length tu_list) ;求得多边形的凸点的个数
)
(if (= k temp1)
(setq pd nil)
(setq pd t)
)
(setq pd3 nil ;跳出第三、第二循环，
pd2 nil
)
)
) ;end if
(setq j (1+ j))
(if (= j n)
(setq pd3 nil) ;超出多边形顶点个数，跳出循环
)
) ;end while pd3
(setq i (1+ i))
(if (= i (- n 2)) ;当达到到数第二条边时，结束三重循环
(progn
(setq pd3 nil
pd2 nil
pd1 nil
)
)
)
) ;end while pd2
) ;end while pd1
plist
)
;;;;循环删除凹点，组成新多边形，直到组成凸多边形
(defun dbx_tuke_2 (plist tu_list / pd j n temp1)
(setq pd t)
;;;检测多边形是否还有凹点，直到没有为止
(while pd
;;;;由凸点组成新的多边形
(setq n (length tu_list)
temp1 nil
j 0
)
(repeat n
(setq temp1 (append temp1 (list (nth (nth j tu_list) plist)))
j (1+ j)
)
)
(setq plist temp1)
;;;;end由凸点组成新的多边形
;;重新检测多边形的凸点个数
(setq tu_list (dbx_tudian plist) ;求得多边形的凸点的序号
j (length tu_list) ;求得多边形的凸点的个数
)
(if (= j n)
(setq pd nil) ;如果全部为凸点，则跳出循环
)
)
;;(makepline plist 1 0 nil)
plist
)

;;(defun c:test () 
 ;; (dbx_tuke (car (entsel))) 
;;) 
;;By Longxin 明经通道 2006.03 
;;参数：多边形图元名或者多边形坐标例表 
;;返回：多边形坐标例表 
 
(defun dbx_tuke        (ename / n j plist tuke_list tu_list) 
  (if (= (type ename) 'ENAME) 
    (setq plist (coords ename))                ;如果参数为图元名则取得多边形的顶点坐标 
    (progn 
      (setq plist ename) 
    ) 
  ) 
  (setq n (length plist))                ;求得多边形顶点个数 
  (if (not (PlineCCW ename)) 
    (setq plist (reverse plist))        ;如果多边形不为逆时针则反向 
  ) 
 
  (setq        tu_list        (dbx_tudian plist) 
        j        (length tu_list)        ;求得多边形的凸点的个数 
  ) 
  (if (= j n) 
    (setq tuke_list plist)                ;如果凸点个数与多边形顶点数相等，则些多边形为凸多边形，其核是其本身 
    (setq tuke_list (dbx_tuke_1 plist tu_list)) ;否则要进一步处理 
  ) 
  ;;(makepline tuke_list 1 0 nil) 
) 
 
 
;;;; 
(defun dbx_tuke_1 
                  (plist tu_list     /           pd0         pd1   pd2   pd3 
                   i         j     n     p           k         temp1 ddxh  ddxh+1 
                   pt 
                  ) 
  (setq        pd1 t 
        pd0 t 
  ) 
  (while pd1 
    (if        pd0 
      (setq plist (dbx_tuke_2 plist tu_list)) 
    ) 
                                        ;循环删除凹点，组成新多边形，直到组成凸多边形 
    (setq n   (length plist) 
          i   0 
          pd2 t 
    ) 
    (while pd2                                ;检测j点是否在PI--PI+1边的右边(j>i<n) 
      (setq ddxh   i 
            ddxh+1 (+ i 1) 
      ) 
      (if (= ddxh+1 n) 
        (setq ddxh+1 0) 
      ) 
 
      (setq j        (+ i 2) 
            pd3        t 
      ) 
      (while pd3 
        (setq temp1 (pntonline (nth ddxh plist) 
                               (nth ddxh+1 plist) 
                               (nth j plist) 
                               5 
                    ) 
        ) 
        (if (< temp1 0) 
          (progn                        ;如果顶点J点在边PI--PI+1右边， 
            (setq k (+ i 1)) 
            (repeat (- j i 1)                ;则删除i与J之间的顶点，组成新的多边形, 
              (setq temp1 (nth k plist) 
                    plist (vl-remove temp1 plist) 
              ) 
            ) 
            ;;重新检测多边形各顶点的凹凸性 
            (setq temp1 (length plist))        ;多边形顶点个数 
            (setq tu_list (dbx_tudian plist) ;求得多边形的凸点的序号 
                  k          (length tu_list) ;求得多边形的凸点的个数 
            ) 
            (if        (= k temp1) 
              (setq pd nil) 
              (setq pd t) 
            ) 
            (setq pd3 nil                ;跳出第三、第二循环， 
                  pd2 nil 
            ) 
          ) 
        )                                ;end if 
        (setq j (1+ j)) 
        (if (= j n) 
          (setq pd3 nil)                ;超出多边形顶点个数，跳出循环 
        ) 
      )                                        ;end while pd3 
      (setq i (1+ i)) 
      (if (= i (- n 2))                        ;当达到到数第二条边时，结束三重循环 
        (progn 
          (setq        pd3 nil 
                pd2 nil 
                pd1 nil 
          ) 
        ) 
      ) 
    )                                        ;end while pd2 
  )                                        ;end while pd1 
  plist 
) 
 
 
;;;;循环删除凹点，组成新多边形，直到组成凸多边形 
(defun dbx_tuke_2 (plist tu_list / pd j n temp1) 
  (setq pd t) 
;;;检测多边形是否还有凹点，直到没有为止 
  (while pd 
;;;;由凸点组成新的多边形 
    (setq n        (length tu_list) 
          temp1        nil 
          j        0 
    ) 
    (repeat n 
      (setq temp1 (append temp1 (list (nth (nth j tu_list) plist))) 
            j          (1+ j) 
      ) 
    ) 
    (setq plist temp1) 
;;;;end由凸点组成新的多边形 
    ;;重新检测多边形的凸点个数 
    (setq tu_list (dbx_tudian plist)        ;求得多边形的凸点的序号 
          j          (length tu_list)        ;求得多边形的凸点的个数 
    ) 
    (if        (= j n) 
      (setq pd nil)                        ;如果全部为凸点，则跳出循环 
    ) 
  ) 
  ;;(makepline plist 1 0 nil) 
  plist 
)

求任意多边形内一点

;;(defun c:test ()
;;(dbx_in_point (car (entsel)))
;;)
;;By Longxin 明经通道 2006.03
;;参数：多边形图元名或者多边形的坐标例表(注，只适合于多折线)
;;返回：(x y z)
(defun in_point_dbx
(ename / n i pd plist
he_list ao_list ang dist pt1 pt2
pt temp1 new_ename
)
(setq new_ename ename)
(if (= (type ename) 'ENAME)
(setq plist (coords ename)) ;如果参数为图元名则取得多边形的顶点坐标
(progn ;如果参数不为图元名则生成一个新图元
(setq plist ename)
(makepline plist 1 0 nil)
(setq ename (entlast))
)
)
(setq n (length plist)) ;求得多边形顶点个数
(if (not (PlineCCW ename))
(setq plist (reverse plist)) ;如果多边形不为逆时针则反向
)
;;求得多边形凹点的集合
(setq ao_list (dbx_aodian plist))
(if (not ao_list)
;;如果ao_list为空，则说明此多边形为凸多边形，则任意一条边的中点与第三点顶点的连线上的点都在多边形内
(progn
(setq pt1 (nth 0 plist)
pt2 (nth 1 plist)
ang (angle pt1 pt2)
i 2
)
(while (not pd)
(setq pt (nth i plist)
temp1 (angle pt2 pt)
)
(if (or (> (abs (- temp1 ang)) 0.000005) (= i n))
(setq pd t)
(setq i (1+ i))
)
)
(setq dist (distance pt1 pt2)
pt1 (polar pt1 ang (/ dist 2))
ang (angle pt1 pt)
dist (distance pt1 pt)
pt (polar pt1 ang (/ dist 2))
)
)
(setq pt (dbx_in_point_1 plist ao_list ename))
;如果不为空则要进一步处理
)
;;(command ".point" pt)
(if (= (type new_ename) 'LIST)
(ENTDEL ENAME) ;如果参数为LIST，因为生成了一个新图元，所以要删除之
)
PT
)
;;;处理函数
(defun dbx_in_point_1 (plist ao_list ename / n i
p n_plist gd1 gd2 ddxh ddxh-1
pt pt-1 l1 ang1 jd1 dist j
temp1 temp2
)
(setq oldcmdecho (getvar "cmdecho"))
(setvar "cmdecho" 0)
(setq i 0
n (length ao_list)
n_plist (length plist)
)
;;求得凹点和与此凹点相连的两点ddxh-1的序号
(setq ddxh (nth i ao_list)
ddxh-1 (- ddxh 1)
)
(cond ((= ddxh-1 -1)
(setq ddxh-1 (- n_plist 1))
)
((= ddxh-1 n_plist)
(setq ddxh-1 0)
)
)
;;求得三点的坐标,及PT---PT-1(L1)向量的方位角
(setq pt (nth ddxh plist)
pt-1 (nth ddxh-1 plist)
ang1 (angle pt-1 pt)
)
;;构造以ang1方位的矢量
(setq gd2 (getbox ename) ;取得多边形的矩形外框
gd2 (+ 100 (distance (nth 0 gd2) (nth 1 gd2)))
gd2 (cons 10 (polar pt ang1 gd2))
gd1 (cons 11 pt)
)
(entmake (list
'(0
.
"line"
)
'(8 . "0")
gd2
gd1
)
)
(setq l1 (entlast)) ;取得l1图元名
;;求得l1与多边形的交点坐标例表的表
(setq jd1 (GetInterPointlist ename l1))
(entdel l1)
;;剔除凹点本身
(setq p (length jd1)
j 0
temp2 nil
)
(repeat p
(setq temp1 (nth j jd1))
(if (not (equal pt temp1 0.00001))
(setq temp2 (append temp2 (list temp1)))
)
(setq j (1+ j))
)
(setq jd1 temp2)
;;交点的个
(setq n (length jd1)
i 0
dist "(min "
)
;;计算各交点与凹点的距离，最近点(本身除外)与凹点的连线的线段必在多边形内
(repeat n
(setq gd1 (distance pt (nth i jd1)))
(setq dist (strcat dist (rtos gd1 2) " "))
(setq i (1+ i))
)
(setq dist (eval (read (strcat dist ")")))
dist (polar pt ang1 (/ dist 2))
)
)
(

;;(defun c:test () 
;;(dbx_in_point (car (entsel))) 
;;) 
;;By Longxin 明经通道 2006.03 
;;参数：多边形图元名或者多边形的坐标例表(注，只适合于多折线) 
;;返回：(x y z) 
(defun in_point_dbx 
                    (ename   /             n             i             pd             plist 
                     he_list ao_list ang     dist    pt1     pt2 
                     pt             temp1   new_ename 
                    ) 
  (setq new_ename ename) 
  (if (= (type ename) 'ENAME) 
    (setq plist (coords ename))                ;如果参数为图元名则取得多边形的顶点坐标 
    (progn                                ;如果参数不为图元名则生成一个新图元 
      (setq plist ename) 
      (makepline plist 1 0 nil) 
      (setq ename (entlast)) 
    ) 
  ) 
  (setq n (length plist))                ;求得多边形顶点个数 
 
  (if (not (PlineCCW ename)) 
    (setq plist (reverse plist))        ;如果多边形不为逆时针则反向 
  ) 
 
  ;;求得多边形凹点的集合 
  (setq ao_list (dbx_aodian plist)) 
 
  (if (not ao_list) 
    ;;如果ao_list为空，则说明此多边形为凸多边形，则任意一条边的中点与第三点顶点的连线上的点都在多边形内 
    (progn 
      (setq pt1        (nth 0 plist) 
            pt2        (nth 1 plist) 
            ang        (angle pt1 pt2) 
            i        2 
      ) 
      (while (not pd) 
        (setq pt    (nth i plist) 
              temp1 (angle pt2 pt) 
        ) 
        (if (or (> (abs (- temp1 ang)) 0.000005) (= i n)) 
          (setq pd t) 
          (setq i (1+ i)) 
        ) 
      ) 
      (setq dist (distance pt1 pt2) 
            pt1         (polar pt1 ang (/ dist 2)) 
            ang         (angle pt1 pt) 
            dist (distance pt1 pt) 
            pt         (polar pt1 ang (/ dist 2)) 
      ) 
    ) 
    (setq pt (dbx_in_point_1 plist ao_list ename)) 
                                        ;如果不为空则要进一步处理 
  ) 
  ;;(command ".point" pt) 
  (if (= (type new_ename) 'LIST) 
    (ENTDEL ENAME)                        ;如果参数为LIST，因为生成了一个新图元，所以要删除之 
  ) 
  PT 
) 
 
;;;处理函数 
(defun dbx_in_point_1 (plist  ao_list            ename  /          n         i 
                       p      n_plist            gd1           gd2          ddxh         ddxh-1 
                       pt     pt-1   l1            ang1   jd1          dist         j 
                       temp1  temp2 
                      ) 
  (setq oldcmdecho (getvar "cmdecho")) 
  (setvar "cmdecho" 0) 
 
  (setq        i        0 
        n        (length ao_list) 
        n_plist        (length plist) 
  ) 
  ;;求得凹点和与此凹点相连的两点ddxh-1的序号 
  (setq        ddxh   (nth i ao_list) 
        ddxh-1 (- ddxh 1) 
  ) 
  (cond        ((= ddxh-1 -1) 
         (setq ddxh-1 (- n_plist 1)) 
        ) 
        ((= ddxh-1 n_plist) 
         (setq ddxh-1 0) 
        ) 
  ) 
  ;;求得三点的坐标,及PT---PT-1(L1)向量的方位角 
  (setq        pt   (nth ddxh plist) 
        pt-1 (nth ddxh-1 plist) 
        ang1 (angle pt-1 pt) 
  ) 
  ;;构造以ang1方位的矢量 
  (setq        gd2 (getbox ename)                ;取得多边形的矩形外框 
        gd2 (+ 100 (distance (nth 0 gd2) (nth 1 gd2))) 
        gd2 (cons 10 (polar pt ang1 gd2)) 
        gd1 (cons 11 pt) 
  ) 
  (entmake (list 
             '(0 
               . 
               "line" 
              ) 
             '(8 . "0") 
             gd2 
             gd1 
           ) 
  ) 
  (setq l1 (entlast))                        ;取得l1图元名 
  ;;求得l1与多边形的交点坐标例表的表 
  (setq jd1 (GetInterPointlist ename l1)) 
  (entdel l1) 
  ;;剔除凹点本身 
  (setq        p     (length jd1) 
        j     0 
        temp2 nil 
  ) 
  (repeat p 
    (setq temp1 (nth j jd1)) 
    (if        (not (equal pt temp1 0.00001)) 
      (setq temp2 (append temp2 (list temp1))) 
    ) 
    (setq j (1+ j)) 
  ) 
  (setq jd1 temp2) 
  ;;交点的个 
  (setq        n    (length jd1) 
        i    0 
        dist "(min " 
  ) 
  ;;计算各交点与凹点的距离，最近点(本身除外)与凹点的连线的线段必在多边形内 
  (repeat n 
    (setq gd1 (distance pt (nth i jd1))) 
    (setq dist (strcat dist (rtos gd1 2) " ")) 
    (setq i (1+ i)) 
  ) 
  (setq        dist (eval (read (strcat dist ")"))) 
        dist (polar pt ang1 (/ dist 2)) 
  ) 
) 
(

;;(defun c:test ()
;;(in_point (car (entsel)))
;;)
;;功能：返回闭合曲线内的一点
;;By Longxin 明经通道 2006.03
;;参数：闭合曲线图元名(注，只适合曲线，包括拟合后的PLINE)
;;返回：(x y z)
(defun in_point_spline (ename / pd pt obj parm startparm endparm yspt1 ang1 ang2 i
n p j x y temp2 dist l1 gd2
gd1 jd1
)
(setq obj (vlax-ename->vla-object ename)
startparm (vlax-curve-getStartParam obj) ;取得曲线起点的参数
endparm (vlax-curve-getendparam obj);取得曲线终点的参数
parm (/ (+ startparm endparm) 2)
pt (vlax-curve-getPointAtParam obj parm) ;取得曲线中间点坐标
yspt1 (vlax-curve-getFirstDeriv obj parm)
;取得该点的第一衍生,即切线的衍生方向增量
yspt1 (list (+ (nth 0 pt) (nth 0 yspt1))
(+ (nth 1 pt) (nth 1 yspt1))
(nth 2 pt)
)
ang2 (angle pt yspt1) ;曲线起点在曲线上的切线方位角
)
;;如果曲线为逆时针，则可得到起点法线的方位角
(if (PlineCCW_obj ename)
(setq ang1 (+ ang2 (/ pi 2))) ;逆时针时+90度
(setq ang1 (- ang2 (/ pi 2))) ;顺时针时-90度
)
;;构造一条起点于曲线起点，边长大于曲线直径的line
(setq gd2 (getbox ename) ;取得多边形的矩形外框
gd2 (+ 100 (distance (nth 0 gd2) (nth 1 gd2)))
gd2 (cons 10 (polar pt ang1 gd2))
gd1 (cons 11 pt)
)
(entmake (list
'(0
.
"line"
)
'(8 . "0")
gd2
gd1
)
)
(setq l1 (entlast)) ;取得l1图元名
;;求得l1与多边形的交点坐标例表的表
(setq jd1 (GetInterPointlist ename l1))
(entdel l1)
;;计算各交点与曲线起点的距离，最近点(本身除外)与之连线的线段必在多边形内
(setq n (length jd1)
i 0
dist nil
)
(repeat n
(setq gd1 (distance pt (nth i jd1))
dist (append dist (list gd1))
i (1+ i)
)
)
(setq dist (vl-sort dist '<) ;给距离排序
dist (polar pt ang1 (/ (nth 1 dist) 2))
)
;;(command "point" dist)
)
(

;;(defun c:test () 
  ;;(in_point (car (entsel))) 
;;) 
 
;;功能：返回闭合曲线内的一点 
;;By Longxin 明经通道 2006.03 
;;参数：闭合曲线图元名(注，只适合曲线，包括拟合后的PLINE) 
;;返回：(x y z) 
 
(defun in_point_spline (ename /  pd   pt           obj        parm startparm endparm yspt1 ang1  ang2         i 
                 n     p     j           x         y     temp2 dist  l1         gd2 
                 gd1   jd1 
                ) 
   
  (setq        obj   (vlax-ename->vla-object ename) 
        startparm  (vlax-curve-getStartParam obj) ;取得曲线起点的参数 
        endparm    (vlax-curve-getendparam obj);取得曲线终点的参数 
        parm (/ (+ startparm endparm) 2) 
        pt    (vlax-curve-getPointAtParam obj parm) ;取得曲线中间点坐标 
        yspt1 (vlax-curve-getFirstDeriv obj parm) 
                                        ;取得该点的第一衍生,即切线的衍生方向增量 
        yspt1 (list (+ (nth 0 pt) (nth 0 yspt1)) 
                    (+ (nth 1 pt) (nth 1 yspt1)) 
                    (nth 2 pt) 
              ) 
        ang2  (angle pt yspt1)                ;曲线起点在曲线上的切线方位角 
  ) 
   
  ;;如果曲线为逆时针，则可得到起点法线的方位角 
  (if (PlineCCW_obj ename) 
    (setq ang1 (+ ang2 (/ pi 2)))        ;逆时针时+90度 
    (setq ang1 (- ang2 (/ pi 2)))        ;顺时针时-90度 
  ) 
  ;;构造一条起点于曲线起点，边长大于曲线直径的line   
  (setq        gd2 (getbox ename)                ;取得多边形的矩形外框 
        gd2 (+ 100 (distance (nth 0 gd2) (nth 1 gd2))) 
        gd2 (cons 10 (polar pt ang1 gd2)) 
        gd1 (cons 11 pt) 
  ) 
  (entmake (list 
             '(0 
               . 
               "line" 
              ) 
             '(8 . "0") 
             gd2 
             gd1 
           ) 
  ) 
  (setq l1 (entlast))                        ;取得l1图元名 
  ;;求得l1与多边形的交点坐标例表的表 
  (setq jd1 (GetInterPointlist ename l1)) 
  (entdel l1) 
   
  ;;计算各交点与曲线起点的距离，最近点(本身除外)与之连线的线段必在多边形内 
  (setq        n    (length jd1) 
        i    0 
        dist nil 
  ) 
  (repeat n 
    (setq gd1  (distance pt (nth i jd1)) 
          dist (append dist (list gd1)) 
          i    (1+ i) 
    ) 
  ) 
  (setq        dist (vl-sort dist '<)                ;给距离排序 
        dist (polar pt ang1 (/ (nth 1 dist) 2)) 
  ) 
   
  ;;(command "point" dist) 
) 
(

求平面点集的凸壳
(

;;(defun c:te (/ ss1 n plist)
;; (setq ss1 (ssget)
;; n (sslength ss1)
;; i 0)
;; (repeat n
;; (setq dxf (entget (ssname ss1 i))
;; pt (cdr (assoc 10 dxf))
;; plist (append plist (list pt))
;; i (1+ i)
;; ))
;; (dianji_tuke plist)
;; )
;;By Longxin 明经通道 2006.05
;;求得逆时针多边形凹点的顶点序号
;;参数：坐标例表
;;返回值:凸壳点表(逆时针)
(defun dianji_tuke (plist / pt ang_list n i lst)
(setq plist (order plist '(("(nth 1 " 1 "<"))) ;;对点表按Y坐标从小到大排序
pt (nth 0 plist);;取得Y坐标最小点坐标
　　　　plist (cdr plist);;去掉最小点后的坐标点列表
n (length plist)
i 0
)
;;生成PT点与坐标点列表中每个点的方位角的集合
(repeat n
(setq ang_list (append ang_list (list (angle pt (nth i plist))))
i (1+ i)
)
)
　;;对方位角集合按从小到大排序,输出的是序号，而不是数据
(setq ang_list (vl-sort-i ang_list '<))
;;按排序后的方位角的顺序生成由所有点组成的多边形点坐标列表
(setq i 0
lst (list pt)
)
(repeat n
(setq lst (append lst (list (nth (nth i ang_list) plist)))
i (1+ i)
)
)
　;;调用求多边形凸壳函数
(setq lst (dbx_tuke lst))
;;(makepline lst 1 0 nil)
)
(

;;(defun c:te (/ ss1 n plist) 
;;  (setq ss1 (ssget) 
;;        n (sslength ss1) 
;;        i 0) 
;;  (repeat n 
;;    (setq dxf (entget (ssname  ss1 i)) 
;;          pt (cdr (assoc 10 dxf)) 
;;          plist (append plist (list pt)) 
;;          i (1+ i) 
;;          )) 
;;  (dianji_tuke plist) 
;;  ) 
 
;;By Longxin 明经通道 2006.05 
;;求得逆时针多边形凹点的顶点序号 
;;参数：坐标例表 
;;返回值:凸壳点表(逆时针) 
(defun dianji_tuke (plist / pt ang_list n i lst) 
  (setq plist (order plist '(("(nth 1 " 1 "<")))  ;;对点表按Y坐标从小到大排序 
        pt (nth 0 plist);;取得Y坐标最小点坐标 
　　　　plist (cdr plist);;去掉最小点后的坐标点列表 
        n (length plist) 
        i 0 
        ) 
  ;;生成PT点与坐标点列表中每个点的方位角的集合 
 (repeat n 
   (setq ang_list (append ang_list (list (angle pt (nth i plist)))) 
         i (1+ i) 
   ) 
  ) 
　;;对方位角集合按从小到大排序,输出的是序号，而不是数据 
  (setq ang_list (vl-sort-i  ang_list '<)) 
  ;;按排序后的方位角的顺序生成由所有点组成的多边形点坐标列表 
  (setq i 0 
        lst (list pt) 
        ) 
  (repeat n 
    (setq lst (append lst (list (nth (nth i ang_list) plist))) 
          i (1+ i) 
    ) 
    ) 
　;;调用求多边形凸壳函数 
  (setq lst (dbx_tuke lst)) 
  ;;(makepline lst 1 0 nil) 
) 
(

tc405003 · 发表于 2006-10-7 07:52:21

楼主的程序下载试用了，很不错，不过是否可以精简代码

fsxm · 发表于 2006-10-7 09:59:52

程序可以不用写这么长的啦~呵呵~了解一下不同的算法也行`

oyxx_1023 · 发表于 2006-12-16 12:08:35

太复杂了。求面内一点论坛内有更好的办法。

Gu_xl · 发表于 2010-3-24 19:32:59

函数 dbx_tuke_1 没贴完整啊！

zxq0220 · 发表于 2013-3-30 10:01:52

偶还是新手:L

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

[讨论]：大家多讨论一下有关计算几何的算法，写出一些函数来，我先来两个：求凸集、凹

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

相关帖子