[转帖]判断点是否在多边形中的分析

efan2000

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

复制代码

myfreemind

好帖！！

bluemoon

好帖 献花一朵！

chb801

好帖！

无痕

射线给一个很小的角度，如0.000000001，就可以避免水平重合的判断问题。

meflying

无痕发表于2004-1-12 23:33:00射线给一个很小的角度，如0.000000001，就可以避免水平重合的判断问题。

那对于有这么一个偏角的直线不是一样的吗？

无痕

实际超做中会有么？那概率是多少？

changyiran

这种情况根据你的算法应该判断是错误的吧。如图点位于水平边所在直线上，不记水平边，交点应该是2个，岂不错误？