当判定两条线段相交后，就可以进行交点的求解了。当然，求交点可以用平面几何方法，列点斜式方程来完成。但这样作会难以处理斜率为0的特殊情况，且运算中会出现多次除法，很难保证精度。这里将使用向量法求解。
设交点为(x0,y0)，则下列方程组必然成立：
x0-x1=k1(x2-x1)
y0-y1=k1(y2-y1)
x0-x3=k2(x4-x3)
y0-y3=k2(y4-y3)
其中k1和k2为任意不为0的常数（若为0，则说明有重合的端点，这种情况在上面已经被排除了）。1式与2式联系，3式与4式联立，消去k1和k2可得：
x0(y2-y1)-x1(y2-y1)=y0(x2-x1)-y1(x2-x1)
x0(y4-y3)-x3(y4-y3)=y0(x4-x3)-y3(x4-x3)
将含有未知数x0和y0的项移到左边，常数项移动到右边，得：
(y2-y1)x0+(x1-x2)y0=(y2-y1)x1+(x1-x2)y1
(y4-y3)x0+(x3-x4)y0=(y4-y3)x3+(x3-x4)y3
设两个常数项分别为b1和b2：
b1=(y2-y1)x1+(x1-x2)y1
b2=(y4-y3)x3+(x3-x4)y3
系数行列式为D，用b1和b2替换x0的系数所得系数行列式为D1，替换y0的系数所得系数行列式为D2，则有：
|D|=(x2-x1)(y4-y3)-(x4-x3)(y2-y1)
|D1|=b2(x2-x1)-b1(x4-x3)
|D2|=b2(y2-y1)-b1(y4-y3)
由此，可求得交点坐标为：
x0=|D1|/|D|,y0=|D2|/|D|
解毕。
C++/STL实现
#include <iostream>
#include <cmath>
using namespace std;
struct POINTF {float x; float y;};
bool Equal(float f1, float f2) {
return (abs(f1 - f2) < 1e-4f);
}
//判断两点是否相等
bool operator==(const POINTF &p1, const POINTF &p2) {
return (Equal(p1.x, p2.x) && Equal(p1.y, p2.y));
}
//比较两点坐标大小，先比较x坐标，若相同则比较y坐标
bool operator>(const POINTF &p1, const POINTF &p2) {
return (p1.x > p2.x || (Equal(p1.x, p2.x) && p1.y > p2.y));
}
//计算两向量外积
float operator^(const POINTF &p1, const POINTF &p2) {
return (p1.x * p2.y - p1.y * p2.x);
}
//判定两线段位置关系，并求出交点(如果存在)。返回值列举如下：
//[有重合] 完全重合(6)，1个端点重合且共线(5)，部分重合(4)
//[无重合] 两端点相交(3)，交于线上(2)，正交(1)，无交(0)，参数错误(-1)
int Intersection(POINTF p1, POINTF p2, POINTF p3, POINTF p4, POINTF &Int) {
//保证参数p1!=p2，p3!=p4
if (p1 == p2 || p3 == p4) {
return -1; //返回-1代表至少有一条线段首尾重合，不能构成线段
}
//为方便运算，保证各线段的起点在前，终点在后。
if (p1 > p2) {
swap(p1, p2);
}
if (p3 > p4) {
swap(p3, p4);
}
//判定两线段是否完全重合
if (p1 == p3 && p2 == p4) {
return 6;
}
//求出两线段构成的向量
POINTF v1 = {p2.x - p1.x, p2.y - p1.y}, v2 = {p4.x - p3.x, p4.y - p3.y};
//求两向量外积，平行时外积为0
float Corss = v1 ^ v2;
//如果起点重合
if (p1 == p3) {
Int = p1;
//起点重合且共线(平行)返回5；不平行则交于端点，返回3
return (Equal(Corss, 0) ? 5 : 3);
}
//如果终点重合
if (p2 == p4) {
Int = p2;
//终点重合且共线(平行)返回5；不平行则交于端点，返回3
return (Equal(Corss, 0) ? 5 : 3);
}
//如果两线端首尾相连
if (p1 == p4) {
Int = p1;
return 3;
}
if (p2 == p3) {
Int = p2;
return 3;
}//经过以上判断，首尾点相重的情况都被排除了
//将线段按起点坐标排序。若线段1的起点较大，则将两线段交换
if (p1 > p3) {
swap(p1, p3);
swap(p2, p4);
//更新原先计算的向量及其外积
swap(v1, v2);
Corss = v1 ^ v2;
}
//处理两线段平行的情况
if (Equal(Corss, 0)) {
//做向量v1(p1, p2)和vs(p1,p3)的外积，判定是否共线
POINTF vs = {p3.x - p1.x, p3.y - p1.y};
//外积为0则两平行线段共线，下面判定是否有重合部分
if (Equal(v1 ^ vs, 0)) {
//前一条线的终点大于后一条线的起点，则判定存在重合
if (p2 > p3) {
Int = p3;
return 4; //返回值4代表线段部分重合
}
}//若三点不共线，则这两条平行线段必不共线。
//不共线或共线但无重合的平行线均无交点
return 0;
} //以下为不平行的情况，先进行快速排斥试验
//x坐标已有序，可直接比较。y坐标要先求两线段的最大和最小值
float ymax1 = p1.y, ymin1 = p2.y, ymax2 = p3.y, ymin2 = p4.y;
if (ymax1 < ymin1) {
swap(ymax1, ymin1);
}
if (ymax2 < ymin2) {
swap(ymax2, ymin2);
}
//如果以两线段为对角线的矩形不相交，则无交点
if (p1.x > p4.x || p2.x < p3.x || ymax1 < ymin2 || ymin1 > ymax2) {
return 0;
}//下面进行跨立试验
POINTF vs1 = {p1.x - p3.x, p1.y - p3.y}, vs2 = {p2.x - p3.x, p2.y - p3.y};
POINTF vt1 = {p3.x - p1.x, p3.y - p1.y}, vt2 = {p4.x - p1.x, p4.y - p1.y};
float s1v2, s2v2, t1v1, t2v1;
//根据外积结果判定否交于线上
if (Equal(s1v2 = vs1 ^ v2, 0) && p4 > p1 && p1 > p3) {
Int = p1;
return 2;
}
if (Equal(s2v2 = vs2 ^ v2, 0) && p4 > p2 && p2 > p3) {
Int = p2;
return 2;
}
if (Equal(t1v1 = vt1 ^ v1, 0) && p2 > p3 && p3 > p1) {
Int = p3;
return 2;
}
if (Equal(t2v1 = vt2 ^ v1, 0) && p2 > p4 && p4 > p1) {
Int = p4;
return 2;
} //未交于线上，则判定是否相交
if(s1v2 * s2v2 > 0 || t1v1 * t2v1 > 0) {
return 0;
} //以下为相交的情况，算法详见文档
//计算二阶行列式的两个常数项
float ConA = p1.x * v1.y - p1.y * v1.x;
float ConB = p3.x * v2.y - p3.y * v2.x;
//计算行列式D1和D2的值，除以系数行列式的值，得到交点坐标
Int.x = (ConB * v1.x - ConA * v2.x) / Corss;
Int.y = (ConB * v1.y - ConA * v2.y) / Corss;
//正交返回1
return 1;
}
//主函数
int main(void) {
//随机生成100个测试数据
for (int i = 0; i < 100; ++i) {
POINTF p1, p2, p3, p4, Int;
p1.x = (float)(rand() % 10); p1.y = (float)(rand() % 10);
p2.x = (float)(rand() % 10); p2.y = (float)(rand() % 10);
p3.x = (float)(rand() % 10); p3.y = (float)(rand() % 10);
p4.x = (float)(rand() % 10); p4.y = (float)(rand() % 10);
int nr = Intersection(p1, p2, p3, p4, Int);
cout << "[(";
cout << (int)p1.x << ',' << (int)p1.y << "),(";
cout << (int)p2.x << ',' << (int)p2.y << ")]--[(";
cout << (int)p3.x << ',' << (int)p3.y << "),(";
cout << (int)p4.x << ',' << (int)p4.y << ")]: ";
cout << nr;
if (nr > 0) {
cout << '(' << Int.x << ',' << Int.y << ')';
}
cout << endl;
}
return 0;
}
