求简单多边形的外接无内折角的多边形函数（不要太复杂的太长的句子，简单外凸包）

zzl9105

如题，已知多边形，且已知它的顶点集，求简单多边形的外接无内折角的多边形函数，就是简单外凸包多边形顶点集，谢谢

Gu_xl

[【高飞鸟】] 【越飞越高讲堂11】一个高效率的凸包算法！

zzl9105

Gu_xl 发表于 2018-5-18 16:26
[【高飞鸟】] 【越飞越高讲堂11】一个高效率的凸包算法！

G版，我有一个简单的想法，目标对象是闭合多段线，就是判断它自身任意一个角点是不是在其它角点所形成的多段线内来实现这个功能，如果在内，则去掉这个点，如果在外，则保留，这样走一圈下来，没有去除的点所形成的点集就是凸外接多边形的角点了。
有没有一个简单的功能，能实现判断一个点是否在多段线内

pzweng

zzl9105 发表于 2018-5-18 16:50
G版，我有一个简单的想法，目标对象是闭合多段线，就是判断它自身任意一个角点是不是在其它角点所形成的 ...

;;功能：判断点在封闭曲线内外，自交曲线不适用 By Gu_xl 2012.07.31
;;返回: 点在封闭曲线上或曲线内，返回T，否则返回nil
;;测试: (gxl-PtInCurveP  (car(entsel "\n选择曲线:")) (getpoint))
(defun gxl-PtInCurveP  (POLY PT           /           CP           LW
                                   MINP           MAXP           MINX           MINY
                                   MAXX           MAXY           X           Y
                                   LST           CLOCKWISEP           ENDPARAM
                                   CURVELENGTH           PARAM   DIST
                                   D1           D2           DEV           )
  (cond
    ((equal pt
            (setq cp (vlax-curve-getclosestpointto poly pt))
            1e-8)) ;_ 点在曲线上 T
    ((progn
       (vla-GetBoundingBox
         (setq lw (vlax-ename->vla-object POLY))
         'MinP
         'MaxP)
       (setq MinP (vlax-safearray->list MinP))
       (setq MaxP (vlax-safearray->list MaxP))
       (setq minx (car MinP)
             miny (cadr MinP)
             maxx (car MaxP)
             maxy (cadr MaxP)
             x          (car pt)
             y          (cadr pt)
             )
       (or (< x minx)
           (> x maxx)
           (< y miny)
           (> y maxy)
           )
       )
     NIL ;_ 点在曲线最小包围盒外 nil
     )
    (t
     (setq
       lst (mapcar
             (function
               (lambda (x)
                 (vlax-curve-getParamAtPoint
                   lw
                   (vlax-curve-getClosestPointTo lw x)
                   )
                 )
               )
             (list minp
                   (list minx maxy)
                   MaxP
                   (list maxx miny)
                   )
             )
       ) ;_ 最小包围盒点在曲线上的投影点的参数表
     (setq ClockwiseP
            (if        (or
                  (<= (car lst) (cadr lst) (caddr lst) (cadddr lst))
                  (<= (cadr lst) (caddr lst) (cadddr lst) (car lst))
                  (<= (caddr lst) (cadddr lst) (car lst) (cadr lst))
                  (<= (cadddr lst) (car lst) (cadr lst) (caddr lst))
                  ) ;_  or
              t
              ) ;_  if
           ) ;_ 判断曲线是否为顺时针，顺时针 = T
     (setq endparam    (vlax-curve-getendparam poly)
           curvelength (vlax-curve-getDistAtParam poly endparam) ;_ 曲线长度
           )
     (setq param (vlax-curve-getparamatpoint poly cp)
           dist         (vlax-curve-getDistAtParam poly param)
           )
     (if (equal param (fix param) 1e-8)
       (progn
         (setq d1 (- dist 1e-8))
         (if (minusp d1)
           (setq d1 (+ curvelength d1))
           )
         (setq d2 (+ dist 1e-8))
         (if (> d2 curvelength)
           (setq d2 (- d2 curvelength)))
         (if (<        (distance pt (vlax-curve-getpointatdist poly d1))
                (distance pt (vlax-curve-getpointatdist poly d2))
                )
           (setq param (vlax-curve-getparamatdist poly d1))
           (setq param (vlax-curve-getparamatdist poly d2))
           )
         )
       )
     (setq dev (vlax-curve-getFirstDeriv poly param)
           cp  (vlax-curve-getpointatparam poly param)
           )
     (=        ClockwiseP
        (
         (lambda (p1 p2 p3)
           (<
             (* (- (car p2) (car p1)) (- (cadr p3) (cadr p1)))
             (* (- (cadr p2) (cadr p1)) (- (car p3) (car p1)))
             )
           )
          pt
          cp
          (mapcar '+ cp dev)
          )
        )
       )
    )
  )

zzl9105

就用这个多段线自身的点集，只是需要去掉它任意一个角点如果是在其余角点所形成的多段线内的点，剩下的点就是所求的凸外接多边形了

zzl9105

Gu_xl 发表于 2018-5-18 16:26
[【高飞鸟】] 【越飞越高讲堂11】一个高效率的凸包算法！

这个帖子里的外包功能太强大了，什么图形都能实现外包，又超长，我只需要一个封闭多边形的外包小程序，不需要那么复杂的，不知道有没有，谢谢G版！谢谢大家