关于多边形凸角凹角的判断

st788796 · 发表于 2013-10-2 13:35:00

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

对由直线边构成的多边形(pline)，判断是凸角还是凹角，可以利用点集面积算法来求解，
1 获取pline顶点表

(setq pts (xdrx_entity_getstretcpoint pl))

2 获取点集面积

(setq mod (apply 'xdrx_points_area pts))

3 判断 pline 方向如果顺时针的话把曲线转向, 同时 Reverse pts

(if (minusp mod)
(progn
(xdrx_curve_reverse pl))
(setq pts (reverse pts))
)
)

4 如图示，三个点围成一个三角形进行判断，面积为负的为凹角

(setq pts (append pts (list (car pts) (cadr pts))));_增加两个点判断起点处
(while (cddr pts)
(mapcar 'set '(a b c) pts)
(if (minusp (xdrx_points_area a b c))
(progn ..... );_凹角处理代码
(progn ......);_凸角处理代码，注意判断三点一线情况
)
(setq pts (cdr pts));_处理下一角
)

在角的处理上可以应用 xdrx_polyline 部分函数对 pline 灵活处理了

newer · 发表于 2013-10-2 13:37:05

能适合所有的情况吗？能不能找出一个反例出来？

st788796 · 发表于 2013-10-2 13:40:21

newer 发表于 2013-10-2 13:37
能适合所有的情况吗？能不能找出一个反例出来？

呵呵，我只想到了算法，反例没有想出来，逆时针凸包，面积为负的就凹进去，欢迎探讨:)

/db_自贡黄明儒_ · 发表于 2013-10-2 16:56:31

三角形内取一点，判断这—点是否在多边形内，，可否？

牢固 · 发表于 2013-10-2 20:47:20

st788796 发表于 2013-10-2 13:40
呵呵，我只想到了算法，反例没有想出来，逆时针凸包，面积为负的就凹进去，欢迎探讨

计算多边形的凸包，如多边形面积比凸包面积小，多边形自然是凹多边形了！

st788796 · 发表于 2013-10-2 22:20:01

牢固发表于 2013-10-2 20:47
计算多边形的凸包，如多边形面积比凸包面积小，多边形自然是凹多边形了！

本意不是算多边形面积，看到机械加工上好像有一个应用，突出来的角扩大一个弧，如果是凹角就做一个 fillet ,这个算法三这方面应用

牢固 · 发表于 2013-10-2 23:10:19

本帖最后由牢固于 2013-10-2 23:12 编辑

st788796 发表于 2013-10-2 22:20
本意不是算多边形面积，看到机械加工上好像有一个应用，突出来的角扩大一个弧，如果是凹角就做一个 fille ...

那就没那么复杂了！先计算多边形面积（带正负号）（判断顺逆时针），再逐个计算每个角点三角形面积（判断顺逆时针），若三角形面积符号和多边形面积符号一致（三角形和多边形同向），就是凸角，否则是凹角！

st788796 · 发表于 2013-10-3 01:34:42

牢固发表于 2013-10-2 23:10
那就没那么复杂了！先计算多边形面积（带正负号）（判断顺逆时针），再逐个计算每个角点三角形面积（判断 ...

是这样的，后面增加端点并设置bulge时，在不事先设好逆时针情况下要多写一些判断

ysq101 · 发表于 2013-10-3 23:05:39

我来分享网上下载的源码,,,好像也是根据三点面积来判断是凹角还是凸角的...可以参考一下

原作者忘了是谁了~~~

;--------------------------倒内角-------------------------------------------
(defun c:nn()
(setvar "cmdecho" 0)
(setq oldosmode (getvar "osmode"))
(setvar "osmode" 0)
(command "UNDO" "be")
(setq dd 0.5)
(setq rr (getreal"\n请输入圆角半径:"))
(command "_fillet" "r" rr )
(setq ss1 (ssget (list (cons 0 "LWPOLYLINE"))))
(while(/= SS1 NIL)
(progn
(setq ii 0)
(repeat (sslength ss1)
(setq en1 (ssname ss1 ii))
(setq ii (+ ii 1))
(yp008chamfer en1)
)
(prompt "\n 完成请检查:")
(setq ss1 (ssget (list (cons 0 "LWPOLYLINE"))))
)
)
(setvar "osmode" oldosmode)
(command "UNDO" "e")
(princ)
)
(defun yp008chamfer(en1 / isclose i j ed1 pt1 pt2 pt3 lst1 lst2 )
(setq ed1 (entget en1))
(setq i 0)
(setq lst1 '() lst2 '())
(repeat (length ed1)
(if(= (car (nth i ed1)) 10)
(setq lst1 (append lst1 (list (cdr (nth i ed1)))))n
)
(if(= (car (nth i ed1)) 42)
(setq lst2 (append lst2 (list (cdr (nth i ed1)))))
)
(setq i (+ i 1))
)
(setq isclose 0)
(if(= (cdr (assoc 70 ed1)) 1)
(progn
(setq isclose 1)
(setq lst1 (append lst1 (list (nth 0 lst1))))
(setq lst2 (append lst2 (list 0)))
))
(if(equal (distance (nth 0 lst1) (nth (- (length lst1) 1) lst1)) 0.000000001)
(setq isclose 1)
)
(setq i 1)
(repeat (- (length lst1) 2)
(progn
(setq pt1 (nth (- i 1) lst1) pt2 (nth i lst1) pt3 (nth (+ i 1) lst1))
(setq ang1 (nth (- i 1) lst2) ang2 (nth i lst2))
(if(and (equal ang1 0 0.000000001) (equal ang2 0 0.00000001))
(yp008c en1 pt1 pt2 pt3)
)
(setq i (+ i 1))
)
)
(if(= isclose 1)
(progn
(setq pt1 (nth (- (length lst1) 2) lst1) pt2 (nth 0 lst1) pt3 (nth 1 lst1))
(setq ang1 (nth (- (length lst1) 2) lst2) ang2 (nth 0 lst2))
(if(and (equal ang1 0 0.000000001) (equal ang2 0 0.00000001))
(yp008c en1 pt1 pt2 pt3)
)
) )
)
(defun yp008c(en1 pt1 pt2 pt3 / x1 x2 y1 y2 en4 en5)
(setq pt1 (trans pt1 0 1) pt2 (trans pt2 0 1) pt3 (trans pt3 0 1))
(if(and (> (distance pt1 pt2) (* dd 2)) (> (distance pt3 pt2) (* dd 2)))
(progn
(setq x1 (yp008x pt2 pt1 dd)
x2 (yp008x pt2 pt3 dd)
y1 (yp008y pt2 pt1 dd)
y2 (yp008y pt2 pt3 dd)
)
(command "_area" "o" en1)
(setq en4 (getvar "AREA"))
;(prompt (strcat "\n" (rtos x1 2 2) ";" (rtos y1 2 2)))
(command "_fillet" (list x2 y2) (list x1 y1) ) ;;en5)
;(prompt (strcat "\n" (rtos x2 2 2) ";" (rtos y2 2 2)))
(command "_area" "o" en1)
(setq en5 (getvar "AREA"))
(IF(> EN4 EN5)
(progn
(command "u")
(command "u")
(command "u")
) )
; (IF(> EN4 EN5) (COMMAND "UNDO" 2))
) )
)
(defun yp008x(pt2 pt1 d / x3 d1)
(setq d1 (distance pt2 pt1))
(if(equal (car pt1) (car pt2) 0.00000001)
(setq x3 (car pt1))
(setq x3 (+ (car pt2) (* (- (car pt1) (car pt2)) 0.25)))
)
)
(defun yp008y(pt2 pt1 d / x3 d1)
(setq d1 (distance pt2 pt1))
(if(equal (cadr pt1) (cadr pt2) 0.00000001)
(setq x3 (cadr pt1))
(setq x3 (+ (cadr pt2) (* (- (cadr pt1) (cadr pt2)) 0.25)))
)
)
;----------------------倒外角-------------------------------------------------------
(defun c:n()
(setvar "cmdecho" 0)
(setq oldosmode (getvar "osmode"))
(command "UNDO" "be")
(setq dd 0.5)
(setq rr (getreal"\n请输入圆角半径:"))
(command "_fillet" "r" rr )
(setq ss1 (ssget (list (cons 0 "LWPOLYLINE"))))
(while(/= SS1 NIL)
(progn
(setq ii 0)
(repeat (sslength ss1)
(setq en1 (ssname ss1 ii))
(setq ii (+ ii 1))
(yp007chamfer en1)
)
(prompt "\n 完成请检查:")
(setq ss1 (ssget (list (cons 0 "LWPOLYLINE"))))
)
)
(setvar "osmode" oldosmode)
(command "UNDO" "e")
(princ)
)
(defun yp007chamfer(en1 / isclose i j ed1 pt1 pt2 pt3 lst1 lst2 )
(setq ed1 (entget en1))
(setq i 0)
(setq lst1 '() lst2 '())
(repeat (length ed1)
(if(= (car (nth i ed1)) 10)
(setq lst1 (append lst1 (list (cdr (nth i ed1)))))
)
(if(= (car (nth i ed1)) 42)
(setq lst2 (append lst2 (list (cdr (nth i ed1)))))
)
(setq i (+ i 1))
)
(setq isclose 0)
(if(= (cdr (assoc 70 ed1)) 1)
(progn
(setq isclose 1)
(setq lst1 (append lst1 (list (nth 0 lst1))))
(setq lst2 (append lst2 (list 0)))
))
(if(equal (distance (nth 0 lst1) (nth (- (length lst1) 1) lst1))
0.000000001)
(setq isclose 1)
)
(setq i 1)
(repeat (- (length lst1) 2)
(progn
(setq pt1 (nth (- i 1) lst1) pt2 (nth i lst1) pt3 (nth (+ i 1)
lst1))
(setq ang1 (nth (- i 1) lst2) ang2 (nth i lst2))
(if(and (equal ang1 0 0.000000001) (equal ang2 0 0.00000001))
(yp007c en1 pt1 pt2 pt3)
)
(setq i (+ i 1))
)
)
(if(= isclose 1)
(progn
(setq pt1 (nth (- (length lst1) 2) lst1) pt2 (nth 0 lst1) pt3
(nth 1 lst1))
(setq ang1 (nth (- (length lst1) 2) lst2) ang2 (nth 0 lst2))
(if(and (equal ang1 0 0.000000001) (equal ang2 0 0.00000001))
(yp007c en1 pt1 pt2 pt3)
)
) )
)
(defun yp007c(en1 pt1 pt2 pt3 / x1 x2 y1 y2 en4 en5)
(setq pt1 (trans pt1 0 1) pt2 (trans pt2 0 1) pt3 (trans pt3 0 1))
(if(and (> (distance pt1 pt2) (* dd 2)) (> (distance pt3 pt2) (* dd
2)))
(progn
(setq x1 (yp007x pt2 pt1 dd)
x2 (yp007x pt2 pt3 dd)
y1 (yp007y pt2 pt1 dd)
y2 (yp007y pt2 pt3 dd)
)
(command "_area" "o" en1)
(setq en4 (getvar "AREA"))
(command "_fillet" (list x2 y2) (list x1 y1) ) ;;en5)
(command "_area" "o" en1)
(setq en5 (getvar "AREA"))
(IF(< EN4 EN5) (COMMAND "UNDO" 2))
) )
)
(defun yp007x(pt2 pt1 d / x3 d1)
(setq d1 (distance pt2 pt1))
(if(equal (car pt1) (car pt2) 0.00000001)
(setq x3 (car pt1))
(setq x3 (+ (car pt2) (* (- (car pt1) (car pt2)) 0.5)))
)
)
(defun yp007y(pt2 pt1 d / x3 d1)
(setq d1 (distance pt2 pt1))
(if(equal (cadr pt1) (cadr pt2) 0.00000001)
(setq x3 (cadr pt1))
(setq x3 (+ (cadr pt2) (* (- (cadr pt1) (cadr pt2)) 0.5)))
)
)

;--------------------------倒内角------------------------------------------- 
(defun c:nn() 
  (setvar "cmdecho" 0) 
    (setq oldosmode (getvar "osmode")) 
  (setvar "osmode" 0) 
   (command "UNDO" "be") 
 
   
  (setq dd 0.5) 
   (setq rr (getreal"\n请输入圆角半径:")) 
  (command "_fillet" "r" rr ) 
  (setq ss1 (ssget (list (cons 0 "LWPOLYLINE")))) 
  (while(/= SS1 NIL) 
    (progn 
       (setq ii 0) 
       (repeat (sslength ss1) 
         (setq en1 (ssname ss1 ii)) 
         (setq ii (+ ii 1)) 
         (yp008chamfer en1) 
      ) 
       (prompt "\n 完成 请检查:") 
       (setq ss1 (ssget (list (cons 0 "LWPOLYLINE")))) 
    ) 
  ) 
  (setvar "osmode" oldosmode) 
  (command "UNDO" "e") 
  (princ) 
  ) 
 
 
(defun yp008chamfer(en1 / isclose i j ed1 pt1 pt2 pt3 lst1 lst2 ) 
  (setq ed1 (entget en1)) 
  (setq i 0) 
  (setq lst1 '()  lst2 '()) 
  (repeat (length ed1) 
    (if(= (car (nth i ed1)) 10) 
       (setq lst1 (append lst1 (list (cdr (nth i ed1)))))n 
    ) 
    (if(= (car (nth i ed1)) 42) 
       (setq lst2 (append lst2 (list (cdr (nth i ed1))))) 
    ) 
    (setq i (+ i 1)) 
  ) 
 
  (setq isclose 0) 
  (if(= (cdr (assoc 70 ed1)) 1) 
     (progn 
        (setq isclose 1) 
        (setq lst1 (append lst1 (list (nth 0 lst1)))) 
        (setq lst2 (append lst2 (list 0))) 
  )) 
  (if(equal (distance (nth 0 lst1) (nth (- (length lst1) 1) lst1)) 0.000000001) 
    (setq isclose 1) 
  ) 
  (setq i 1) 
  (repeat (- (length lst1) 2) 
    (progn 
      (setq pt1 (nth (- i 1) lst1)    pt2 (nth i lst1)   pt3 (nth (+ i 1) lst1)) 
      (setq ang1 (nth (- i 1) lst2)   ang2 (nth i lst2)) 
      (if(and (equal ang1 0 0.000000001) (equal ang2 0 0.00000001)) 
         (yp008c en1 pt1 pt2 pt3) 
      ) 
      (setq i (+ i 1)) 
    ) 
  ) 
  (if(= isclose 1) 
     (progn 
       (setq pt1 (nth (- (length lst1) 2) lst1)    pt2 (nth 0 lst1)   pt3 (nth 1 lst1)) 
       (setq ang1 (nth (- (length lst1) 2) lst2)   ang2 (nth 0 lst2)) 
       (if(and (equal ang1 0 0.000000001) (equal ang2 0 0.00000001)) 
         (yp008c en1 pt1 pt2 pt3) 
       ) 
  )  ) 
 
) 
 
(defun yp008c(en1 pt1 pt2 pt3 / x1 x2 y1 y2 en4 en5) 
   (setq pt1 (trans pt1 0 1)   pt2 (trans pt2 0 1)   pt3 (trans pt3 0 1)) 
   (if(and (> (distance pt1 pt2)  (* dd 2))  (> (distance pt3 pt2)  (* dd 2))) 
      (progn 
         (setq x1 (yp008x pt2 pt1 dd) 
               x2 (yp008x pt2 pt3 dd) 
               y1 (yp008y pt2 pt1 dd) 
               y2 (yp008y pt2 pt3 dd) 
         ) 
         (command "_area" "o" en1) 
         (setq en4 (getvar "AREA")) 
;(prompt (strcat "\n" (rtos x1 2 2) ";" (rtos y1 2 2))) 
         (command "_fillet"  (list x2 y2) (list x1 y1) )  ;;en5) 
;(prompt (strcat "\n" (rtos x2 2 2) ";" (rtos y2 2 2))) 
         (command "_area" "o" en1) 
         (setq en5 (getvar "AREA")) 
         (IF(> EN4 EN5) 
            (progn 
              (command "u") 
              (command "u") 
              (command "u") 
         )   ) 
 
     ;    (IF(> EN4 EN5) (COMMAND "UNDO" 2)) 
         
   )  ) 
) 
 
(defun yp008x(pt2 pt1 d / x3 d1) 
   (setq d1 (distance pt2 pt1)) 
   (if(equal (car pt1) (car pt2) 0.00000001) 
      (setq x3 (car pt1)) 
      (setq x3 (+ (car pt2) (* (- (car pt1) (car pt2)) 0.25))) 
   ) 
) 
(defun yp008y(pt2 pt1 d / x3 d1) 
   (setq d1 (distance pt2 pt1)) 
   (if(equal (cadr pt1) (cadr pt2) 0.00000001) 
      (setq x3 (cadr pt1)) 
      (setq x3 (+ (cadr pt2) (* (- (cadr pt1) (cadr pt2)) 0.25))) 
   ) 
) 
 
 
;----------------------倒外角------------------------------------------------------- 
(defun c:n() 
  (setvar "cmdecho" 0) 
  (setq oldosmode (getvar "osmode")) 
     (command "UNDO" "be") 
 
  (setq dd 0.5)   
  (setq rr (getreal"\n请输入圆角半径:")) 
  (command "_fillet" "r" rr ) 
    (setq ss1 (ssget (list (cons 0 "LWPOLYLINE")))) 
  (while(/= SS1 NIL) 
    (progn 
       (setq ii 0) 
       (repeat (sslength ss1) 
         (setq en1 (ssname ss1 ii)) 
         (setq ii (+ ii 1)) 
         (yp007chamfer en1) 
       ) 
       (prompt "\n 完成 请检查:") 
       (setq ss1 (ssget (list (cons 0 "LWPOLYLINE")))) 
    ) 
  ) 
  (setvar "osmode" oldosmode) 
    (command "UNDO" "e") 
  (princ) 
) 
 
(defun yp007chamfer(en1 / isclose i j ed1 pt1 pt2 pt3 lst1 lst2 ) 
  (setq ed1 (entget en1)) 
  (setq i 0) 
  (setq lst1 '()  lst2 '()) 
  (repeat (length ed1) 
    (if(= (car (nth i ed1)) 10) 
       (setq lst1 (append lst1 (list (cdr (nth i ed1))))) 
    ) 
    (if(= (car (nth i ed1)) 42) 
       (setq lst2 (append lst2 (list (cdr (nth i ed1))))) 
    ) 
    (setq i (+ i 1)) 
  ) 
 
  (setq isclose 0) 
  (if(= (cdr (assoc 70 ed1)) 1) 
     (progn 
        (setq isclose 1) 
        (setq lst1 (append lst1 (list (nth 0 lst1)))) 
        (setq lst2 (append lst2 (list 0))) 
  )) 
  (if(equal (distance (nth 0 lst1) (nth (- (length lst1) 1) lst1)) 
0.000000001) 
    (setq isclose 1) 
  ) 
  (setq i 1) 
  (repeat (- (length lst1) 2) 
    (progn 
      (setq pt1 (nth (- i 1) lst1)    pt2 (nth i lst1)   pt3 (nth (+ i 1) 
lst1)) 
      (setq ang1 (nth (- i 1) lst2)   ang2 (nth i lst2)) 
      (if(and (equal ang1 0 0.000000001) (equal ang2 0 0.00000001)) 
         (yp007c en1 pt1 pt2 pt3) 
      ) 
      (setq i (+ i 1)) 
    ) 
  ) 
  (if(= isclose 1) 
     (progn 
       (setq pt1 (nth (- (length lst1) 2) lst1)    pt2 (nth 0 lst1)   pt3 
(nth 1 lst1)) 
       (setq ang1 (nth (- (length lst1) 2) lst2)   ang2 (nth 0 lst2)) 
       (if(and (equal ang1 0 0.000000001) (equal ang2 0 0.00000001)) 
         (yp007c en1 pt1 pt2 pt3) 
       ) 
  )  ) 
 
) 
 
(defun yp007c(en1 pt1 pt2 pt3 / x1 x2 y1 y2 en4 en5) 
   (setq pt1 (trans pt1 0 1)   pt2 (trans pt2 0 1)   pt3 (trans pt3 0 1)) 
   (if(and (> (distance pt1 pt2)  (* dd 2))  (> (distance pt3 pt2)  (* dd 
2))) 
      (progn 
         (setq x1 (yp007x pt2 pt1 dd) 
               x2 (yp007x pt2 pt3 dd) 
               y1 (yp007y pt2 pt1 dd) 
               y2 (yp007y pt2 pt3 dd) 
         ) 
         (command "_area" "o" en1) 
         (setq en4 (getvar "AREA")) 
          
         (command "_fillet"  (list x2 y2) (list x1 y1) )  ;;en5) 
         (command "_area" "o" en1) 
         (setq en5 (getvar "AREA")) 
         (IF(< EN4 EN5) (COMMAND "UNDO" 2)) 
         
   )  ) 
) 
 
(defun yp007x(pt2 pt1 d / x3 d1) 
   (setq d1 (distance pt2 pt1)) 
   (if(equal (car pt1) (car pt2) 0.00000001) 
      (setq x3 (car pt1)) 
      (setq x3 (+ (car pt2) (* (- (car pt1) (car pt2)) 0.5))) 
   ) 
) 
(defun yp007y(pt2 pt1 d / x3 d1) 
   (setq d1 (distance pt2 pt1)) 
   (if(equal (cadr pt1) (cadr pt2) 0.00000001) 
      (setq x3 (cadr pt1)) 
      (setq x3 (+ (cadr pt2) (* (- (cadr pt1) (cadr pt2)) 0.5))) 
   ) 
)

st788796 · 发表于 2013-10-4 01:49:48

ysq101 发表于 2013-10-3 23:05
我来分享网上下载的源码,,,好像也是根据三点面积来判断是凹角还是凸角的...可以参考一下

原作者忘了 ...

Command 有时候不灵光，没有运行成功

kcad2010 · 发表于 2013-10-4 13:15:48

提示: 作者被禁止或删除内容自动屏蔽

st788796 · 发表于 2013-10-4 15:06:32

kcad2010 发表于 2013-10-4 13:15
看样子，好像是同行哦，做模具设计的吧？

完全不懂模具，不过这个有具体要求的话，可以写一个用XDAPI的插件

ysq101 · 发表于 2013-10-4 16:24:23

kcad2010 发表于 2013-10-4 13:15
看样子，好像是同行哦，做模具设计的吧？

没错..我就是模具专业的~~不过不是模具设计...而是模具加工

ysq101 · 发表于 2013-10-4 16:25:06

st788796 发表于 2013-10-4 01:49
Command 有时候不灵光，没有运行成功

呵..没办法...对于新手来说只能看得懂COMMAND了...

xyp1964 · 发表于 2013-10-4 23:32:32

账号		自动登录	找回密码
密码			立即注册

kcad2010 kcad2010 当前离线 UID 677304 积分 391 精华贡献威望活跃度 D豆在线时间小时注册时间 2013-6-7 最后登录 1970-1-1 窥视卡雷达卡已领礼包: 182个财富等级: 日进斗金	发表于 2013-10-4 13:15:48 \| 显示全部楼层【广而告之】积分规则、D豆获取攻略窝窝空间装扮攻略提示: 作者被禁止或删除内容自动屏蔽
	论坛插件加载方法发帖求助前要善用【论坛搜索】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【D豆】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
	回复支持反对使用道具举报

[研讨] 关于多边形凸角凹角的判断

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分

点评

点评

点评

点评

点评

评分