线段扫描算法会插入2*n个线段的端点到一个事件队列，这个队列是一个修改过的优先队列，它能够支持在O(log q)的时间内（q是队列中元素个数）完成如下操作：
min
从队列中删除最小的元素。
insert(e)
将元素插入到有序队列中的适当位置。
member(e)
是否给定的元素已经在队列中。这个操作并不一定需要一个泛型的优先队列类型。在事件队列中，所有的点都是唯一的。如果要插入的事件点已经存在，那么它的信息会被加入到已经存在的事件点的信息中。因此将图9-13的点都插入到优先队列中之后，优先队列的规模是8个事件点。
线段扫描算法从上到下进行扫描，在线段状态中添加或者删除线段。在图9-13中，有序的线段状态从左至右表示处理了事件点之后，和扫描线相交的线段。为了正确计算交点，线段扫描算法需要计算出线段状态中给定线段Si左边或者右边的线段。线段扫描算法使用了一种增量平衡二叉树，这样能在O(log t)的时间内（t是树中元素的个数）完成如下操作：
insert(s)
将线段插入树中。
delete(s)
从树中删除线段。
previous(s)
返回有序线段集合，给定线段的前驱线段。
successor(s)
返回有序线段集合，给定线段的后继线段。
为了正确地维护线段的有序性，线段扫描算法在检测到线段Si和Sj存在交点时，交换这两条线段的顺序，很幸运的是，这个操作在O(log t)的时间内就能完成，只需要简单地更新一下扫描线和删除并再插入线段Si和Sj。例如，在图9-13中，当找到交点（6.66,6.33）时进行交换。
算法的最初阶段将会构建一个包含了2*n个点的优先队列。这个事件队列需要支持查询某个点是否已经存在的操作，因此，我们不能简单地使用堆这种通常用来组成队列的结构。由于队列要求有序，所以我们必须定义一个点的顺序。如果p1.y＞p2.y或p1.y=p2.y时，p1.x＜p2.x，那么p1＜p2。这个队列的规模不会超过2n+k，k是n条线段的交点个数。线性扫描算法会将所有在扫描线下方的交点加入到事件队列，当扫描线到达交点时，相交线段的顺序会被交换。一开始所有的交点都会在扫描线下方，所以我们会扫描所有的交点。
线段扫描算法会处理所有的事件点，一条线段在上端点被扫描时加入到状态结构中，并且在下端点被扫描时从状态结构中删除。因此线段状态存储的线段不会超过n条。在线段状态中查找线段的操作能在O(log n)的时间内完成，而且不会执行超过O(n+k)次操作，所以算法的开销是O((n+k)log(n+k))。由于k不会大于C(n,2)或者n*(n-1)/2，所以这个等式可以化简：
O((n+k)log(n+k))=O((n+k)log(n*(n+1)/2))
使用对数的性质，可以得到：
log(n*(n+1)/2)=log n+log(n+1)-log 2≤log n+log(2n)-1≤2 log n
结果是：
O((n+k)log(n*(n+1)/2))=O(2*(n+k)log n)
因此总体性能还是O((n+k)log n)。
因为线段扫描算法的性能和输入的复杂程度有关（例如：交点的总数，任何时候扫描线维护的线段平均个数），我们使用特定的问题和输入数据来做算法的基准测试。我们现在讨论两个特定问题。
一个很有意思的数学问题是如何使用一些牙签和一张纸，计算π的一个近似值（叫做Buffon's needle problem）。假设牙签长度为10，在纸上画一些垂直线段，每条线段相隔d，线段长len。随机将n根牙签投向纸上，牙签和线段会有k个交点。一根牙签有可能和一条线段相交的概率是(2*len)/(π*d)[1]。
当交点的个数远远少于n2时，穷举检测算法将会浪费大量的时间在检测那些不相交的线段之间是否存在交点（见表9-4）。当存在大量交点时，采用哪种算法，其决定因素便是LineState在线段扫描时维护的线段个数。如果这个值比较小，那么我们需要使用线段扫描算法来获得更好的性能。
最坏情况下，线段之间的交点是O(n2)个，此时线段扫描算法的性能将会特别差，因为它在维护线段状态结构上开销过大。我们从表9-5的结果中可以看到穷举检测算法轻易地胜过了线段扫描算法，这里n条线段最多会有n*(n-1)/2个交点。
[1]http://mathworld.wolfram.com/BuffonsNeedleProblem.html/.