Segment Intersecion - 线段交叉
问题
判断两线段和是否相交。
解法
对于一条线段和一条直线，若线段两端点在直线的不同两侧则称该线段“跨越”了该直线。根据该公理，线段和相交有两种情况：
两条线段和，任意一条线段的两个端点都在另一线段所在直线的两侧。即的两端点跨越所在的直线，的两端点也跨越所在直线。如图所示：
对于图，的两端点和分别在所在直线的两边，且的两端点和分别在所在直线的两边，因此和相交。
设和的叉积为，和的叉积为，和的叉积为，和的叉积为。根据Cross中的转向可知，、两个叉积的转向相反，一正一负（表示一个方向与方向向量（平面中的轴）相同，另一个方向相反），、两个叉积的转向相反，一正一负。
对于图，和的叉积转向相反，但和的叉积转向相同，同正同负，因此图2中的两线段不相交。
线段的其中一个端点在线段上，这是一种边界情况，无需考虑的另一个端点的位置，也可以确定、相交。如图所示：
点在线段上的条件为：和两向量方向相同，即两向量的叉积值为；且点的坐标在线段的范围内。
该算法的时间复杂度为。