本文算法见：http://www.faqs.org/faqs/graphics/algorithms-faq/ 中的Subject 1.03

线段的定义

很明显，线段的端点由两个SPoint来定义，SPoint定义如下，坐标系中的x，y坐标可以决定一个点：

class SPoint(object): def __init__(self, a=0.0, b=0.0): self._x = a self._y = b

所以一条线段AB的定义可以为(SPoint A, SPointB).很明显，这个线段用A，B来表示的话就是：

AB = A + r(B-A), r=[0,1]

r=0的时候，线段AB其实就是A点，r=1的时候，线段AB就是B点。r的取值在0-1之间就描述了AB之间的的线段。

线段的交叉

给定两个线段AB，CD，根据上面的定义，这两个线段的程序表达式如下：

AB = A + r(B-A), r=[0,1] CD = C + s(D-C), s=[0,1]

如果AB和CD有交叉，那么必然有对应的 r 和 s 满足下面的等式：

A + r(B-A) = C + s(D-C)

转换成坐标x, y也就是：

A._x+r(B._x-A._x)=C._x+s(D._x-C._x) A._y+r(B._y-A._y)=C._y+s(D._y-C._y)

根据上面的两个等式可以得到 r 和 s 的值为：

(A._y-C._y)(D._x-C._x)-(A._x-C._x)(D._y-C._y) r = --------------------------------------------- (B._x-A._x)(D._y-C._y)-(B._y-A._y)(D._x-C._x) (A._y-C._y)(B._x-A._x)-(A._x-C._x)(B._y-A._y) s = --------------------------------------------- (B._x-A._x)(D._y-C._y)-(B._y-A._y)(D._x-C._x)

很明显，当 0<= r <=1 并且 0<= s <=1的时候，两个线段是有相交的。

当 r 或者 s 的分母为0时，两条线段是平行的。 当 r 或者 s 的分母为0并且分子也为0时，两条线段是重合的。

延长线上相交

如果r>1, 线段的交点位于AB的延长线上； 如果r<0, 线段的交点位于BA的延长线上； 如果s>1, 线段的交点位于CD的延长线上； 如果s<0, 线段的交点位于DC的延长线上；

实现

实现的代码如下，注意在测试用例中有一个特殊的case：[(1,1), (2,2), (2,2), (3,3)], 线段AB和CD交于(2,2)，但是线段AB和CD其实是一条直线，具体判断这种情况为相交线还是不相交就看应用场景了.

# -*- coding: utf-8 -*- class SPoint(object): def __init__(self, a=0.0, b=0.0): self._x = a self._y = b def LineIntersection2D(A, B, C, D): rDenominator = (B._x-A._x)*(D._y-C._y)-(B._y-A._y)*(D._x-C._x) rNumerator = (A._y-C._y)*(D._x-C._x)-(A._x-C._x)*(D._y-C._y) sDenominator = (B._x-A._x)*(D._y-C._y)-(B._y-A._y)*(D._x-C._x) sNumerator = (A._y-C._y)*(B._x-A._x)-(A._x-C._x)*(B._y-A._y) if rDenominator == 0: # rDenominator == sDenominator # lines are parallel return False r = (1.0) * rNumerator / rDenominator s = (1.0) * sNumerator / sDenominator if 0<=r<=1.0 and 0<=s<=1.0: return True else: return False if __name__ == '__main__': TestLines = [[(1,1), (2,2), (1,2), (2,1)], # intersected: YES [(1,1), (2,2), (1,1), (2,2)], # NO [(1,1), (2,2), (1,1), (2,1)], # YES [(1,1), (2,2), (1,2), (2,3)], # NO [(1,1), (2,2), (2,2), (3,3)], # YES or NO??? [(1,1), (2,2), (2,2), (3,4)]] # YES for points in TestLines: A = SPoint(points[0][0], points[0][1]) B = SPoint(points[1][0], points[1][1]) C = SPoint(points[2][0], points[2][1]) D = SPoint(points[3][0], points[3][1]) intersected = "Yes" if LineIntersection2D(A,B,C,D) else "No" print "AB and CD is intersected?", intersected