做软装在那些网站找家具,怎么用网络推广,宁波代理公司注册,如何设计一个网页自动运行0. 介绍
网上资料很多#xff0c;只简单介绍下#xff0c;方便自己今后的理解。
1. 射线法
从该点引一条射线出来#xff0c;如果和多边形有偶数个交点#xff0c;则点在多边形外部。
因为有入必有出#xff0c;所以从外部引进来的射线一定是交多边形偶数个点。
如图…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 (i1;iN;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 π 2 \pi 2π。
实现参考
typedef struct {int h,v;
} Point;int InsidePolygon(Point *polygon,int n,Point p)
{int i;double angle0;Point p1,p2;for (i0;in;i) {p1.h polygon[i].h - p.h;p1.v polygon[i].v - p.v;p2.h polygon[(i1)%n].h - p.h;p2.v polygon[(i1)%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 ) (x-x_0)(y_1-y_0)(y-y_0)(x_0-x_1) (x−x0)(y1−y0)(y−y0)(x0−x1)
的值即可判断点在多边形边的哪一侧。
给定两个点 P 0 ( x 0 , y 0 ) , P 1 ( x 1 , y 1 ) P_0(x_0,y_0),P_1(x_1,y_1) P0(x0,y0),P1(x1,y1)直线一般方程 A x B y c 0 AxByc0 AxByc0推导。 x 0 x 1 x_0x_1 x0x1 x − x 0 0 x-x_00 x−x00 x 0 ≠ x 1 x_0 \ne x_1 x0x1 直线点斜式方程 y k x b k y 1 − y 0 x 1 − x 0 带入 P 0 , P 1 b y 0 − k x 0 b y 1 − k x 1 2 b ( y 0 y 1 ) − k ( x 0 x 1 ) 带入 k 化简得到 b 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 直线点斜式方程ykxb\\ k\frac{y_1- y_0}{x_1-x_0}\\ 带入P_0,P_1\\ by_0-kx_0\\ by_1-kx_1\\ 2b(y_0y_1)-k(x_0x_1)\\ 带入k化简得到\\ b\frac{x_1y_0-x_0y_1}{x_1-x_0}\\ 化为一般式子得到\\ (y_1-y_0)x(x_0-x_1)yx_1y_0-x_0y_10\\ 更加统一的形式\\(y_1-y_0)(x-x_0)x_0y_1-x_0y_0\\(x_0-x_1)(y-y_0)x_0y_0-x_1y_0x_1y_0-x_0y_10\\ 合并化简得到\\ (x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)0 直线点斜式方程ykxbkx1−x0y1−y0带入P0,P1by0−kx0by1−kx12b(y0y1)−k(x0x1)带入k化简得到bx1−x0x1y0−x0y1化为一般式子得到(y1−y0)x(x0−x1)yx1y0−x0y10更加统一的形式(y1−y0)(x−x0)x0y1−x0y0(x0−x1)(y−y0)x0y0−x1y0x1y0−x0y10合并化简得到(x−x0)(y1−y0)−(y−y0)(x1−x0)0将 x 0 x 1 x_0x_1 x0x1代入 ( x − x 0 ) ( y 1 − y 0 ) − ( y − y 0 ) ( x 1 − x 0 ) 0 (x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)0 (x−x0)(y1−y0)−(y−y0)(x1−x0)0; 得到 x − x 0 0 x-x_00 x−x00
归纳可得直线一般式方程 ( 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 (y_1-y_0)x(x_0-x_1)yx_1y_0-x_0y_10\\ 或\\ (x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)0 (y1−y0)x(x0−x1)yx1y0−x0y10或(x−x0)(y1−y0)−(y−y0)(x1−x0)0
4. 原文
eecs
