Sweeping - 扫除算法
问题
判断个线段中是否存在相交的线段。
解法
对于条线段，暴力枚举任意两条线段是否相交的时间复杂度为。Sweeping算法有更低的时间复杂度。
首先介绍扫除线，在平面中设置一条垂直于轴，平行于轴的直线，从左向右依次经过所有线段。如图所示：
假设扫除线与线段和同时相交，存在以下情况：
若与的交点的轴坐标大于与的交点的轴坐标，则称在轴的这个位置；反之若交点的轴坐标小于交点的轴坐标，则称在轴这个位置。这是一个全序关系。
显然，若，线段相交，则从左向右经过此交点时，与的全序关系会变化（从变为，或从变为）。
将所有线段的端点按照坐标从小到大排序，若两个端点的坐标相等，则在线段的左端点的端点优先（两个端点中坐标较小的端点为左端点，若坐标相等则坐标较小的端点算作左端点）。排序之后的所有端点组成事件点序列。当经过某个点时，有两线段的全序关系发生了变化，则认为这两线段相交。
扫除线从左边向右边移动经过每个端点，维护状态，该状态记录了当前扫除线与哪些线段的端点相交，以及端点的坐标。由此可得：
当扫除线遇到线段的左端点时，将线段加入状态。若此时状态中存在相交的端点（在线段上），若与相交，则可知这组线段中存在相交的线段；
当扫除线遇到线段的右端点时，将线段从状态中删除。若此时状态中存在相交的端点和（端点在线段上，端点在线段上），若在上方、在下方（反之亦然），且与相交，则可知这组线段中存在相交的线段；
状态通过红黑树实现，需要实现：插入线段，删除线段、查询线段上方的线段，查询线段下方的线段四种操作。
对于个线段，该算法的时间复杂度为。