求線段交點

#include <stdio.h>

typedef struct Point
{
double x;
double y;
}Point;

typedef struct Vector
{
struct Point begin;
struct Point end;
}Vector;

double VectorMul(Vector AB,Vector CD)/*求向量的叉积（以向量作参数）*/
{
return ((AB.end.x-AB.begin.x)*(CD.end.y-CD.begin.y) - (AB.end.y-AB.begin.y)*(CD.end.x-CD.begin.x));
}

double mul(Point A,Point B,Point C)/*向量叉积（以点做参数):求AB与AC的叉积*/
{
Point AB,AC;
AB.x=B.x-A.x;
AB.y=B.y-A.y;
AC.x=C.x-A.x;
AC.y=C.y-A.y;
return (AB.x*AC.y - AB.y * AC.x);
}

double Max(double a,double b)
{
return a > b ? a : b ;
}

double Min(double a,double b)
{
return a < b ? a : b ;
}

int Across(Vector AB,Vector CD)
/*判断线段是否相交（快速排斥试验和跨立试验）*/
{
if( /*X方向的排斥试验*/
( Max(AB.begin.x,AB.end.x) >= Min(CD.begin.x,CD.end.x) )
&&( Max(CD.begin.x,CD.end.x) >= Min(AB.begin.x,AB.end.x) )
/*Y方向的排斥试验*/
&&( Max(AB.begin.y,AB.end.y) >= Min(CD.begin.y,CD.end.y) )
&&( Max(CD.begin.y,CD.end.y) >= Min(AB.begin.y,AB.end.y) )
&&( mul(CD.begin,AB.begin,CD.end) * mul(CD.begin,AB.end,CD.end) <= 0 )/*A、B跨立CD的测试*/
&&( mul(AB.begin,CD.begin,AB.end) * mul(AB.begin,CD.end,AB.end) <= 0 )/*C、D跨立AB的测试*/
)
{
return 1;
}
return 0;
}

Point CrossPoint(Vector AB,Vector CD)
/*
求AB与CD的交点，前提：AB与CD相交
*/
{
Vector AD,AC;
Point result;
double k;
AD.begin = AB.begin;
AD.end = CD.end;
AC.begin = AB.begin;
AC.end = CD.begin;
k=(VectorMul(AB,AD))/(VectorMul(AB,AC) * 1.0);

k=k>0?k:(-k);/*这句话很重要*/

result.x = ( k * CD.begin.x + CD.end.x )/((1+k)*1.0) ;
result.y = ( k * CD.begin.y + CD.end.y )/((1+k)*1.0) ;
return result;
}

//以下是测试代码，仅供参考
int main()
{
Vector AB,CD;
Point result;

printf("Please input A:\t");
scanf("%lf%lf",&AB.begin.x,&AB.begin.y);

printf("Please input B:\t");
scanf("%lf%lf",&AB.end.x,&AB.end.y);

printf("Please input C:\t");
scanf("%lf%lf",&CD.begin.x,&CD.begin.y);

printf("Please input D:\t");
scanf("%lf%lf",&CD.end.x,&CD.end.y);

if( Across(AB,CD) )
{
result = CrossPoint(AB,CD);
printf("The Cross Point:\t");
printf("(%.2lf,%.2lf)\n",result.x,result.y);
}
else
{
printf("The segments have no cross point!\n ");
}
getchar();
getchar();
return 0;
}