射线法
射线法,由基准点水平向右生成射线Y,如果Y与多边形的交点数为偶数,则在外部,为奇数则在图内部,特殊情景另外考虑
hdu1756-射线法模板:
struct Point {
double x, y;
Point(double x=0,double y=0):x(x),y(y){}
//向量+
Point operator +(const Point& b) const {
return Point(x + b.x, y + b.y);
}
//向量-
Point operator -(const Point& b)const {
return Point(x - b.x, y - b.y);
}
//点积
double operator *(const Point& b)const {
return x*b.x + y*b.y;
}
//叉积
//P^Q>0,P在Q的顺时针方向;<0,P在Q的逆时针方向;=0,P,Q共线,可能正向可能反向
double operator ^(const Point& b)const {
return x*b.y - b.x*y;
}
};
float eps = 1e-6;
int dcmp(double x) {
if (fabs(x) < eps)
return 0;
else
return x < 0 ? -1 : 1;
}
bool OnSegment(Point& P1, Point& P2,Point& Q) {//判断点Q是否在P1和P2的线段上
return dcmp((P1 - Q) ^ (P2 - Q)) == 0 && dcmp((P1 - Q) * (P2 - Q)) <= 0;//前一个判断点Q在P1P2直线上 后一个判断在P1P2范围上
}
bool InPolygon(Point& P,vector<Point>& v) {//射线法
bool flag = false;
Point P1, P2;
int n = v.size();
for (int i = 0, j = n - 1; i < n; j = i++) {
P1 = v[i];
P2 = v[j];
if (OnSegment(P1, P2, P))
return true;
//前一个判断min(P1.y,P2.y)<P.y<=max(P1.y,P2.y)
//后一个判断被测点 在 射线与边交点 的左边
if ((dcmp(P1.y - P.y) > 0 != dcmp(P2.y - P.y) > 0) && dcmp(P.x - (P.y - P1.y)*(P1.x - P2.x) / (P1.y - P2.y) - P1.x) < 0)
flag = !flag;
}
return flag;
}