欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

判断两条线段是否相交以及点是否在四边形内的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;
}