Question

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

已知一个不规则的四边形的四个点(x1,y1),(x2,y2),(x3,y3),(x4,y4).和任意一点(x,y).怎么判断(x,y)在这个四边形内?
急求只相对这个题目的算法,不要太笼统,只要能解决这道题就行.
2楼的回答不明白,两两直线的斜率必相等?怎么也相等不起来.能不能给个具体的例子看下?3楼算法有问题,不说别的,如果是个正方形或矩形,随便用几个点代进去,就不成立

Answer 1

四个点两两组成直线。
可得四个点的直线方程。
两点式直线方程：y-y1=[(y1-y2)/(x1-x2)]×(x-x1)

其中两两直线的斜率必相等，就是： (y1-y2)/(x1-x2) 部分相等。
将x带入四个方程解y'，那么y必在斜率相等的一对直线之间，就是y'<y<y"。
一共四条，两对直线。

如果不在，必然有y<y'<y"，在矩形上必然有某一组中y=y'，另一组满足y'<y<y"。（如果只是在延长线上，一组满足，另一组不满足）

对于平行四边形适用。
////////////////////////////////////////////////
#include <iostream>
using namespace std;
int main()
{
float *x=new float [4];//四个点的横坐标
float *y=new float [4];//四个点的纵坐标
float *ty=new float [4];//经计算后的y`值
float fx,fy;//目标点的坐标
float flag[2];//判断点与平行的一对直线的位置，两两平行，所以有两对。
int i;//循环用变量

cout<<"按任意时针方向顺序输入"<<endl;
for(i=0;i<=3;i++)//输入数据
{
cout<<"x"<<i+1<<"= ";
cin>>x[i];
cout<<"y"<<i+1<<"= ";
cin>>y[i];
cout<<endl;
}
cout<<"目标点:"<<endl;
cout<<"点x"<<"= ";
cin>>fx;
cout<<"点y"<<"= ";
cin>>fy;

float k[2]={0,0};//两对直线的斜率，因为两两平行相等，所以只有2个值
for (i=0;i<=1;i++)//当斜率存在的时候（直线垂直x轴时斜率不存在）计算斜率
{
if(x[i]!=x[i+1])
{
k[i]=(y[i]-y[i+1])/(x[i]-x[i+1]);//计算公式是(y1-y2)/(x1-x2),初中几何
}
}

for(i=0;i<=3;i++)//将目标点的x值带入四条直线方程，计算x位置的四条直线的y`值。
{
ty[i]=k[i%2]*(fx-x[i])+y[i];
}

for(i=0;i<=1;i++)//判断位置，
{
if(x[i]==x[i+1])//斜率不存在的时候，x应该在一对平行直线的x之间
{
flag[i]=(x[i]-fx)*(x[i+2]-fx);
//若在之间，则差异号，乘积为负；在一条直线上，则其中一个是0，乘积为0；则在一侧，不在其之间，则同号。
}
else//斜率存在时，y在一对平行的直线y`之间
{
flag[i]=(ty[i]-fy)*(ty[i+2]-fy);
//同上
}
}
if((flag[0]*flag[1])>0 && (flag[0]+flag[1])<0)//若都在之内
{
cout<<"在矩形内"<<endl;
}
else if((flag[0]*flag[1])==0 && (flag[0]+flag[1])<=0)//一个在线上，一个在之内
{
cout<<"在矩形上"<<endl;
}
else
{
cout<<"在矩形外"<<endl;
}
return 0;
}
/////////////////////////////////////////

！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
无敌了，我又想到一个超简单的办法，只对矩形有效。
如果在矩形外，那么矩形的相邻点与目标点形成的三角形中一定有钝角三角形。 而且一定有两个！那么关键的算法只要两行就解决了
/////////////////////////////////////////
#include <iostream>
#include "math.h"
using namespace std;
int main()
{
float *x=new float [4];//四个点的横坐标
float *y=new float [4];//四个点的纵坐标
float fx,fy;//目标点的坐标
int i;//循环用变量

for(i=0;i<=3;i++)//输入数据
{
cout<<"x"<<i+1<<"= ";
cin>>x[i];
cout<<"y"<<i+1<<"= ";
cin>>y[i];
cout<<endl;
}
cout<<"目标点:"<<endl;
cout<<"点x"<<"= ";
cin>>fx;
cout<<"点y"<<"= ";
cin>>fy;

for(i=0;i<=3;i++)
{
if( (pow((x[i]-x[(1+i)%4]),2) +pow((y[i]-y[(1+i)%4]),2) +pow((x[i]-fx),2) +pow((y[i]-fy),2) ) < (pow((fy-y[(1+i)%4]),2) +pow((fx-x[(1+i)%4]),2) )) //根据勾股定理判断是否为钝角三角形 。因为有两个，所以不用判断长短，只要找出一个就可以解决问题，而且矩形边一定是短边 ，pow是乘方函数。
{
break;
}
}
if(i==4)
{
cout<<"在矩形内"<<endl;
}
else
{
cout<<"在矩形外"<<endl;
}
return 0;
}

Answer 2

你好 我认为判断一个点是不是在一个不规则的多边形内，
可用面积相等法；
设此多边形的面积为S；
然后将该点与多边形的个定点连起来；
于是便将这个多边形分成了许多小三角形；
若这些小三角形的面积之和等于S；则说明该点在多边形里。

Answer 3

设该四边形四个点按顺时针排列
(x1,y1),(x2,y2),(x3,y3),(x4,y4)
平面上某点(x,y)
（atan2()计算的弧度在-PI ~ PI之间）
#include <stdio.h>
#include <string.h>
#include <math.h>

int main( )
{
double x1=142,y1=162;
double x2=248,y2=96;
double x3=298,y3=151;
double x4=221,y4=187;
double x=241,y=142;
double a[8] = {0};
a[0] = atan2((y-y1),(x-x1));
a[1] = atan2((y2-y1),(x2-x1));
a[2] = atan2((y-y2),(x-x2));
a[3] = atan2((y3-y2),(x3-x2));
a[4] = atan2((y-y3),(x-x3));
a[5] = atan2((y4-y3),(x4-x3));
a[6] = atan2((y-y4),(x-x4));
a[7] = atan2((y1-y4),(x1-x4));
int i = 0;
for(i = 0; i < 8; i++)
{
if(a[i]<0) a[i] = 2*3.1415926 + a[i];
}
if(a[0]>a[1]&&a[2]>a[3]&&a[4]>a[5]&&a[6]>a[7])
printf("在内部\n");
else
printf("在外部\n");
return 0;
}
你随便用windows画板画一个突四边形，把四个点坐标按顺时针记下来，再在平面上随便选一点(x,y)，试一下。

Answer 4

设定某个x值，在四边形内部则y必定会有一个范围。（需要考虑x值处于中间的两个点。同时还有直线的方程）

Answer 5

"这个是属于计算几何算法了，判别1个点是不是属于任意多边形，就要以这个点为横坐标，画一条横向射线，假如和多边形的交点个数为奇数则在多边形内，否则就在外，特殊情形：
1、当射线与其中一条边重合，那么边忽略不计；
2、当射线与其中一顶点相交（外凸），交点只可以计算1个；
3、当射线与其中一顶点相交（内凹），交点不应被计算；
下边为伪代码：
count
←
0;
以(x,y)为端点，作从右向左的射线L;
for
多边形的每条边s
do
if
(x,y)在边s上
then
return
true;
if
s不是水平的
then
if
s的1个端点在L上
if
该端点是s两端点中纵坐标较大的端点
then
count
←
count+1
else
if
s和L相交
then
count
←
count+1;
if
count
mod
2
=
1
then
return
true;
else
return
false;"