;;;************************************************************************
;;;一個(gè)求點(diǎn)集合的凸包的lisp程序--------------------------------------------
;;;------采用的算法為禮品包扎法--------------------------------------------
;;;方法為最右端的點(diǎn)開始處理，將該點(diǎn)作為凸包邊界的第一個(gè)點(diǎn)P1，從最初的垂直線
;;;方向繞P1順時(shí)針旋轉(zhuǎn)，直到碰到另一個(gè)P2這就是凸包邊界的第二個(gè)點(diǎn)P2，依此類推
;;;p2求得p3......直到又重新回到p1，已經(jīng)考慮了各種退化情況和浮點(diǎn)運(yùn)算，其算法
;;;時(shí)間不超過O(n.h),其中h是凸包的復(fù)雜度，時(shí)間還是很快的。大家不妨驗(yàn)證。    
;;;參考文獻(xiàn)<<計(jì)算幾何-算法及其應(yīng)用>>(第二版),以及參考了其他網(wǎng)站的一些源代碼
;;;------------------------------------------------------------------------
;;;其中程序主段是核心算法，其他的附加程序?yàn)槿〉命c(diǎn)集，畫凸包邊界線，測(cè)試大量
;;;點(diǎn)集函數(shù)處理所花費(fèi)的時(shí)間。----------------------------------------------
;;;用法: 加載lisp運(yùn)行test選取點(diǎn)，直線段，或多義線(全是直線段組成)即可。----
;;;************************************************************************
(defun C:test (/ sel t0 ptlist pp 2Pi)
  (setq 2Pi (* 2 pi))
  ;;(setq	sel (ssget (list '(0 . "POINT"))))                  ;選擇點(diǎn)集
  (setq sel (ssget))
  (if (setq ptlist (getpt sel))                             ;構(gòu)造點(diǎn)集
    (progn
      (setq t1 (getvar "CDATE"))                            ;計(jì)時(shí)開始
      ;;(setq t0 (getvar "TDUSRTIMER"))                       ;開始計(jì)時(shí)
      (setq p1 (hull ptlist))                               ;求凸包
      (setq t2 (getvar "CDATE"))                            ;計(jì)時(shí)結(jié)束
      (setq pp (Max-distance p1))
      (setq t3 (getvar "CDATE")) 
      (princ "\n求點(diǎn)集的凸包用時(shí):")
      (princ (* (- t2 t1) 1e6))
      (princ "秒")
      (princ "\n凸包共有")
      (princ (length p1))
      (princ "個(gè)頂點(diǎn)")
      (princ "\n求凸包的直徑用時(shí):")
      (princ (* (- t3 t2) 1e6))
      (princ "秒")
      (princ "\n總用時(shí)=最大距離點(diǎn)對(duì)用時(shí):")
      (princ (* (- t3 t1) 1e6))
      (princ "秒")      
      ;;(princ (* (- (getvar "TDUSRTIMER") t0) 86400))        ;結(jié)束計(jì)時(shí)
    )
  )
  (if (null pp)
    (alert "點(diǎn)的有效數(shù)目太小，請(qǐng)重新輸入!")
    (entmake                                                ;畫凸包
      (append
       '( (0 . "LWPOLYLINE")
	  (100 . "AcDbEntity")
	  (100 . "AcDbPolyline")
	)
	(list (cons 90 (length pp)))                        ;頂點(diǎn)個(gè)數(shù)
	(mapcar '(lambda (x) (cons 10 x)) pp)               ;多段線頂點(diǎn)
	(list (cons 70 0))                                  ;閉合的
	(list (cons 62 1))                                  ;紅色的
      )
    )
  )
  (princ)
)
;;;==========================
;;;程序主段，可以單獨(dú)成為函數(shù)
;;;==========================

;;;右半部的凸包
(defun hull1 (pts MaxPt MinPt / nextPt hullPt)
  (if (< (length pts) 3)
    pts
    (progn
      (setq nextPt (Max-angle1 pts MaxPt))                  ;從最上面的點(diǎn)開始
      (setq hullPt (cons nextPt (cons MaxPt hullPt)))       ;順時(shí)針求得第一點(diǎn)
      (while (not (equal nextPt MinPt 1e-8))                ;到最下面的點(diǎn)為止
        (setq nextPt (Max-angle pts nextPt))                ;循環(huán)求凸包每一點(diǎn)
	(setq hullPt (cons nextPt hullPt))                  ;把每點(diǎn)加入凸包集
      )
    )
  )
)
;;;左半部的凸包
(defun hull (ptlist / revPts 2ndPts maxYp1 minYp1 maxYp2 minYp2
	              ptlst1 ptlst2 +ptlst -ptlst hullp1 hullp2)
  (setq revPts (mapcar 'reverse ptlist))                    ;點(diǎn)表的X和Y交換
  (setq 2ndPts (mapcar 'cadr ptlist))                       ;點(diǎn)表的Y值的表
  (setq maxYp1 (reverse (assoc (apply 'max 2ndPts) revPts)));最上面的點(diǎn)
  (setq minYp1 (reverse (assoc (apply 'min 2ndPts) revPts)));最下面的點(diǎn)
  (setq maxYp2 (list (- (car maxYp1)) (cadr maxYp1)))       ;鏡像后最上面的點(diǎn)
  (setq minYp2 (list (- (car minYp1)) (cadr minYp1)))       ;鏡像后最下面的點(diǎn)
  (foreach n ptlist                                         ;把點(diǎn)表分成兩部分
    (if (> (det minYp1 n maxYp1) 0)                         ;如果左轉(zhuǎn)
      (setq ptlst1 (cons n ptlst1))                         ;加入右半部分
      (setq ptlst2 (cons n ptlst2))                         ;否則左半部分
    )
  )
  (setq +ptlst (cons minYp1 (cons maxYp1 ptlst1)))          ;右半部分
  (setq -ptlst (Mirror-list-X ptlst2))                      ;左半部分以Y軸鏡像
  (setq hullp1 (hull1 +ptlst maxYp1 minYp1))                ;右半部分的凸包
  (setq hullp2 (hull1 -ptlst maxYp2 minYp2))                ;左半部分鏡像的凸包
  (setq hullp2 (cdr (reverse (cdr hullp2))))
  (setq hullp2 (Mirror-list-X hullp2))                      ;左半部分的凸包
  (append hullp1 hullp2)                                    ;把凸包左右相加
)
;;;鏡像左半部分
(defun Mirror-list-X (ptlist)
  (mapcar (function (lambda (x)(list (- (car x))(cadr x)))) ptlist)
)
;;;求點(diǎn)集中夾角的最大值的點(diǎn)
(defun Max-angle (ptlist pt / An)
  (setq An (mapcar (function (lambda (x) (angle pt x))) ptlist))
  (nth (- (length An) (length (member (apply 'max An) An))) ptlist)
)
(defun Max-angle1 (ptlist pt / An)
  (setq An
    (mapcar
      (function
        (lambda (x)
	  (if
	    (and
	      (equal (cadr x) (cadr pt) 1e-8)
	      (> (car x) (car pt))
	    )
	    (+ 2Pi (- (car x) (car pt)))
	    (angle pt x)
	  )	   
	)
      )
      ptlist
    )
  )
  (nth (- (length An) (length (member (apply 'max An) An))) ptlist)
)
;;定義三點(diǎn)的行列式,即三點(diǎn)之倍面積
(defun det (p1 p2 p3 / dx1 dy1 dx2 dy2)
  (setq	dx1 (- (car  p2) (car  p1))
	dy1 (- (cadr p2) (cadr p1))
	dx2 (- (car  p3) (car  p1))
	dy2 (- (cadr p3) (cadr p1))
  )
  (- (* dx1 dy2) (* dx2 dy1))
)
(defun Max-distance (ptlist / maxD halfPi HullP1 l HullP2 midPts
		              i j Pi+1 Qi+1 Ai+1 D-i PairPt)
  (setq MaxD nil)
  (setq 2Pi  (* 2 pi))
  (setq halfPi (/ Pi 2))
  (setq HullP1 (Hull ptlist))
  (setq l      (1- (length HullP1)))
  (setq HullP2 (append (cdr HullP1) (list (car HullP1))))
  (setq midPts (mapcar 'mid-pt HullP1 HullP2))
  (setq i 1)
  (foreach pt (reverse (cdr (reverse HullP1)))
    (setq j i)
    (setq Pi+1 (nth i HullP1))
    (setq Qi+1 (nth i midPts))
    (setq Ai+1 (ang Qi+1 pt Pi+1))
    (while (and (< Ai+1 halfPi) (< j l))
      (setq j (1+ j))
      (setq Ai+1 (ang (nth j midPts) Pt (nth j HullP1)))  
    )
    (setq D-i  (distance pt (nth j HullP1)))
    (setq MAXD (cons (list D-i (1- i) j) MAXD)) 	  
    (setq i (1+ i))  
  )
  (setq PairPt (assoc (apply 'Max (mapcar 'car MaxD)) MaxD))
  (list
    (nth (cadr  PairPt) HullP1)
    (nth (caddr PairPt) HullP1)
  )
)
(defun mid-pt (p1 p2)
  (list
    (* (+ (car  p1) (car  p2)) 0.5)
    (* (+ (cadr p1) (cadr p2)) 0.5)
  )
)
;;;============
;;;程序主段結(jié)束
;;;============

;;;依據(jù)曉東網(wǎng)站的代碼改寫而成的取點(diǎn)函數(shù)
(defun getpt1 (ss / a b c d i p)
  (setq	i 0)
  (if ss
    (repeat (sslength ss)
      (setq a (ssname ss i))
      (setq b (entget a))
      (setq c (cdr (assoc 10 b)))
      (setq c (list (car c) (cadr c)))
      (setq p (cons c p))
      (setq i (1+ i))
    )
  )
  p
)
;;定義三點(diǎn)的夾角函數(shù)
(defun ang (p1 p2 p3 / x)
  (setq x (abs (- (angle p1 p3) (angle p1 p2))))
  (if (< x Pi) x (- 2Pi x)) 
)
(defun C:tt (/ p1 p2 p3)
  (initget 1)
  (setq p1 (getpoint "\n輸入第一點(diǎn):"))
  (setq p2 (getpoint "\n輸入第二點(diǎn):"))
  (setq p3 (getpoint "\n輸入第三點(diǎn):"))
  (ang p1 p2 p3)
)  
;;;取點(diǎn)函數(shù)2
(defun getpt (ss / i listpp a b c d)
  (setq	i 0)
  (if ss
    (repeat (sslength ss)
      (setq a (ssname ss i))
      (setq b (entget a))
      (setq ename (cdr (assoc 0 b)))
      (cond
	( (= ename "LWPOLYLINE")
	  (setq c (get-LWpolyline-vertexs b))
	  (setq listpp (append c listpp))
	)
	( (= ename "LINE")
	  (setq c (cdr (assoc 10 b)))
	  (setq d (cdr (assoc 11 b)))
	  (setq c (list (car c) (cadr c)))
	  (setq d (list (car d) (cadr d)))
	  (setq listpp (cons c listpp))
	  (setq listpp (cons d listpp))
	)
	( (= ename "POINT")
	  (setq c (cdr (assoc 10 b)))
	  (setq c (list (car c) (cadr c)))
	  (setq listpp (cons c listpp))
	)
      )
      (setq i (1+ i))
    )
  )
  listpp
)
;;取得多邊形頂點(diǎn)
(defun get-LWpolyline-vertexs (entlst / n lst)
  (foreach n entlst
    (if (= (car n) 10)
      (setq lst (cons (cdr n) lst))
    )
  )
  lst
)