[分享]：也谈关于如何测试点是否在任意多边形内（用纯lisp）

zhynt

测试点是否在多边形内用的是“射线法”，即过点作一条射线，如果该射线与多边形相交奇数次，则点在多边形内，如果不相交或相交偶数次，则点在多边形外。问题是在cad中如何用lsp作这条假想的射线。
我的方法是，先测出多边形的总宽度，过点向左和右作两条比这个宽度稍长的线，如果两边均与多边形相交奇数次，则点在多边形内。为了更严谨，我上下左右作四条线。

2. 
   
3. ;;获取表中最大值
   
4. (defun max_lst (lst / lst n m a b maxpt)
   
5.   (setq n (length lst))
   
6.   (setq m 0)
   
7.   (setq a (nth 0 lst))
   
8.   (while (/= m n)
   
9.     (setq b (nth m lst))
   
10.     (if        (> b a)
    
11.       (setq maxpt b
    
12.             a b
    
13.       )
    
14.       (setq maxpt a)
    
15.     )
    
16.     (setq m (1+ m))
    
17.   )
    
18.   maxpt
    
19. )
    
20. ;;获取表中最小值
    
21. (defun min_lst (lst / lst n m a b minpt)
    
22.   (setq n (length lst))
    
23.   (setq m 0)
    
24.   (setq a (nth 0 lst))
    
25.   (while (/= m n)
    
26.     (setq b (nth m lst))
    
27.     (if        (< b a)
    
28.       (setq minpt b
    
29.             a b
    
30.       )
    
31.       (setq minpt a)
    
32.     )
    
33.     (setq m (1+ m))
    
34.   )
    
35.   minpt
    
36. )
    
37. ;;将点表中的x或y坐标组成新表
    
38. (defun point_x (pt_lst xory / pt_xlst)
    
39.   (setq pt_xlst '())
    
40.   (foreach n pt_lst
    
41.     (if        (= xory x)
    
42.       (setq pt_xlst (cons (car n) pt_xlst))
    
43.     )
    
44.     (if        (= xory y)
    
45.       (setq pt_xlst (cons (cadr n) pt_xlst))
    
46.     )
    
47.   )
    
48.   (setq pt_xlst (reverse pt_xlst))
    
49. )
    
50. ;;测试点是否在多边形内(判断四个方向,如果四个方向均认为在多边形内，点就肯定在多边形内。)
    
51. (defun ea:point_inm (p pm xory ang / p1 p2 tf tf1 tf2 mx my)
    
52.   (setq mx (- (max_lst (point_x pm xory)) (min_lst (point_x pm xory))))
    
53.   (setq        p1  (last pm)
    
54.         px1 (polar p ang (+ mx 100))
    
55.   )
    
56.   (foreach p2 pm
    
57.     (if        (inters p px1 p1 p2)
    
58.       (if (= tf nil)
    
59.         (setq tf t)
    
60.         (setq tf nil)
    
61.       )
    
62.     )
    
63.     (setq p1 p2)
    
64.   )
    
65.   tf
    
66. )
    
67. 
    
68. (defun c:qqq ()
    
69.   (setq aalst '())
    
70.   (setq aa (getpoint "\n选取多边形的一个顶点"))
    
71.   (setq aalst (cons aa aalst))
    
72.   (setq dd aa)
    
73.   (while (setq cc (getpoint aa "\n选取多边形的下一顶点"))
    
74.     (grdraw aa cc 7 1)
    
75.     (setq aa cc)
    
76.     (setq aalst (cons aa aalst))
    
77.   )
    
78.   (grdraw aa dd 7 1)
    
79.   (while (setq bb (getpoint "\n选取一点"))
    
80.     (if        (or (and (ea:point_inm bb aalst x 0)
    
81.                  (ea:point_inm bb aalst x pi)
    
82.             )
    
83.             (and (ea:point_inm bb aalst x (* 0.5 pi))
    
84.                  (ea:point_inm bb aalst x (* 1.5 pi))
    
85.             )
    
86.         )
    
87.       (princ "\n该点在多边形内 ")
    
88.       (princ "\n该点不在多边形内")
    
89.     )
    
90.   )
    
91.   (princ)
    
92. )
    

<br /> ;;获取表中最大值<br /> (defun max_lst (lst / lst n m a b maxpt)<br />   (setq n (length lst))<br />   (setq m 0)<br />   (setq a (nth 0 lst))<br />   (while (/= m n)<br />     (setq b (nth m lst))<br />     (if        (> b a)<br />       (setq maxpt b<br />             a b<br />       )<br />       (setq maxpt a)<br />     )<br />     (setq m (1+ m))<br />   )<br />   maxpt<br /> )<br /> ;;获取表中最小值<br /> (defun min_lst (lst / lst n m a b minpt)<br />   (setq n (length lst))<br />   (setq m 0)<br />   (setq a (nth 0 lst))<br />   (while (/= m n)<br />     (setq b (nth m lst))<br />     (if        (< b a)<br />       (setq minpt b<br />             a b<br />       )<br />       (setq minpt a)<br />     )<br />     (setq m (1+ m))<br />   )<br />   minpt<br /> )<br /> ;;将点表中的x或y坐标组成新表<br /> (defun point_x (pt_lst xory / pt_xlst)<br />   (setq pt_xlst '())<br />   (foreach n pt_lst<br />     (if        (= xory x)<br />       (setq pt_xlst (cons (car n) pt_xlst))<br />     )<br />     (if        (= xory y)<br />       (setq pt_xlst (cons (cadr n) pt_xlst))<br />     )<br />   )<br />   (setq pt_xlst (reverse pt_xlst))<br /> )<br /> ;;测试点是否在多边形内(判断四个方向,如果四个方向均认为在多边形内，点就肯定在多边形内。)<br /> (defun ea:point_inm (p pm xory ang / p1 p2 tf tf1 tf2 mx my)<br />   (setq mx (- (max_lst (point_x pm xory)) (min_lst (point_x pm xory))))<br />   (setq        p1  (last pm)<br />         px1 (polar p ang (+ mx 100))<br />   )<br />   (foreach p2 pm<br />     (if        (inters p px1 p1 p2)<br />       (if (= tf nil)<br />         (setq tf t)<br />         (setq tf nil)<br />       )<br />     )<br />     (setq p1 p2)<br />   )<br />   tf<br /> )<br /> <br /> (defun c:qqq ()<br />   (setq aalst '())<br />   (setq aa (getpoint "\n选取多边形的一个顶点"))<br />   (setq aalst (cons aa aalst))<br />   (setq dd aa)<br />   (while (setq cc (getpoint aa "\n选取多边形的下一顶点"))<br />     (grdraw aa cc 7 1)<br />     (setq aa cc)<br />     (setq aalst (cons aa aalst))<br />   )<br />   (grdraw aa dd 7 1)<br />   (while (setq bb (getpoint "\n选取一点"))<br />     (if        (or (and (ea:point_inm bb aalst x 0)<br />                  (ea:point_inm bb aalst x pi)<br />             )<br />             (and (ea:point_inm bb aalst x (* 0.5 pi))<br />                  (ea:point_inm bb aalst x (* 1.5 pi))<br />             )<br />         )<br />       (princ "\n该点在多边形内 ")<br />       (princ "\n该点不在多边形内")<br />     )<br />   )<br />   (princ)<br /> )<br />

)欢迎大家来测试。看看有没有例外。

wkai

运行出错呀~
另外我想这种情况，是不是测不准？
算法设计不精密，测四个方向的意义不大，只是提高了准确率，却不能做到100%准确~
我想，
除了测量射线与多边形的各边的交点数（M）,
还需要测量在射线上的多边形的端点数（N）,
与射线重合的多边形边线的条数（O）
如果（rem  （- （+ M N） O）2）为奇数则在多边形内部，否则就在外部。

zhynt

说说有什么提示，我这里是好的呀，我试了上面的图形没有问题，同样可以的。

wkai

那为什么要测四个方向呢？

zhynt

呵呵上面的程序是有个错误，现在改好了，你试试，我上面说过，只要两个方向就行了。
嗯上面的图形确实有问题，你说的对！

playboy

转贴此帖来自明经通道
(defun GetNext (i n)
  (if (= i (1- n))
    0
    (1+ i)
  )
)

(defun c:test( / ss pt sname ent pt_tmp pt_lst vname area areaall)
  (setq ss (ssget))
  (setq pt (getpoint "Enter the point:"))
  (setq sname (ssname ss 0))
  (setq ent (entget sname))
  (while (setq pt_tmp (assoc 10 ent))
    (setq pt_lst (append pt_lst (list (cdr pt_tmp))))
    (setq ent (cdr (member pt_tmp ent)))
    (setq pts (append pts (list pt)))
  )
  (setq area 0)
  (setq i 0)
  (setq n (length pt_lst))
  (while (< i n)
    (entmake (list '(0 . "LWPOLYLINE") '(100 . "AcDbEntity") '(67 . 0) '(410 . "Model") '(100 . "AcDbPolyline")
     '(90 . 7) '(70 . 0) '(43 . 0.0) '(38 . 0.0) '(39 . 0.0)
     (cons 10 pt)
     '(40 . 0.0) '(41 . 0.0) '(42 . 0.0)
     (cons 10 (nth i pt_lst))
     '(40 . 0.0) '(41 . 0.0) '(42 . 0.0)
     (cons 10 (nth (GetNext i n) pt_lst))
     '(210 0.0 0.0 1.0))
      )
    (setq ent (entlast))
    (setq vname (vlax-ename->vla-object ent))
    (setq area (+ area (vla-get-area vname)))
    (entdel ent)
    (setq i (1+ i))
  )
  (setq areaall (vla-get-area (vlax-ename->vla-object sname)))
  (if (equal area areaall 0.000000001)
    (princ "\nin")
    (princ "\nout")
  )
  (princ)
)

zhynt

改了一下，现在只有一种情况判断错误，就是当点在……怎么说呢看图吧，就是wkai提供的图形的那个点上，我想只要再增加其它的角度，只要其中任一角度判断在多边形内那点就在多边形内。当然那个点那个点还是存在的，但是碰到这个点的可能性就太小了，已经能满足实际需要了。

现在知道我判断四个方向的用意了吧。

playboy

就是用四个点虚拟出一个矩形然后再判断这个点的坐标就可以了是吗

wkai

最初由 zhynt 发布
[B]现在知道我判断四个方向的用意了吧。 [/B]

算法精确的话，只需要判断一次~
测试一下我的程序
http://www.xdcad.net/forum/showt ... d=677002#post677002

aeo

射线算法，autodesk上好像有.
晓东用arx写的(好像有bug)

求的那点射向无重远(保证出那个框就可以)
交点是单数就在里面，反之在外面.(除在曲线上)

zhynt

主要是在lsp中作不出无穷远的点,只要是有长度,就有例外.

LUCAS

2. 
   
3. ;; From a Tony Tanzillo suggestion, see
   
4. ;; John Uhden's @cv_inside function thread.
   
5. ;; minimal, dirty, etc...
   
6. ;;
   
7. (defun ALE_ISINSIDE (IMPPNT ENTNAM / NEWENT ENTARE)
   
8.   (command "_.AREA" "_O" ENTNAM)
   
9.   (setq ENTARE (getvar "AREA"))
   
10.   (command "_.OFFSET" (/ ENTARE 10000) ENTNAM IMPPNT "" "_.AREA" "_O"
    
11.     (setq NEWENT (entlast))
    
12.   )
    
13.   (entdel NEWENT)
    
14.   (> ENTARE (getvar "AREA"))
    
15. )
    
16. 
    
17. ;;command: pline 0.0 100,0 100,50 0,50 c
    
18. 
    
19. ;;command: (ALE_IsInside '(-0.00000000001 -0.00000000001) (entlast))
    
20. ;;nil
    
21. 
    
22. ;;command: (ALE_IsInside '(0.00000000001 0.00000000001) (entlast))
    
23. ;;T
    

<br /> ;; From a Tony Tanzillo suggestion, see<br /> ;; John Uhden's @cv_inside function thread.<br /> ;; minimal, dirty, etc...<br /> ;; <br /> (defun ALE_ISINSIDE (IMPPNT ENTNAM / NEWENT ENTARE)<br />   (command "_.AREA" "_O" ENTNAM)<br />   (setq ENTARE (getvar "AREA"))<br />   (command "_.OFFSET" (/ ENTARE 10000) ENTNAM IMPPNT "" "_.AREA" "_O"<br />     (setq NEWENT (entlast))<br />   )<br />   (entdel NEWENT)<br />   (> ENTARE (getvar "AREA"))<br /> )<br /> <br /> ;;command: pline 0.0 100,0 100,50 0,50 c<br /> <br /> ;;command: (ALE_IsInside '(-0.00000000001 -0.00000000001) (entlast))<br /> ;;nil<br /> <br /> ;;command: (ALE_IsInside '(0.00000000001 0.00000000001) (entlast))<br /> ;;T<br />

lt_zzy

如果那个点在图形上的时候会出现不同的结果，有的点详图形上，有的点说不图形上。主要表现在凹多边形。

zhynt

Wkai的程序比我的强多了，我的这个基本上可以枪毙了。