判断两条线段是否相交以及点是否在四边形内的C++算法
程序员文章站
2022-04-01 18:41:52
...
1.判断两条线段是否相交
#include <iostream>
using namespace std;
struct Point
{
double x, y;
};
// 判断两条直线是否相交
double determinant(double v1, double v2, double v3, double v4) // 行列式
{
return (v1*v4 - v2 * v3);
}
bool intersect(Point aa, Point bb, Point cc, Point dd)
{
double delta = determinant(bb.x - aa.x, cc.x - dd.x, bb.y - aa.y, cc.y - dd.y);
if (delta <= (1e-6) && delta >= -(1e-6)) // delta=0,表示两线段重合或平行
{
return false;
}
double namenda = determinant(cc.x - aa.x, cc.x - dd.x, cc.y - aa.y, cc.y - dd.y) / delta;
if (namenda > 1 || namenda < 0)
{
return false;
}
double miu = determinant(bb.x - aa.x, cc.x - aa.x, bb.y - aa.y, cc.y - aa.y) / delta;
if (miu > 1 || miu < 0)
{
return false;
}
return true;
}
int main()
{
Point a1, a2, b1, b2;
// 分别指定两条线段的端点
a1.x = 1;
a1.y = 1;
a2.x = 2;
a2.y = 2;
b1.x = 2;
b1.y = 1;
b2.x = 3;
b2.y = 1;
if (intersect(a1, a2, b1, b2))
cout << "相交" << endl;
else
cout << "不相交" << endl;
return 0;
}
2.判断点是否在一个四边形内(凸四边形)
逻辑简单解释就是循环的以每条边为基准判断点是否始终在同一侧(四条边的选取是从某一个点出发顺时针或者逆时针一圈)
#include <iostream>
#include <vector>
using namespace std;
struct Point
{
double x, y;
};
struct LinePara
{
float a;
float b;
float c;//变量满足等式ax + by + c = 0
};
// 获取直线参数
void getLinePara(Point p1, Point p2, LinePara & LP)
{
LP.a = p2.y - p1.y;
LP.b = p1.x - p2.x;
LP.c = p1.y * (p2.x - p1.x) - p1.x * (p2.y - p1.y);
}
float eval(LinePara LP, Point p)
{
return (LP.a * p.x + LP.b * p.y + LP.c);
}
bool PointInQuad(vector<struct Point> quad, Point srcpt)
{
if (quad.size() < 4)
return false;
Point p_a, p_b, p_c, p_d;
p_a = quad[0];
p_b = quad[1];
p_c = quad[2];
p_d = quad[3];
LinePara line_a2b;
getLinePara(p_a, p_b, line_a2b);
LinePara line_b2c;
getLinePara(p_b, p_c, line_b2c);
LinePara line_c2d;
getLinePara(p_c, p_d, line_c2d);
LinePara line_d2a;
getLinePara(p_d, p_a, line_d2a);
float df1, df2, df3, df4;
df1 = eval(line_a2b, srcpt);
df2 = eval(line_b2c, srcpt);
df3 = eval(line_c2d, srcpt);
df4 = eval(line_d2a, srcpt);
if ((df1 > 0 && df2 > 0 && df3 > 0 && df4 > 0) || (df1 < 0 && df2 < 0 && df3 < 0 && df4 < 0)) // 在同侧
return true;
return false;
}
int main()
{
vector<struct Point> quad;
Point testpt1, testpt2;
testpt1.x = 0, testpt1.y = 0;
testpt2.x = 2, testpt2.y = 2;
Point a1, a2, b1, b2;
// 四边形坐标的设定需要按照顺时针或者逆时针,保证相邻的两个点相连确实是四边形的某一条边
a1.x = 0;
a1.y = 2;
a2.x = 2;
a2.y = 4;
b1.x = 4;
b1.y = 2;
b2.x = 2;
b2.y = 0;
if (PointInQuad(quad, testpt1))
cout << "在四边形内" << endl;
else
cout << "不在四边形内" << endl;
if (PointInQuad(quad, testpt2))
cout << "在四边形内" << endl;
else
cout << "不在四边形内" << endl;
return 0;
}
上一篇: 点A围绕点B 旋转 A度