点集的最小包围圆

csharp

aimisiyou 发表于 2014-12-25 12:30
看来巨人的肩膀被你踩坏了，呵呵开个玩笑不介意吧。按你的说法，我认为你没有完全领悟透高飞的算法。该算法 ...

恭喜你啊，比我理解透彻，有空了写成Net代码，前面按高飞版主lisp高效凸包算法改成了Net代码

aimisiyou

csharp 发表于 2014-12-25 17:47
恭喜你啊，比我理解透彻，有空了写成Net代码，前面按高飞版主lisp高效凸包算法改成了Net代码

经典的程序都值得细细品味。对于一般情况，高飞算法迭代很少次数就能得到最小覆盖圆，所以执行速度很快。初步想了下特殊情况，比如点集分散在最小覆盖圆左右，估计迭代次数就多些，当然这特殊情况很少出现。

aimisiyou

写完前面的平面点集的最小包围圆算法，总感觉还能做点什么，加上论友提到凸包算法，然后网上搜了部分相关凸包算法及高版的礼品包扎算法，突想能不能在原算法上实现呢？带着疑问入梦，总睡不踏实，半夜醒来突然有点思路，简要写下算法，1求最小包围圆上的三点（直径特例两点）。2以三点构成三角形，删除三角形内部的点 （特例情况下选个到直径端点张角最大的点构成三角形）。3求剩余点中每边的最大张角及该点，若张角大于90度将每边对应的张角点加入进来，更新凸包，并删除凸包内的点。4重复步骤3。   5每边都没有对应的张角点时结束迭代过程。      

aimisiyou

不对，有问题，再好好想想。

aimisiyou

今天论友指出了我的算法中第一点P1在特殊情况下不在最小包围圆上（http://bbs.emath.ac.cn/forum.php ... amp;page=2#pid56898），即最终的三角形为钝角三角形时运算不正确。

aimisiyou

(defun gcen (plst)
  (setq nn (length plst))
  (setq p_g (list (/ (apply '+ (mapcar '(lambda (x)  (car x)) plst )) nn) (/ (apply '+ (mapcar '(lambda (x)  (cadr x)) plst )) nn)))
)
(defun p_dmax (p plst)
   (setq lst (vl-sort plst '(lambda(a b) (> (distance p a) (distance p b))) ))
)
(defun fmax (p_1 p_j p)
   (setq d1 (distance p_1 p_j) d2 (distance p_1 p) d3 (distance p_j p))
   (setq dn (/ (* d2 d2 d1) (+ (* d1 d1) (* d2 d2) (* d3 d3 -1))  ))
)
(defun pfmax (p_1 p_j plst)
   (setq lst (vl-sort plst '(lambda(a b) (> (fmax p_1 p_j a) (fmax p_1 p_j b))) ))
)
(defun cc (p_1 p_2 p)
   (setq d1 (distance p_1 p) d2 (distance p_2 p) d3 (distance p_1 p_2))
   (setq cosa (/ (+ (* d1 d1) (* d2 d2) (* d3 d3 -1)) (* d1 d2 2) ))
)
(defun tmax (p_1 p_2 plst)
   (setq lst (vl-sort plst '(lambda(a b) (> (cc p_1 p_2 a) (cc p_1 p_2 b) )) ))
)
(defun fp ()
    (setq sn (ssget ":N" '((0 . "point"))))
    (setq i 0 n (sslength sn) plst nil)
    (while (< i n)
        (setq plst (cons (cdr (assoc 10 (entget (ssname sn i)))) plst))
        (setq i (+ i 1))
    )
    plst
)
(defun c:tt()
   (setq plst (fp))
   (setq p_j (gcen plst))
   (setq p_1 (car (p_dmax p_j plst)))
   (setq p_2 (car (pfmax p_1 p_j (vl-remove p_1 plst))))
   (setq p_3 (car (tmax p_1 p_2 (vl-remove p_2 (vl-remove p_1 plst)))))
   (if (< (cc p_1 p_2 p_3) 0)
       (progn
         (command "circle" "2p" p_1 p_2 "")
         (command "pline" p_1 p_2 "")
        )
      (if (> (cc p_1 p_3 p_2) 0)
         (progn
            (command "circle" "3p" p_1 p_2 p_3 "")
            (command "pline" p_1 p_2 p_3 p_1 "")
          )
         (progn
            (setq p_2 (car (tmax p_1 p_3 (vl-remove p_1 (vl-remove p_3 plst)))))
            (command "circle" "3p" p_1 p_2 p_3 "")
            (command "pline" p_1 p_2 p_3 p_1 "")
          )
       )
    )
)

aimisiyou

http://blog.sina.com.cn/s/blog_6296cebc0100flj0.html

newer

aimisiyou 发表于 2016-11-4 00:23

用LISP写出来吧。

aimisiyou

newer 发表于 2016-11-4 00:41

似懂非懂，不好理解。只是我也感觉复杂度为O(n)。