[原创]：判断一点是否在不规则多边形内，有算法

xiao_longxin

2. 
   
3. ;;By Xiao_longxin 明经通道
   
4. ;;有一不规则多边形由点a1(x1,y1)、a2(x2,y2).....an(xn,yn)依次连接而成，如何求证点p(x,y)是在多边形内还是多边形外？
   
5. ;;将直线PAi记作ki.将ki旋转到ki+1(令kn+1=k1)的角记为βi(规定逆时针为正，顺时针为负，如果βi大于180侧令βi＝βi－360)。
   
6. ;;从直观上看有下面的结论
   
7. ;;若P在形内，诸β的代数和为360度；
   
8. ;;若P在形外，诸β的代数和为0。
   
9. 
   
10. ;;pt_list 为((x y z) (x y z)......(x y z))即围成多边形的表
    
11. ;;
    
12. ;;自相交多边形适用，不适用于曲线
    
13. 
    
14. (defun pt_inorout ( pt_list pt / e1 pt  n i j va va_count)
    
15.   ;(setq pt_list (quxian->pline (car (entsel))))
    
16.   ;(setq pt (getpoint))
    
17.   (setq        i 0
    
18.         va_count 0
    
19.   )
    
20.   (setq n (length pt_list))
    
21.   (repeat (- n 1)
    
22.     (setq va (-        (angle pt (nth i pt_list))
    
23.                 (angle pt (nth (+ 1 i) pt_list))
    
24.              )
    
25.     )
    
26.     (cond ((> va pi)
    
27.            (setq va (- va pi))
    
28.           )
    
29.           ((< va (* -1 pi))
    
30.            (setq va (+ va pi))
    
31.           )
    
32.     )
    
33.     (setq va_count (+ va_count va))
    
34.     (setq i (1+ i))
    
35.   )
    
36.   (setq        va (- (angle pt (nth i pt_list))
    
37.               (angle pt (nth 0 pt_list))
    
38.            )
    
39.   )
    
40.   (cond        ((> va pi)
    
41.          (setq va (- va pi))
    
42.         )
    
43.         ((< va (* -1 pi))
    
44.          (setq va (+ va pi))
    
45.         )
    
46.   )
    
47.   (setq va_count (+ va_count va))
    
48.   (if (< (abs (- (abs va_count) pi)) 0.000001)
    
49.     't
    
50.     'nil
    
51.   )
    
52. )
    

<br /> ;;By Xiao_longxin 明经通道<br /> ;;有一不规则多边形由点a1(x1,y1)、a2(x2,y2).....an(xn,yn)依次连接而成，如何求证点p(x,y)是在多边形内还是多边形外？<br /> ;;将直线PAi记作ki.将ki旋转到ki+1(令kn+1=k1)的角记为βi(规定逆时针为正，顺时针为负，如果βi大于180侧令βi＝βi－360)。<br /> ;;从直观上看有下面的结论<br /> ;;若P在形内，诸β的代数和为360度；<br /> ;;若P在形外，诸β的代数和为0。<br /> <br /> ;;pt_list 为((x y z) (x y z)......(x y z))即围成多边形的表<br /> ;;<br /> ;;自相交多边形适用，不适用于曲线<br /> <br /> (defun pt_inorout ( pt_list pt / e1 pt  n i j va va_count)<br />   ;(setq pt_list (quxian->pline (car (entsel))))<br />   ;(setq pt (getpoint))<br />   (setq        i 0<br />         va_count 0<br />   )<br />   (setq n (length pt_list))<br />   (repeat (- n 1)<br />     (setq va (-        (angle pt (nth i pt_list))<br />                 (angle pt (nth (+ 1 i) pt_list))<br />              )<br />     )<br />     (cond ((> va pi)<br />            (setq va (- va pi))<br />           )<br />           ((< va (* -1 pi))<br />            (setq va (+ va pi))<br />           )<br />     )<br />     (setq va_count (+ va_count va))<br />     (setq i (1+ i))<br />   )<br />   (setq        va (- (angle pt (nth i pt_list))<br />               (angle pt (nth 0 pt_list))<br />            )<br />   )<br />   (cond        ((> va pi)<br />          (setq va (- va pi))<br />         )<br />         ((< va (* -1 pi))<br />          (setq va (+ va pi))<br />         )<br />   )<br />   (setq va_count (+ va_count va))<br />   (if (< (abs (- (abs va_count) pi)) 0.000001)<br />     't<br />     'nil<br />   )<br /> )<br />

yicai

这程序运行不了,问题出在quxian

狂刀

我觉得不支持曲线，意义不大

xiao_longxin

可以把曲线模拟成近似的多边形，但这样子影响了程序的速度和精度

狂刀

射线法，谁来？

xiao_longxin

其实我也觉得射线法比较实用，并且对于曲线同样适用。但是因为要排除过顶点和与边重合的情况，使编程有了一定的难度,且不适用于曲线。但是我个人认为，如果不去理会这些特殊情况，在四个方向上做四条射线，如果有三条以上的射线与线的交点为奇数就可以认为是在线内了。虽然有时可能会现错，但这个概率应该是很低很低的了，在实际工作中应该是可以接受的。

lovelife80356

实际应用范围不大,还是谢谢

陌生人

通常的射线法是做xline或一条很长的line与曲线相交. 根据与曲线交点的单双数来确定内外.
但是经过研究,用ray做为射线法也很好,关键是取什么方向的ray来与曲线相交.以前做的一个程序,
用一个几乎不可能的角度,如 0.04051545,效果也很好,可以说成功率几乎100%,因为在实际做图中几乎不可能画出一条角度为0.04051545的线来与xline重合,这样就可以有效避免计算中的难点,当然,可用vlax-curve-getclosestpoint先判断点是否在曲线上.
但是,我想说的是,取角度还有更科学的方法,我现在正在调一个程序,时间关系,估计晚上能完成.

yshf

该程序除点落在多边形的边上判断结果有问题外，其它结果均正确。在计多边形最后一点与第一个点的夹角时，程序太长，现改为如下：
(defun pt_inorout ( pt_list pt / e1 pt  n i j va va_count)
  (setq        i 0  va_count 0  n (length pt_list)
        pt_list (append pt_list (list (car pt_list)))
  )
  (repeat n
    (setq va (-        (angle pt (nth i pt_list))
                (angle pt (nth (1+ i) pt_list))
             )
    )
    (cond ((> va pi) (setq va (- va pi)))
          ((< va (* -1 pi)) (setq va (+ va pi)))
    )
    (setq va_count (+ va_count va)  i (1+ i))
  )
  (if (< (abs (- (abs va_count) pi)) 0.000001)
    't
    'nil
  )
)

xiao_longxin

有劳楼上的帮我修改了，代码的确是短了很多

xyp1964

(< (abs (- (abs va_count) pi)) 0.000001)
可改为
(> va_count 3.14159)

aeo

no:
(equal  (abs va_count)pi 0.00001)

WHGF

我用上面的程序为什么运行不了？各位老大

zhynt

呵呵，记得以前我编修剪程序时讨论过这个问题，我是用射线法来确定的。

狂刀

不明白，为什么经过精简之后还有那么多代码,应该像这样：
[php]
(defun inorout (lst pt)
(equal PI (apply '+ (mapcar '(lambda(x y)(rem (- (angle pt x)(angle pt y)) PI)) (cons (last lst) lst) lst)) 1e-4)
)
[/php]
测试：

2. 
   
3. (defun c:tt()
   
4. (setq        lst (mapcar 'cdr (vl-remove-if
   
5.               '(lambda (x) (/= 10 (car x)))
   
6.               (entget (car (entsel)))
   
7.             ))
   
8.         pt  (getpoint)
   
9.   )
   
10.   (inorout lst pt)
    
11. )
    

<br /> (defun c:tt()<br /> (setq        lst (mapcar 'cdr (vl-remove-if<br />               '(lambda (x) (/= 10 (car x)))<br />               (entget (car (entsel)))<br />             ))<br />         pt  (getpoint)<br />   )<br />   (inorout lst pt)<br /> )<br />