算法一
#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))); }