社区 › AutoLISP/Visual LISP 编程技术 › graham-scan算法求点集凸包函数

落魄山人 发表于 2016-5-29 22:04:36

graham-scan算法求点集凸包函数

本帖最后由 落魄山人 于 2016-5-31 11:00 编辑

根据graham-scan算法编写的凸包函数，欢迎测试及提出bug。。。
其中用到高飞鸟的向量相关函数／飞诗的排序函数（黄总修改版）／多段线生成函数是某位我不知名的前辈的，再此感谢。。
更新：根据user2128的反馈，进行修改。。。
更新2：取消大量的自定义函数，只保留判断左转函数，同时优化程序代码，使其更清晰可读，该算法的时间复杂度为O（nlogn）;;;name:graham-scan
;;;desc:graham-scan算法计算点集凸包
;;;arg:ptlst:点表
;;;return:凸包点表
;;;example:(graham-scan '(pt1 pt2 pt3 ...))
(defun graham-scan (ptlst / d i p0)
(setq ptlst
(vl-sort
    ptlst
    '(lambda (p1 p2)
       (cond
((< (cadr p1) (cadr p2)))
((equal (cadr p1) (cadr p2) 1e-8)
   (< (car p1) (car p2))
)
       )
   )
)
)   ;点集坐标排序
(setq p0 (car ptlst))   ;根据坐标排序结果选取Y值最小，同时X最小的点作为凸包的第一个点
(setq ptlst
(vl-sort
    (cdr ptlst)
    (function
      (lambda (p1 p2 / m n)
      (cond
   ((< (setq m (angle p1 p0)) (setq n (angle p2 p0))))
   ((equal m n 1e-8)
    (< (distance p1 p0) (distance p2 p0))
   )
      )
      )
    )
)
)   ;极角排序
   ;写凸包算法
(setq d (list (cadr ptlst) (car ptlst) p0)) ;构建初始凸包点集
(foreach curpt (cddr ptlst);遍历剩余点
    (setq d (cons curpt d));当前点入栈   
    (while (and (caddr d) (isLeft (caddr d) (cadr d) curpt))
      (setq d (cons curpt (cddr d))) ;判断这时候的凸包前三点是否左转，如果非左转，将第二点删除
    )
)
)
;;;name:isLeft
;;;desc:判断点3-点2 与点2-点1 是否左转
;;;arg:pt1:点1
;;;arg:pt2:点2
;;;arg:pt3:点3
;;;return:nil为左转，t为右转或共线
;;;example:(isLeft '(0 1) '(3 2) '(4 3))
(defun isLeft (pt1 pt2 pt3)
(< (- (* (- (car pt2) (car pt1)) (- (cadr pt3) (cadr pt1)))
(* (- (cadr pt2) (cadr pt1)) (- (car pt3) (car pt1)))
   )
   1e-8
)
)
;;;测试函数
(defun c:tt (/ ss i lst)
(if (setq ss (ssget '((0 . "POINT"))))
    (progn
      (repeat (setq i (sslength ss))
(setq
   lst
    (cons (cdr (assoc 10 (entget (ssname ss (setq i (1- i))))))
   lst
    )
)
      )
      (setq lst (graham-scan lst))
      (entmakex
(append
   (list
   '(000 . "LWPOLYLINE")
   '(100 . "AcDbEntity")
   '(100 . "AcDbPolyline")
   (cons 90 (length lst))
   '(070 . 1)
   )
   (mapcar '(lambda (x) (cons 10 x)) lst)
)
      )
    )
)

USER2128 发表于 2016-5-30 08:28:27

点取一个矩形的4个角点，运行正确，点取一个矩形的每边端点和中点时，不正确

shh1980 发表于 2016-5-30 09:35:27

支持一下楼主，留个脚印先！

自贡黄明儒 发表于 2016-5-30 22:01:51

graham-scan 已经包括排序，只不过是按角度排序的。

落魄山人 发表于 2016-5-30 22:31:04

自贡黄明儒 发表于 2016-5-30 22:01 static/image/common/back.gif
graham-scan 已经包括排序，只不过是按角度排序的。

是的，不过第一次按坐标排序是为了找到一个起点，找到这个起点后，其余点按跟起点的极角排序

cchessbd 发表于 2024-6-5 12:04:24

经过我的测试，您这个速度是比较快，但是有点小bug，函数有时候会返回nil导致无法画线。
正在想法修复中。。。

nzl1116 发表于 2024-6-6 20:28:21

本帖最后由 nzl1116 于 2024-6-6 20:30 编辑

cchessbd 发表于 2024-6-5 12:04
经过我的测试，您这个速度是比较快，但是有点小bug，函数有时候会返回nil导致无法画线。
正在想法修复中。 ...

如果只选三个点，就画不出来了，就是在(foreach curpt (cddr ptlst) ...)结束后多写一个d就能解决了。
vl-sort排序也有问题，应该先equal。

查看完整版本: graham-scan算法求点集凸包函数