很多情况下，我们需要在几何形状中检测交点。例如在大规模集成电路设计中，精密的电路将会印制在电路板上，因此除了预先设计好的交点之外，不能存在其他交点。在做旅游计划时，大量的路在数据库中以线段的形式存储，我们需要根据交点来将路网打断。
图9-13是一个例子，在6条线段中有7个交点。也许我们不需要比较所有的C(n,2)或者n*(n-1)/2条线段。相互之间离得很远的线段很明显不会有交点。线段扫描算法是一个已经证明的高效算法，它在处理时关注数据的一个子集，而不是全部数据，这样能够提高效率。想象一下，扫描并且输出水平线L和输入线段的交点。图9-13是从上到下扫描时，线段L的状态。
图 9-13 在6条线段中检测到7个交点线段扫描的创新在于将所有的线段从左至右按照y坐标进行排序[1]。线段只可能和扫描线上的相邻线段有交点。具体来说，有两条相交的线段Si和Sj，那么在扫描线上，肯定有它们相邻时。线段扫描算法能高效地维护扫描线状态，因此它能够快速地检测交点。
我们仔细地看看在图9-13的水平线上那9个选择了的位置，你将会发现这些位置是线段的起点或者终点，也或是一个交点。线段扫描不会真正地在笛卡儿平面上扫描线段，它首先在事件队列中插入2*n条线段的端点，这个事件队列是一个优化过的优先队列，如图9-14所示。所有的属于起点或者终点的交点都可以在处理这些点时找到。线段扫描算法对这个队列进行处理，维护L的状态，检测是否相邻的线段相交。其逻辑如图9-15所示。
图 9-14 线段扫描算法详解（第一部分） 图 9-15 线段扫描算法详解（第二部分）输入/输出
输入
笛卡儿平面上规模为n的线段集S。
输出
这些线段的k个交点（如果存在）。
假设
在S中不会出现重复的线段。没有两条线段会共线（也就是说，重叠或者有相同的斜率）。算法需要仔细地计算和精准地排序线段，这样才能支持垂直线段或者水平线段。没有一条线段只有一个点（例如，一条起点和终点相同的线段）。
[1]水平线段被认为左端点（高于）右端点。