计算几何中的扫描（sweeping)算法（转自百度）

要解决的问题是判断一大堆线段中是否存在一对线段相交。

个人感觉计算几何的扫描算法算是属于解题思想上的东西，类似常规问题的搜索，是遍历处理对象的一种方法。

算法的思想是安照某种方式组织要被处理的对象，比如点、线段。组织方式通常就是从上到下、从左到右等。具体的办法是假想一条扫描线，并按某个方向（如X坐标的从小到大）依次移动它，在移动的每一步里执行自己的处理语句。

扫描算法所要维护的两个数据结构：

a. 事件点序列。也就是移动的每一步的“步”。

b. 扫描线状态。在每一步中，处于扫描线上的对象。

但是具体到本问题，实现细节上用到了红黑树存扫描线状态（一个全序T），红黑树没看过，不懂。关键是：

取所有线段的所有端点为事件点，按从左到右一级、从下到上二级排序，即为事件点序列。

在每一点上，判断当前点P：如果为某线段s的左端点，则取扫描线上位于s前面（ABOVE）的线段s1和s做相交判断，若相交，over；再取扫描线上s位于后面（BELOW）的线段s2和s做相交判断，同上。都不行的话插入s到扫描线状态中。如果P为某个s的右端点，仍取s1和s2，判断s1和s2是否相交，是的话over，否则从扫描线中删除s。

本质上讲，就是依次判断所有可能相交的线段是否相交。但关键就是这个判断次序、遍历方式。

为什么用红黑树？因为这里所涉及的操作，插入、删除、ABOVE、BELOW操作用红黑树的话都是logn的。