如何判断两条直线是否相交？
这很容易。平面直线，无非就是两种关系：相交 或 平行。因此，只需判断它们是否平行即可。而直线平行，等价于它们的斜率相等，只需分别计算出它们的斜率，即可做出判断。
但倘若我把“直线”换成“线段”呢——如何判断两条线段是否相交？
这就有些难度了。和 直线 不同，线段 是有固定长度的，即使它们所属的两条直线相交，这两条线段也不一定相交。
问题分析
对于“判断两条直线是否相交”这个问题，我们之所以能迅速而准确地进行判断，是因为“相交”与“不相交”这两个状态有着明显的不同点，即斜率是否相等。
那么现在，为了判断两条线段是否相交，我们也要找出“相交”与“不相交”这两个状态的不同点。
假设现在有两条线段 AB 和 CD，我们画出它们之间的三种关系：
其中，情况 1 为不相交，情况 2、3 为相交。
作出向量 AC、AD、BC、BD。
首先介绍一个概念： 向量有序对的旋转方向。这个概念指：对于共起点有序向量二元组(a, b)，其旋转方向为 使 a 能够旋转一个小于 180 度的角并与 b 重合的方向，简记为 direct(a, b)。若 a 和 b 反向共线，则旋转方向取任意值。
举个例子：图一中，direct(AC, AD) 为顺时针方向。
接下来我们要分析四个值：direct(AC, AD)、direct(BC, BD)、direct(CA, CB)、direct(DA, DB)。
对于图一，direct(AC, AD) 和 direct(BC, BD) 都为顺时针，direct(CA, CB) 为逆时针，direct(DA, DB) 为顺时针。
对于图二，direct(AC, AD) 为顺时针，direct(BC, BD) 为任意方向，direct(CA, CB) 为逆时针，direct(DA, DB) 为顺时针。
对于图三，direct(AC, AD)、direct(DA, DB) 为顺时针，direct(BC, BD)、direct(CA, CB) 为逆时针。
不难发现，两条线段相交的充要条件是：direct(AC, AD) != direct(BC, BD) 且 direct(CA, CB) != direct(DA, DB)。这便是“相交”与“不相交”这两个状态的不同点。
然而你可能会觉得：旋转方向这么一个虚无飘渺的东西，怎么用程序去描述啊？
再来看一幅图：
再来定义有向角：
有向角
不难看出，对于向量 a、b：
若 direct(a, b) 为逆时针，则 0 <=
若 direct(a, b) 为顺时针，则 180 <=
这样一来，我们可以将旋转方向的问题转化为 求有向角正弦值 的问题。而这个问题，是很容易的。
如上图，记
$_math_inline$OA=(x_1,y_1),OB=(x_2,y_2)$math_inline_$
$_math_inline$|OA|=r_1, |OB|=r_2$math_inline_$
则：
$_math_inline$sin()$math_inline_$
$_math_inline$=\sin\theta$math_inline_$
$_math_inline$=\sin(\alpha-\beta)$math_inline_$
$_math_inline$=\sin\alpha\cos\beta-\sin\beta\cos\alpha$math_inline_$
$_math_inline$=\frac{(\sin\alpha\cos\beta-\sin\beta\cos\alpha)r_1\cdot r_2}{r_1\cdot r_2}$math_inline_$
$_math_inline$=\frac{x_1 \cdot y_2-x_2 \cdot y_1}{r_1 \cdot r_2}$math_inline_$
而这里，我们要的只是 sin(
这个方法的数学背景是 叉乘，可以前往 Wikipedia 了解更多。
思路小结
由点 A，B，C，D 计算出向量 AC，AD，BC，BD
计算 sin(
实现
1# 点
2class Point(object):
3
4 def __init__(self, x, y):
5 self.x, self.y = x, y
6
7# 向量
8class Vector(object):
9
10 def __init__(self, start_point, end_point):
11 self.start, self.end = start_point, end_point
12 self.x = end_point.x - start_point.x
13 self.y = end_point.y - start_point.y
14
15
16ZERO = 1e-9
17
18def negative(vector):
19 """取反"""
20 return Vector(vector.end_point, vector.start_point)
21
22def vector_product(vectorA, vectorB):
23 '''计算 x_1 * y_2 - x_2 * y_1'''
24 return vectorA.x * vectorB.y - vectorB.x * vectorA.y
25
26def is_intersected(A, B, C, D):
27 '''A, B, C, D 为 Point 类型'''
28 AC = Vector(A, C)
29 AD = Vector(A, D)
30 BC = Vector(B, C)
31 BD = Vector(B, D)
32 CA = negative(AC)
33 CB = negative(BC)
34 DA = negative(AD)
35 DB = negative(BD)
36
37 return (vector_product(AC, AD) * vector_product(BC, BD) <= ZERO) \
38 and (vector_product(CA, CB) * vector_product(DA, DB) <= ZERO)