判断两条线段是否相交以及点是否在四边形内的C++算法

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;
}