Question

c++ 怎么判断1个点在一个不规则的四边形内

已知一个不规则的四边形的四个点(x1,y1),(x2,y2),(x3,y3),(x4,y4).和任意一点(x,y).怎么判断(x,y)在这个四边形内?

Answer 1

C++
同事在VS 2005里面写的

在多边形内包含线上 返回true
不在 返回false

bool InPolygon(List<PointF>^ pointarray,PointF point)//pointarray 点的集合（可以是任意多边形） point 要判断的点
{
int n = pointarray->Count;//确定点的个数
int count = 0;
LineSegment line;
line.pt1=point;
line.pt2.Y=point.Y;
line.pt2.X=-INFINITY;
for(int i=0;i<n;i++)
{
LineSegment side;
side.pt1=pointarray[i];
side.pt2=pointarray[(i+1)%n];
if(Isonline(point,side))
{
return 1;
}
if(fabs(side.pt1.Y-side.pt2.Y)<ESP)
{
continue;
}
if(Isonline(side.pt1,line))
{
if(side.pt1.Y>side.pt2.Y) count++;
}
else if(Isonline(side.pt2,line))
{
if(side.pt2.Y>side.pt1.Y) count++;
}
else if(Intersect(line,side))
{
count++;
}
}
if(count%2==1){return 2;}
else {return 0;}

}

struct LineSegment
{
PointF pt1,pt2;
};//结构

double Multiply(PointF p1,PointF p2, PointF p0)//向量乘法(忘记是差乘还是点乘)
{
return ((p1.X-p0.X)*(p2.Y-p0.Y)-(p2.X-p0.X)*(p1.Y-p0.Y));
}

bool Isonline(PointF point,LineSegment line)//判断是否在线上
{
return( (fabs(Multiply(line.pt1,line.pt2,point))<ESP)&&
((point.X-line.pt1.X)*(point.X-line.pt2.X)<=0)&&
((point.Y-line.pt1.Y)*(point.Y-line.pt2.Y)<=0)) ;
}
bool Intersect(LineSegment L1,LineSegment L2) //判断两线是否相交
{
return(
(Math::Max(L1.pt1.X,L1.pt2.X)>=Math::Min(L2.pt1.X,L2.pt2.X))&&
(Math::Max(L2.pt1.X,L2.pt2.X)>=Math::Min(L1.pt1.X,L1.pt2.X))&&
(Math::Max(L1.pt1.Y,L1.pt2.Y)>=Math::Min(L2.pt1.Y,L2.pt2.Y))&&
(Math::Max(L2.pt1.Y,L2.pt2.Y)>=Math::Min(L1.pt1.Y,L1.pt2.Y))&&
(Multiply(L2.pt1,L1.pt2,L1.pt1)*Multiply(L1.pt2,L2.pt2,L1.pt1)>=0)&&
(Multiply(L1.pt1,L2.pt2,L2.pt1)*Multiply(L2.pt2,L1.pt2,L2.pt1)>=0)
);
}