找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2958|回复: 34

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

[复制链接]

已领礼包: 3个

财富等级: 恭喜发财

发表于 2005-6-10 18:14:26 | 显示全部楼层 |阅读模式

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

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

×

  1. ;;By Xiao_longxin 明经通道
  2. ;;有一不规则多边形由点a1(x1,y1)、a2(x2,y2).....an(xn,yn)依次连接而成,如何求证点p(x,y)是在多边形内还是多边形外?
  3. ;;将直线PAi记作ki.将ki旋转到ki+1(令kn+1=k1)的角记为βi(规定逆时针为正,顺时针为负,如果βi大于180侧令βi=βi-360)。
  4. ;;从直观上看有下面的结论
  5. ;;若P在形内,诸β的代数和为360度;
  6. ;;若P在形外,诸β的代数和为0。

  7. ;;pt_list 为((x y z) (x y z)......(x y z))即围成多边形的表
  8. ;;
  9. ;;自相交多边形适用,不适用于曲线

  10. (defun pt_inorout ( pt_list pt / e1 pt  n i j va va_count)
  11.   ;(setq pt_list (quxian->pline (car (entsel))))
  12.   ;(setq pt (getpoint))
  13.   (setq        i 0
  14.         va_count 0
  15.   )
  16.   (setq n (length pt_list))
  17.   (repeat (- n 1)
  18.     (setq va (-        (angle pt (nth i pt_list))
  19.                 (angle pt (nth (+ 1 i) pt_list))
  20.              )
  21.     )
  22.     (cond ((> va pi)
  23.            (setq va (- va pi))
  24.           )
  25.           ((< va (* -1 pi))
  26.            (setq va (+ va pi))
  27.           )
  28.     )
  29.     (setq va_count (+ va_count va))
  30.     (setq i (1+ i))
  31.   )
  32.   (setq        va (- (angle pt (nth i pt_list))
  33.               (angle pt (nth 0 pt_list))
  34.            )
  35.   )
  36.   (cond        ((> va pi)
  37.          (setq va (- va pi))
  38.         )
  39.         ((< va (* -1 pi))
  40.          (setq va (+ va pi))
  41.         )
  42.   )
  43.   (setq va_count (+ va_count va))
  44.   (if (< (abs (- (abs va_count) pi)) 0.000001)
  45.     't
  46.     'nil
  47.   )
  48. )
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
发表于 2005-6-10 19:50:37 | 显示全部楼层
这程序运行不了,问题出在quxian
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2005-6-10 20:11:20 | 显示全部楼层
我觉得不支持曲线,意义不大
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 3个

财富等级: 恭喜发财

 楼主| 发表于 2005-6-10 21:15:16 | 显示全部楼层
可以把曲线模拟成近似的多边形,但这样子影响了程序的速度和精度
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2005-6-13 23:32:16 | 显示全部楼层
射线法,谁来?
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 3个

财富等级: 恭喜发财

 楼主| 发表于 2005-6-14 11:38:05 | 显示全部楼层
其实我也觉得射线法比较实用,并且对于曲线同样适用。但是因为要排除过顶点和与边重合的情况,使编程有了一定的难度,且不适用于曲线。但是我个人认为,如果不去理会这些特殊情况,在四个方向上做四条射线,如果有三条以上的射线与线的交点为奇数就可以认为是在线内了。虽然有时可能会现错,但这个概率应该是很低很低的了,在实际工作中应该是可以接受的。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2005-6-14 12:02:34 | 显示全部楼层
实际应用范围不大,还是谢谢
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2005-6-14 12:33:19 | 显示全部楼层
通常的射线法是做xline或一条很长的line与曲线相交. 根据与曲线交点的单双数来确定内外.
但是经过研究,用ray做为射线法也很好,关键是取什么方向的ray来与曲线相交.以前做的一个程序,
用一个几乎不可能的角度,如 0.04051545,效果也很好,可以说成功率几乎100%,因为在实际做图中几乎不可能画出一条角度为0.04051545的线来与xline重合,这样就可以有效避免计算中的难点,当然,可用vlax-curve-getclosestpoint先判断点是否在曲线上.
但是,我想说的是,取角度还有更科学的方法,我现在正在调一个程序,时间关系,估计晚上能完成.
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 111个

财富等级: 日进斗金

发表于 2005-6-14 15:57:49 | 显示全部楼层
该程序除点落在多边形的边上判断结果有问题外,其它结果均正确。在计多边形最后一点与第一个点的夹角时,程序太长,现改为如下:
(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
  )
)
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 3个

财富等级: 恭喜发财

 楼主| 发表于 2005-6-14 17:50:58 | 显示全部楼层
有劳楼上的帮我修改了,代码的确是短了很多
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2005-6-14 18:55:00 | 显示全部楼层
(< (abs (- (abs va_count) pi)) 0.000001)
可改为
(> va_count 3.14159)
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 488个

财富等级: 日进斗金

发表于 2005-6-15 23:05:33 | 显示全部楼层
no:
(equal  (abs va_count)pi 0.00001)
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2005-6-17 07:36:53 | 显示全部楼层
我用上面的程序为什么运行不了?各位老大
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2005-6-18 01:35:04 | 显示全部楼层
呵呵,记得以前我编修剪程序时讨论过这个问题,我是用射线法来确定的。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2005-6-18 14:30:26 | 显示全部楼层
不明白,为什么经过精简之后还有那么多代码,应该像这样:
[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]
测试:

  1. (defun c:tt()
  2. (setq        lst (mapcar 'cdr (vl-remove-if
  3.               '(lambda (x) (/= 10 (car x)))
  4.               (entget (car (entsel)))
  5.             ))
  6.         pt  (getpoint)
  7.   )
  8.   (inorout lst pt)
  9. )
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-3-28 18:17 , Processed in 0.567494 second(s), 59 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表