算法一
#include<stdio.h> #include<stdlib.h> #include<assert.h>
struct POINT { int x; int y; };
bool IsLineSegmentCross(POINT pFirst1, POINT pFirst2, POINT pSecond1, POINT pSecond2)
{
//每个线段的两点都在另一个线段的左右不同侧，则能断定线段相交
//公式对于向量(x1,y1)->(x2,y2),判断点(x3,y3)在向量的左边,右边,还是线上.
//p=x1(y3-y2)+x2(y1-y3)+x3(y2-y1).p<0 左侧, p=0 线上, p>0 右侧
long Linep1,Linep2; //判断pSecond1和pSecond2是否在pFirst1->pFirst2两侧
Linep1 = pFirst1.x * (pSecond1.y - pFirst2.y) + pFirst2.x * (pFirst1.y - pSecond1.y) + pSecond1.x * (pFirst2.y -pFirst1.y); Linep2 = pFirst1.x * (pSecond2.y - pFirst2.y) + pFirst2.x * (pFirst1.y - pSecond2.y) + pSecond2.x * (pFirst2.y - pFirst1.y); if ( ((Linep1 ^ Linep2) >= 0 ) && !(Linep1==0 && Linep2==0))//符号位异或为0:pSecond1和pSecond2在pFirst1->pFirst2同侧
{ return false; } //判断pFirst1和pFirst2是否在pSecond1->pSecond2两侧
Linep1 = pSecond1.x * (pFirst1.y - pSecond2.y) +pSecond2.x * (pSecond1.y - pFirst1.y) + pFirst1.x * (pSecond2.y -pSecond1.y); Linep2 = pSecond1.x * (pFirst2.y - pSecond2.y) + pSecond2.x * (pSecond1.y - pFirst2.y) + pFirst2.x * (pSecond2.y - pSecond1.y); if ( ((Linep1 ^ Linep2) >= 0 ) && !(Linep1==0 && Linep2==0))//符号位异或为0:pFirst1和pFirst2在pSecond1->pSecond2同侧
{ return false; } //否则判为相交 return true; } POINT GetCrossPoint(POINT p1, POINT p2, POINT q1, POINT q2)
{ //必须相交求出的才是线段的交点，但是下面的程序段是通用的assert(IsLineSegmentCross(p1,p2,q1,q2)); POINT crossPoint; long tempLeft,tempRight; //求x坐标 tempLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
tempRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) - p1.x * (p2.y - p1.y) * (q2.x - q1.x);
crossPoint.x =(int)( (double)tempRight / (double)tempLeft );
//求y坐标 tempLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
tempRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x- p2.x) * (q2.y - q1.y) * (p1.y - p2.y) - q2.y * (q1.x - q2.x) * (p2.y - p1.y);
crossPoint.y =(int)( (double)tempRight / (double)tempLeft );
return crossPoint; } int main(void) { POINT pointA,pointB,pointC,pointD; POINT pointCross; bool bCross(false); pointA.x = 400;pointA.y=440; pointB.x = 300;pointB.y = 440; pointC.x = 350;pointC.y = 500; pointD.x = 350;pointD.y = 400; bCross = IsLineSegmentCross(pointA,pointB,pointC,pointD); if (bCross) {
pointCross = GetCrossPoint(pointA,pointB,pointC,pointD); printf("交点坐标x=%d,y=%d\n",pointCross.x,pointCross.y); } else {
printf("They are not crossed!"); } return 0; }
算法二
定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：
|x1 x2 x3|
S(P1,P2,P3) = |y1 y2 y3| = (x1-x3)*(y2-y3) - (y1-y3)(x2-x3)
|1 1 1|
已知一条线段的两个端点为A(x1,y1),B(x2,y2),另一条线段的两个端点为C(x3,y3),D(x4,y4),要判断AB与CD是否有交点，若有求出.
首先判断d = (y2-y1)(x4-x3)-(y4-y3)(x2-x1)，
若d=0，则直线AB与CD平行或重合，
若d!=0，则直线AB与CD有交点，设交点为E(x0,y0)：
则有:CE/ED = S(A,C,B) / S(A,B,D)
所以:CE/CD = S(A,C,B) / (S(A,C,B) + S(A,B,D))
故 x0 = C.x + (D.x - C.x) * S(A,C,B) / (S(A,C,B) + S(A,B,D));
y0 = C.y + (D.y - C.y) * S(A,C,B) / (S(A,C,B) + S(A,B,D));
也可以直接求
x0 = [(x2-x1)*(x4-x3)*(y3-y1)+(y2-y1)*(x4-x3)*x1-(y4-y3)*(x2-x1)*x3]/d
y0 = [(y2-y1)*(y4-y3)*(x3-x1)+(x2-x1)*(y4-y3)*y1-(x4-x3)*(y2-y1)*y3]/(-d)
求出交点后在判断交点是否在线段上，即判断以下的式子：
(x0-x1)*(x0-x2) <=0
(x0-x3)*(x0-x4) <=0
(y0-y1)*(y0-y2) <=0
(y0-y3)*(y0-y4) <=0
只有上面的四个式子都成立才可判定(x0,y0)是线段AB与CD的交点，否则两线段无交点
算法三
//求两个点的直线方程
LINE makeline(POINT p1,POINT p2) {
LINE tl;
int sign = 1;
tl.a=p2.y-p1.y;
if (tl.a<0) {
sign = -1;
tl.a=sign*tl.a;
}
tl.b=sign*(p1.x-p2.x);
tl.c=sign*(p1.y*p2.x-p1.x*p2.y);
return tl;
}
// 如果两条直线 l1(a1*x+b1*y+c1 = 0), l2(a2*x+b2*y+c2 = 0)相交，返回true，且返回交点p
bool lineintersect(LINE l1,LINE l2,POINT &p) {// 是 L1，L2
double d=l1.a*l2.b-l2.a*l1.b;
if (abs(d)<EP) return false;// 不相交
p.x = (l2.c*l1.b-l1.c*l2.b)/d;
p.y = (l2.a*l1.c-l1.a*l2.c)/d;
return true;
}
//计算叉积
double multiply(POINT sp,POINT ep,POINT op) {
return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));
}
bool online(LINEl,POINT p)
{
return((multiply(l.b,p,l.a)==0)&&(((p.x-l.a.x)*(p.x-l.b.x)<=0)&&((p.y-l.a.y)*(p.y-l.b.y)<=0)));
}