Microsoft : 判断点的位置

二维平面上给出一个多边形，按点的顺时针顺序表示，多边形可以是凸多边形也可以是凹多边形。
给出一个点，判断这个点是否在这个多边形内部

假如顺时针两个点依次是A (x1,y1), B (x2,y2)那点(x,y)在AB右侧的充要条件就是：
(y2-y)(x-x1)>(y-y1)(x2-x)
对每一条边都做上述判断，方向一定要对

上面说的好像不能正确处理凹的多边形。。

可以用射线法解决。
也就是说从待判定点做向x轴正方向的射线，其和多边形的边（或点）有交点，基本概念是统计总交点数，奇数则在多边形内，偶数则在多边形外。
当然，其中还要考虑交点就是多边形顶点神马的。

我写了一个，自己测试了一下，应该是对的:)。判定函数是那个exam函数

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. int exam(float x1, float y1, float x2, float y2, float xp, float yp)
   
5. {
   
6.         int flag;
   
7.         if(x1==x2)//perallel to y axis
   
8.         {
   
9.                 if(xp < x1)
   
10.                 {
    
11.                         if( (yp-y1)*(yp-y2)<0 || yp==y2)
    
12.                         {
    
13.                                 flag = 1;
    
14.                         }
    
15.                         else flag=0;
    
16.                 }
    
17.                 else flag=0;
    
18.         }
    
19.         else if(y1==y2)//perallel to x axis
    
20.         {
    
21.                 if(yp==y2 && xp<x1 && xp<x2) flag=1;
    
22.                 else flag=0;
    
23.         }
    
24.         else
    
25.         {
    
26.                 float k=(x1-x2)/(y1-y2)*(yp-y2)+x2;
    
27.                 if(xp < k && ((k-x1)*(k-x2)<0 || k==x2)) flag=1;
    
28.                 else flag=0;
    
29.         }
    
30.         return flag;
    
31. }
    
32. 
    
33. 
    
34. int main()
    
35. {
    
36.         int num;
    
37.         cin >> num;
    
38.         float *x=new float[num];
    
39.         float *y=new float[num];
    
40. 
    
41.         for (int i = 0; i < num; ++i)
    
42.         {
    
43.                 cin >> x[i] >> y[i];
    
44.         }
    
45. 
    
46.         float xp, yp;
    
47.         cin >> xp >> yp;
    
48. 
    
49.         //start examining every side
    
50.         int t=0;
    
51.         for (int i = 0; i < num-1; i++)
    
52.         {
    
53.                 t+=exam(x[i],y[i],x[i+1],y[i+1],xp,yp);
    
54.         }
    
55. 
    
56.         t+=exam(x[num-1],y[num-1],x[0],y[0],xp,yp);
    
57.         if(t%2==1) cout << "in!" << endl;
    
58.         else cout << "out!" << endl;
    
59. 
    
60.         delete []x;
    
61.         delete []y;
    
62.         return 0;
    
63. }

复制代码

回复 4# yxyxyx
很好的方法，应该是对的。之前想了半天也没想出怎么处理凹多边形的情况

可以用射线法解决。
也就是说从待判定点做向x轴正方向的射线，其和多边形的边（或点）有交点，基本概念是统计总交点数，奇数则在多边形内，偶数则在多边形外。
当然，其中还要考虑交点就是多边形顶点神马的。

我写了一个，自己测试了一下，应该是对的:)。判定函数是那个exam函数
yxyxyx 发表于 2011-5-13 16:35

方法是对的，实现太复杂了！！
代码如下：

//(x0,y0) (x1,y1)==> (x-x0)*(x1-x0) = (y1-y0)*(y-y0)==> x*(x1-x0) = (y-y0)*(y1-y0) + x0(x1-x0) <==> pt.x*(x1-x0)

bool InPolygon(POINT a[], int n, POINT pt)
{
        assert(a && n>3);

        bool bRet = false;
        for (int i = 0; i < n-1; i++)
        {
                if ((pt.y <= a[i].y && pt.y >= a[i+1].y || pt.y <= a[i+1].y && pt.y >= a[i].y)
                        && (((pt.y-a[i].y)*(a[i+1].y-a[i].y)+a[i].x*(a[i+1].x-a[i].x)) >= pt.x*(a[i+1].x-a[i].x)))
                        bRet = !a[i+1].x-a[i].x;
        }

        return bRet;
}