对于点A是否在多边形P内的判定, 一般有两种方法:射线法和转角法。 这里介绍一下射线法。
射线法:从点A出发作一条射线,计算这条射线与多边形P的边的交点数量N,如果N为奇数,则点A在多边形P内,否则在P外部。
射线法中这条射线是任意方向的,一般在编程的时候选取从A出发往X坐标轴正方向的一条射线X。
(红心点为A,右边有3个点,说明在多边形内部)
射线法的原理:直线不可能从内部再次进入多边形,或从外部再次穿出多边形,即连续两次穿越边界的情况必然成对(大概就是这个意思,不是严格证明)。
射线法具体逻辑见源代码,涉及到几个子问题,大概说一下。
子问题1:判定点A在线段P1P2上(特殊处理点在边上的情况使用)。
两个向量a和b的叉积写作a^b = |a| |b|sinα (α为a,b向量之间的夹角)
叉积的几何意义:
对于向量AP1与向量AP2,如果叉积为0,说明夹角为0,也就是共线。
另外还要注意向量a、b的乘积a·b。
(向量的乘积)
乘积的几何意义:
a·b>0 方向基本相同,夹角在0°到90°之间
a·b=0 正交,相互垂直
a·b<0 方向基本相反,夹角在90°到180°之间
子问题2:判断点A在线段P1P2的左边。
对于线段P1P2的斜率k,如果P1A的斜率k'大于k,则A在线段P1P2的左边。
(P1A的斜率大于P1P2的斜率)
Problem Description
传说世上有一支丘比特的箭,凡是被这支箭射到的人,就会深深的爱上射箭的人。
世上无数人都曾经梦想得到这支箭。Lele当然也不例外。不过他想,在得到这支箭前,他总得先学会射箭。
日子一天天地过,Lele的箭术也越来越强,渐渐得,他不再满足于去射那圆形的靶子,他开始设计各种各样多边形的靶子。
不过,这样又出现了新的问题,由于长时间地练习射箭,Lele的视力已经高度近视,他现在甚至无法判断他的箭射到了靶子没有。所以他现在只能求助于聪明的Acmers,你能帮帮他嘛?
Input
本题目包含多组测试,请处理到文件结束。
在每组测试的第一行,包含一个正整数N(2<N<100),表示靶子的顶点数。
接着N行按顺时针方向给出这N个顶点的x和y坐标(0<x,y<1000)。
然后有一个正整数M,表示Lele射的箭的数目。
接下来M行分别给出Lele射的这些箭的X,Y坐标(0<X,Y<1000)。
Output
对于每枝箭,如果Lele射中了靶子,就在一行里面输出"Yes",否则输出"No"。
Sample Input
4
10 10
20 10
20 5
10 5
2
15 8
25 8
Sample Output
Yes
No
源代码:G++ 0ms
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-6;
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;
}
//叉积
double operator ^(const Point &b)const
{
return x * b.y - b.x * y;
}
};
static Point polygons[105];
//三态函数,判断两个double在eps精度下的大小关系
int dcmp(double x)
{
if (fabs(x) < eps) return 0;
else
return x < 0 ? -1 : 1;
}
//判断点Q是否在P1和P2的线段上
bool is_in_line(Point P1, Point P2, Point Q)
{
return dcmp((P1 - Q) ^ (P2 - Q)) == 0 && dcmp((P1 - Q) * (P2 - Q)) <= 0;
}
//判断点P在多边形内-射线法
bool is_in_polygon(Point P, int point_count)
{
bool flag = false;
for (int i = 1, j = point_count; i <= point_count; j = i++)
{
//多边形一条边的两个顶点
Point P1 = polygons[i];
Point P2 = polygons[j];
//点在多边形一条边上
if (is_in_line(P1, P2, P)) {
return true;
}
//在多边形里面
//以P点做一条水平向右的射线
//1、线段在点的上下,而不是一边
bool isUpDownLine = (dcmp(P1.y - P.y) > 0 != dcmp(P2.y - P.y) > 0);
if (isUpDownLine) {
//2、点在射线与线段交点的左边
//直线应该是y=kx+b吧
//假如当前点是坐标是x1,y1,那么y>kx+b就说明点在直线左边,反之在右边
/*
p.x < (p.y-p1.y)/k + p1.x
k*p.x < p.y-p1.y + k*p1.x
p.y-p1.y + k*(p1.x-p.x) > 0
p.y-p1.y > k*(p.x-p1.x)
对于如果向量P1P的斜率大于P1P2的斜率,则P在P1P2的左边
*/
bool isLeft = dcmp(P.x - (P.y - P1.y) * (P1.x - P2.x) / (P1.y - P2.y) - P1.x) < 0;
if (isLeft) {
flag = !flag;
}
}
}
return flag;
}
int main()
{
int case_count, point_count;
while (~scanf("%d", &point_count))
{
for (int i = 1; i <= point_count; i++) {
scanf("%lf %lf", &polygons[i].x, &polygons[i].y);
}
Point point;
scanf("%d", &case_count);
while (case_count--)
{
scanf("%lf %lf", &point.x, &point.y);
//判断是否在多边形里面
if (is_in_polygon(point, point_count)) {
printf("Yes\n");
}
else {
printf("No\n");
}
}
}
return 0;
}