判断点在多边形内部

0. 介绍

网上资料很多，只简单介绍下，方便自己今后的理解。

1. 射线法

从该点引一条射线出来，如果和多边形有偶数个交点，则点在多边形外部。

因为有入必有出，所以从外部引进来的射线一定是交多边形偶数个点。

如图

这种方法唯一注意点是处理，引出的这条射线包括了多边形的边或者端点。

对此为了保证不重复，我们忽略在该射线上的边，和终点在该射线上的点。

实现

#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1typedef struct {double x,y;
} Point;int InsidePolygon(Point *polygon,int N,Point p)
{int counter = 0;int i;double xinters;Point p1,p2;p1 = polygon[0];for (i=1;i<=N;i++) {p2 = polygon[i % N];if (p.y > MIN(p1.y,p2.y)) // 确保了点在多边形端点上，点的相邻边只被计算了一次。{if (p.y <= MAX(p1.y,p2.y)) {if (p.x <= MAX(p1.x,p2.x)) {// 为使得水平射线与边相交的条件 // y_0 < y <= y_1// min(x_0,x_1) < xif (p1.y != p2.y) {xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;// 判断点是否在这条边的左侧if (p1.x == p2.x || p.x <= xinters)counter++;}}}}p1 = p2;}if (counter % 2 == 0)return(OUTSIDE);elsereturn(INSIDE);
}

判断点在边的左侧的示意图

2. 内角和

当点在多边形内时，内角和为$2\pi$。

实现参考

typedef struct {int h,v;
} Point;int InsidePolygon(Point *polygon,int n,Point p)
{int i;double angle=0;Point p1,p2;for (i=0;i<n;i++) {p1.h = polygon[i].h - p.h;p1.v = polygon[i].v - p.v;p2.h = polygon[(i+1)%n].h - p.h;p2.v = polygon[(i+1)%n].v - p.v;angle += Angle2D(p1.h,p1.v,p2.h,p2.v);}if (ABS(angle) < PI)return(FALSE);elsereturn(TRUE);
}/*Return the angle between two vectors on a planeThe angle is from vector 1 to vector 2, positive anticlockwiseThe result is between -pi -> pi
*/
double Angle2D(double x1, double y1, double x2, double y2)
{double dtheta,theta1,theta2;theta1 = atan2(y1,x1);theta2 = atan2(y2,x2);dtheta = theta2 - theta1;while (dtheta > PI)dtheta -= TWOPI;while (dtheta < -PI)dtheta += TWOPI;return(dtheta);
}

3. 同侧法

当多边形为凸多边形时，我们可以判断该点是否在各个边形成的直线的一侧;

来判断点是否在多边形的内部。实际上就是一个线性规划问题。

凹多边形的凹角附近不满足该条件。

只需要判断

$$(x-x_0)(y_1-y_0)+(y-y_0)(x_0-x_1)$$

的值即可判断，点在多边形边的哪一侧。

给定两个点$P_0(x_0,y_0),P_1(x_1,y_1)$，直线一般方程$Ax+By+c=0$推导。

1. $x_0=x_1$
   $x-x_0=0$
2. $x_0\ne x_1$
   $$\begin{gathered} 直线点斜式方程y=kx+b \\ k=\frac{y_1-y_0}{x_1-x_0} \\ 带入P_0,P_1 \\ b=y_0-k{x}_0 \\ b=y_1-k{x}_1 \\ 2b=(y_0+y_1)-k(x_0+x_1) \\ 带入k，化简得到 \\ b=\frac{x_1{y}_0-x_0{y}_1}{x_1-x_0} \\ 化为一般式子得到 \\ (y_1-y_0)x+(x_0-x_1)y+x_1{y}_0-x_0{y}_1=0 \\ 更加统一的形式 \\ (y_1-y_0)(x-x_0)+x_0{y}_1-x_0{y}_0+ \\ (x_0-x_1)(y-y_0)+x_0{y}_0-x_1{y}_0+x_1{y}_0-x_0{y}_1=0 \\ 合并化简得到 \\ (x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)=0 \end{gathered}$$
3. 将$x_0=x_1$代入$(x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)=0$;
   得到$x-x_0=0$

归纳可得直线一般式方程
$$\begin{gathered} (y_1-y_0)x+(x_0-x_1)y+x_1{y}_0-x_0{y}_1=0 \\ 或 \\ (x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)=0 \end{gathered}$$

4. 原文

eecs