问题
判断两线段l1和l2是否相交。
解法
对于一条线段和一条直线，若线段两端点在直线的不同两侧则称该线段“跨越”了该直线。根据该公理，线段l1和l2相交有两种情况：
(1) 两条线段l1和l2，任意一条线段的两个端点都在另一线段所在直线的两侧。即l1的两端点跨越l2所在的直线，l2的两端点也跨越l1所在直线。如图所示：
对于图1，l2的两端点c和d分别在l1所在直线的两边，且l1的两端点a和b分别在l2所在直线的两边，因此l1和l2相交。
设ab和ac的叉积为ab−ac，ab和ad的叉积为ab−ad，cd和ca的叉积为cd−ca，cd和cb的叉积为cd−cb。根据Cross中的转向可知，ab−ac、ab−ad两个叉积的转向相反，一正一负（表示一个方向与方向向量k（x,y,z平面中的z轴）相同，另一个方向相反），cd−ca、cd−cb两个叉积的转向相反，一正一负。
对于图2，ab−ac和ab−ad的叉积转向相反，但cd−ca和cd−cb的叉积转向相同，同正同负，因此图2中的两线段不相交。
(2) 线段l1的其中一个端点在线段l2上，这是一种边界情况，无需考虑l1的另一个端点的位置，也可以确定l1、l2相交。如图所示：
点a在线段l2上的条件为：ca和ad两向量方向相同，即两向量的叉积值为0；且点a的x,y坐标在线段l2的x,y范围内。
该算法的时间复杂度为O(1)。
Introduction to Algorithms
源码
SegmentIntersection.h
SegmentIntersection.cpp
测试
SegmentIntersectionTest.cpp
