线段交点问题
设有 条线段，分布在二维平面中。我们的问题是：找出所有这些线段两两之间的交点。
最直观的思路是：遍历所有线段对，检查是否相交。这种 暴力法 的时间复杂度是 . 这在 较小时还能接受，但当 达到上万、几十万时，算法运行时间将不可接受。
有没有更优雅的算法？有没有方法，只检查“可能会交”的线段，跳过那些无关的组合？但在介绍它之前，我们需要先引出一个重要的思想：输入敏感性 vs 输出敏感性。
算法的输入敏感性与输出敏感性
我们通常说“算法复杂度依赖输入规模 ”，这是显而易见的。你给我多少数据，我就花多少时间/空间去处理。这被称为输入敏感算法，复杂度取决于输入大小。
但在某些问题中，输出的规模也会对算法复杂度产生重要影响。比如线段交点问题，假设你有 条线段，但它们分布得非常规整，没有一个交点。这种情况下，我们其实根本不需要做 的比较。而他们两两彼此都相交时，则会产生 个交点。
如果算法的时间复杂度依赖于 实际输出规模 （交点数），这类算法被称为输出敏感算法，复杂度取决于输入和输出。
所有的算法都是输入型敏感的，但如果设计出一种对输出敏感的算法，它会在结果稀疏时获得更优性能。
扫描线算法
一个观察
通过观察可以发现，如果拿一条平行于 轴的直线从上到下扫描，并关注它依次穿过的线段，并按照它与线段的交点在 轴上的位置进行排序。如果两个线段相交，那么在扫描线经过它们交点时，它们在当前的线段排序中是相邻的。也就是说，只有在“刚好要相交”的时候，它们在当前的扫描线上是左右相邻的两条线段。
那什么时候线段之间的相邻关系会发生改变呢？继续观察可以发现，有以下几种情况：
- 当扫描线刚刚扫到一条新线段的上端点，这条线段会“插入”当前的序列，它在插入的位置上可能会打破原来的相邻结构；
- 当扫描线扫过一个交点，意味着这两条线段相互穿过了，此时它们在扫描线上的顺序会交换，他们各自会获得对方原来的邻居；
- 当扫描线扫到某一条线段的下端点，这条线段就不再与扫描线相交了，相当于“退出”当前的视野，它原本的两个邻居，现在变成了新邻居。
算法步骤
基于这样的思想，就可以设计出一种扫描线算法，只考虑可能会相交的线段。扫描线算法是一种 事件驱动 的思想。
想象一根从上到下缓慢扫过平面的直线。每当扫描线扫描到上面观察到的三个情况时，就触发一个事件。我们用两个数据结构来协作完成整个过程：
事件队列 （Event Queue）：存储待处理的所有事件（上端点、下端点、交点），使用最大堆（优先队列）按 坐标降序排序
活动线段集合 （Active Set）：用于维护当前与扫描线相交的线段，按 坐标排序（比如平衡二叉树）
使用扫描线算法求平面中线段交点
基于上述的数据结构，算法的步骤如下：
对所有线段的上端点、下端点按照 坐标降序排序，用于模拟扫描线从上到下扫描的过程，将这些端点插入事件集合 中。
While ( 不为空)：
- 从 中取出一个事件点 （它的 坐标最大）
- 如果 是某条线段的上端点（进入）：
- 把这条线段插入当前扫描线穿过的线段序列 中（想象有一堆线段按 坐标排序挂在扫描线上）；
- 检查它和它的左右“邻居”是否相交；
- 如果相交，把交点也当作事件加入 ；
- 如果 是某条线段的下端点（离开）：
- 把这条线段从当前序列中删掉；
- 它原来的左右邻居现在变成了新邻居，检查它们之间是否可能相交；
- 如果相交，也把交点加入事件集合 ；
- 如果 是一个交点：
- 说明有两条线段在这里相交，输出他们的交点；
- 交换它们在当前序列 中的左右位置；
- 更新这两条线段和它们的新邻居的相交情况，有可能会产生新的交点，继续加入事件集合。
整个过程会不断地处理“下一个最近事件”，直到所有可能的交点都被枚举出来为止。
算法时间复杂度
整个算法的复杂度是输出敏感的，取决于输入的线段数量 和输出的交点数量 。 对端点排序以及插入 中:
事件总数是 个：每条线段的两个端点会产生两个事件，每个交点最多被处理一次，总共 个。
每个事件的处理：
- 向事件队列 插入/取出（堆操作，）；
- 在线段集合 中插入、删除或交换线段（通常用平衡树，）；
- 检查相邻线段是否相交（常数时间）；
因此，总体时间复杂度为：
参考资料
M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars, Computational Geometry: Algorithms and Applications, 3rd ed. Berlin, Germany: Springer, 2008, ISBN 978-3-540-77973-5.