点集的最小包围圆

aimisiyou

;;;求点集包容矩形对角线交点坐标p_j
(defun kcen (plst)
  (setq xlst (vl-sort (mapcar '(lambda (x)  (car x)  ) plst ) '<))
  (setq xmin (car xlst))
  (setq xmax (last xlst))
  (setq ylst (vl-sort (mapcar '(lambda (x)  (cadr x)  ) plst ) '<))
  (setq ymin (car ylst))
  (setq ymax (last ylst))
  (setq p_j (list (/ (+ xmin xmax) 2.0) (/ (+ ymin ymax) 2.0)))
  p_j
)
;;;求点集中各元素到p_j的距离，并根据距离由大到小的规则对点集排序（第一点p_1,就算最远点有多个也不影响程序正确性）
(defun p_dmax (p plst)
   (setq lst (vl-sort plst '(lambda(a b) (> (distance p a) (distance p b))) ))
   lst
)
;;;求第二点p_2
(defun fmax (p_1 p_j p)
(setq d1 (distance p_1 p_j))
(setq d2 (distance p_1 p))
(setq d3 (distance p_j p))
(setq dn (/ (* d2 d2 d1) (+ (* d1 d1) (* d2 d2) (* d3 d3 -1))  ))
dn
)
(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))) ))
   lst
)
;;;求第三点
(defun cc (p_1 p_2 p)
(setq d1 (distance p_1 p))
(setq d2 (distance p_2 p))
(setq d3 (distance p_1 p_2))
(setq cosa (/ (+ (* d1 d1) (* d2 d2) (* d3 d3 -1)) (* d1 d2 2) ))
cosa
)
(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) )) ))
    lst
)
;;;取点函数
(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:fmin()
(setq plst (fp))
(setq p_j (kcen 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 "line" p_1 p_2 "")
        )
      (if (> (cc p_1 p_3 p_2) 0)
         (progn
            (command "circle" "3p" p_1 p_2 p_3 "")
            (command "line" 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 "line" p_1 p_2 p_3 p_1 "")
          )
      )
  )
)

newer

能讲讲算法吗？

aimisiyou

newer 发表于 2014-12-23 18:15
能讲讲算法吗？

1、先求第一点p1，p1为到点集包围矩形对角线交点最远的点，此时包围圆过p1且以对角线交点为圆心；
2、缩小包围圆，圆心向p1移动，圆半径缩小，直至第二点p2在圆上;
3、以P1、P2为弦，剩余点中对p1、p2构成的张角最小的点为p3（若最小张角为钝角，则p1p2为直径）；
4、检验角p1p2p3是否为锐角，若是则最小包围圆过p1p2p3；否则以p1p3为弦，返回步骤3；

newer

aimisiyou 发表于 2014-12-23 20:01
1、先求第一点p1，p1为到点集包围矩形对角线交点最远的点，此时包围圆过p1且以对角线交点为圆心；
2、缩 ...

算法的时间复杂度是多少? N2 ?

aimisiyou

newer 发表于 2014-12-23 20:25
算法的时间复杂度是多少? N2 ?

理论上是O（N）。

newer

aimisiyou 发表于 2014-12-23 20:31
理论上是O（N）。

先求凸包，然后从凸包在求最小包围圆是否能更快？

aimisiyou

快与否我不知道，但凸包算法相对要复杂些。

csharp

凸包、最小包围圆，高飞版主都写了，我认为是alisp的最佳算法了，看懂就够了，没必要自己再费时间

aimisiyou

csharp 发表于 2014-12-23 21:48
凸包、最小包围圆，高飞版主都写了，我认为是alisp的最佳算法了，看懂就够了，没必要自己再费时间

呵呵，你可能觉得是浪费时间，但我认为照部就搬就没提高自己的思维水平，哪怕一些简单问题，自己换个角度思考下还是有点意义，个人看法。

csharp

aimisiyou 发表于 2014-12-23 21:54
呵呵，你可能觉得是浪费时间，但我认为照部就搬就没提高自己的思维水平，哪怕一些简单问题，自己换个角度 ...

看多了就能分出算法优劣，能区分自然就有提高，做事站在巨人肩上才能眼界更广、提高更快！

m786372966

不错，挺好的，谢谢！

aimisiyou

csharp 发表于 2014-12-23 21:59
看多了就能分出算法优劣，能区分自然就有提高，做事站在巨人肩上才能眼界更广、提高更快！

我只是跟着兴趣走，纯属自娱自乐而已，没想那么多。

csharp

aimisiyou 发表于 2014-12-24 12:10
我只是跟着兴趣走，纯属自娱自乐而已，没想那么多。

高飞版主的算法，前三点构造最小圆，依次插入第四点，如果在圆在求该四点的最小圆，点集小于3点单独判断，每个点只遍历一次

aimisiyou

看来巨人的肩膀被你踩坏了，呵呵开个玩笑不介意吧。按你的说法，我认为你没有完全领悟透高飞的算法。该算法的精髓是通过三点迭代法（直径特殊情况不谈）不断扩大圆，最终满足圆覆盖所有点。

aimisiyou

csharp 发表于 2014-12-24 22:11
高飞版主的算法，前三点构造最小圆，依次插入第四点，如果在圆在求该四点的最小圆，点集小于3点单独判断 ...

你所说的“依次插入第四点”有点不准确，第四点应该是到前三点确定的最小覆盖圆圆心最远的点，最后“每个点只遍历一遍”就不正确了，迭代的条件是到已确定的圆心最远的点是否在圆内，那么迭代几次，每个点就遍历几次。