两条线段的交点的计算
问题
已知线段P1P2和Q1Q2，判断它们是否有交点，若有，求出交点。
1.判断线段是否相交
如图，判断线段是否相交，可以通过一系列实验来进行。
快速排斥实验
若以P1P2和Q1Q2为对角线的矩形不相交，则P1P2肯定不相交
只有当
min(p1.x,p2.x) <= max(q1.x,q2.x)
min(q1.x,q2.x) <= max(p1.x,p2.x)
min(p1.y,p2.y) <= max(q1.y,q2.y)
min(q1.y,q2.y) <= max(p1.y,p2.y)
四个式子都满足时，两线段才有可能相交，否则比不相交。此即为快速排斥实验。
跨立实验
根据上图可知，即使通过了快速排斥实验，两直线也不一定相交，因此，我们需要进一步通过所谓的跨立实验进行判断。
这部分内容可以直接参见链接
2.线段交点的计算
设
P
1
(
x
1
,
y
1
)
,
P
2
(
x
2
,
y
2
)
,
Q
1
(
x
3
,
y
3
)
,
Q
2
(
x
4
,
y
4
)
P_1(x_1,y_1),P_2(x_2,y_2),Q_1(x_3,y_3),Q_2(x_4,y_4)
P1(x1,y1),P2(x2,y2),Q1(x3,y3),Q2(x4,y4)，则
P
1
P
2
P_1P_2
P1P2和
Q
1
Q
2
Q_1Q_2
Q1Q2的交点计算如下：
之所以觉得跨立实验意义不大，是因为跨立实验的计算量和直接计算交点的计算量没有很大的差别，我们可以直接通过计算直线交点，然后判断交点是否位于线段上来进行，判断的准则如下:
m
a
x
(
x
1
,
x
2
)
≥
x
o
≥
m
i
n
(
x
1
,
x
2
)
max(x_1,x_2)\ge x_o\ge min(x_1,x_2)
max(x1,x2)≥xo≥min(x1,x2)
m
a
x
(
x
3
,
x
4
)
≥
x
o
≥
m
i
n
(
x
3
,
x
4
)
max(x_3,x_4)\ge x_o\ge min(x_3,x_4)
max(x3,x4)≥xo≥min(x3,x4)