[分享]：通过算法精确测试点与多边形的位置关系

小菜 · 发表于 2004-3-3 12:15:14

这个方法有点意思，暂时没发现什么问题
对曲线也有效

陌生人 · 发表于 2004-3-3 14:51:03

最初由 lsjjm 发布
[B]

试试这个:
(defun isinside (p ent)
(command "_.area" "_O" ent)
... [/B]

offset 不一定是得到一个实体。得做些处理，不然有残留物。
以下测试分别对应图中pt1~pt5点，返回有异常，未排除残留物的影响。

ISINSIDE

Command: (isinside (getpoint)(car(entsel)))
>>
Select object: nil

Command: (isinside (getpoint)(car(entsel)))

Select object: T

Command: (isinside (getpoint)(car(entsel)))

Select object: T

Command: (isinside (getpoint)(car(entsel)))

Select object: T

Command: (isinside (getpoint)(car(entsel)))

Select object: nil

陌生人 · 发表于 2004-3-3 14:55:20

测试文件
测试时候请先删除残留的多余实体

小菜 · 发表于 2004-3-3 15:20:36

看来需要判断曲线不能自相交

陌生人 · 发表于 2004-3-3 15:54:51

贴一个判断点在曲线内外的测试程序，对自相交有效，就目前我自己测试，成功率100％
但要判断是否在线上，大家自己开动脑筋想想吧：）
[php]
;|
(setq ent (car(entsel)))
(while (setq pt (getpoint "\n选择点:"))
  (x@-ptin ent pt)
)
|;
(defun x@-ptin (ent pt / e)
  (setq e (entlast))
  (vl-cmdf ".boundary" "a" "o" "r" "b" "n" ent "" "" pt "")
  (if (eq (entlast) e)
(princ "\n点在曲线外.")
(progn (entdel (entlast))(princ "\n点在曲线内."))
  )
)
[/php]

另发一个已经加上判断在曲线上的测试程序：
判断点与曲线内外关系(boundary方法)--------------------------陌生人.2004.2
返回: 0 (在曲线内) ;1 (在曲线上)； 2 (在曲线外)|;
加载后运行:test

eachy · 发表于 2004-3-3 20:55:09

12.　　判断点是否在多边形中：
　　判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点，向左方作射线L，
由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多
边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易
看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
　　但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中，L和多边形的顶点相交，这时候交点只
能计算一个；在图(b)中，L和多边形顶点的交点不应被计算；在图(c)和(d) 中，L和多边形的一条边重合，这条
边应该被忽略不计。如果L和多边形的一条边重合，这条边应该被忽略不计。
　　为了统一起见，我们在计算射线L和多边形的交点的时候，
1。对于多边形的水平边不作考虑；
2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；
3。对于P在多边形边上的情形，直接可判断P属于多边行。由此得出算法的伪代码如下：
count ← 0;
以P为端点，作从右向左的射线L;
for 多边形的每条边s
do if P在边s上
then return true;
if s不是水平的
then if s的一个端点在L上
if 该端点是s两端点中纵坐标较大的端点
then count ← count+1
else if s和L相交
then count ← count+1;
if count mod 2 = 1
then return true;
else return false;
　　其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正数），则P和P'就确定了射线L。
　　判断点是否在多边形中的这个算法的时间复杂度为O(n)。
　　另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点数运算所以
会带来一定误差，不推荐大家使用。

复制代码

陌生人 · 发表于 2004-3-3 21:00:10

我也做了一个通过构造线判定的程序，在19楼
http://www.xdcad.net/forum/showt ... d=691090#post691090
大家测试看看是否通用

小菜 · 发表于 2004-3-4 08:13:21

19楼、35楼为什么不提供一个源代码？没有源代码就不能在别的函数里调用了
35楼使用boundary的问题在于，当点在内部且很接近边界曲线，而且该曲线在屏幕上没有最大化显示时，结果显示在曲线外面
19楼的程序因不知道是怎么设计的，暂时测不到问题

不知道对于任意曲线及自相交的曲线，有没有通用算法？用acad的命令做出来的程序总是在实战时出点问题

陌生人 · 发表于 2004-3-10 18:32:19

应该没问题，你要先关掉捕捉，如果打开，就捕捉到曲线上，程序中在线上没作判断，因为没生成实体，因此判断为在外。你再试试

(defun c:test ()
(setq ent (car(entsel))
os (getvar "osmode"))
(setvar "osmode" 0)
(while (setq pt (getpoint "\n选择点:"))
(x@-ptin ent pt)
)
(setvar "osmode" os)
)

19楼的程序思路和36楼ea版主的是一样的，细节处理有些不同而已。我觉得用构造线比较稳定（心理感觉：））

小菜 · 发表于 2004-3-11 12:23:11

我试过了不行的，好象与捕捉没有关系，作一个1000*1000的矩形，在屏幕上显示得不要太大，然后点在距顶点2.5@45的地方，结果就不对，我是在实际应用中发现这个问题的，但zoom;e后就是对的
eachy的算法是有数学依据的，对多边形结果都正确，对曲线不行，19楼的程序能否看看代码？

buba · 发表于 2004-5-18 03:53:49

我试了, 没有问题啊!

zhanzujie · 发表于 2004-6-13 02:45:22

能否换一个思路,我是这样想的,不知对不
1在多边形上寻找距给定点pt1最近的点(vlax-curve-getclosedpointto ......)->pt2 ,取得它们之间的距离d.
2,以pt1为圆心略小于d的半径画一圆
3.把二维多边形和圆分别转换为面域REG1和REG2
4.求这两个面域的交集(VLA-BOOLEAN VLA_REG1 INTERSECT VLA_REG2),
5.最后(VLAX-GET-AREA REG1)的值若与所画的圆的面积相同,
则点在多边形内部,否则在外部.

aeo · 发表于 2004-6-13 18:39:50

最初由小菜发布
[B]斗胆改了一下程序，不知道改得对不对，请大家指教:
[CODE]

;以测试点为起点作超过多边形外框的线段A。
;除了测线段A与多边形的各边的交点数（M）,
;还需要测落在在线段A上的多边形的端点?.. [/B]

理论上一点不差!

关键是怎么判断交点是端点.
比如Z字形，和下面一横相交于端点(判断是端点大概要equal)
交点离端点1e-3,你肯定认为是端点了，但这时候它和上面的一横可能不相交。交点数就刚好反了.
xdapi里可能也这样，这时出错.

还是面积求法实在.

maoding · 发表于 2004-7-14 14:59:36

这个我觉得只要在这个点和距曲线最近点划一条线如果线长为0则点在曲线上简单明了

czxue123000 · 发表于 2007-3-19 20:44:46

有VBA代码吗?

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