【算法导论】33.2：判断任意两条线段是否相交

1.基本方法：扫描线法（sweeping）,垂直扫描线，只是可以判断是否相交，而不能打印交点。扫描线自左向右，x轴看作是时间，，两个假设：（1）没有垂直的线段（2）没有三条线段交与一点。

2.如果不相交，则对于处于任何位置的扫描线，两条线段的指间的比较关系式不变的。

3.使用的数据结构：（1）扫描线状态：给出相交的object的关系；（2）x轴上的扫描点为时间点序列。

4.使用红黑树。

今天的长相厮守，只是尽力而为而已。