判断线段是否相交.cpp

数值分析中常用的几种算法的实现

//判断线段是否相交
struct pp
{
	double x;
	double y;
}point[2000];
bool inter(pp s1,pp e1,pp s2,pp e2)
{
	double a1,a2,b1,b2,c1,c2,d1,d2;
	a1=e1.x-s1.x;
	a2=e1.y-s1.y;
	b1=s2.x-e2.x;
	b2=s2.y-e2.y;
	c1=s2.x-s1.x;
	c2=s2.y-s1.y;
	if(a1*b2==a2*b1)
		return false;
	d1=(c1*b2-c2*b1)/(a1*b2-a2*b1);
	d2=(c1*a2-c2*a1)/(b1*a2-b2*a1);
	if(d1>=0&&d1<=1&&d2>=0&&d2<=1)
		return true;
	return false;
}