十字路口,线段
线段是两个点的凸包，称为线段的端点(或顶点)。我们已知一组 线段，每个线段由其端点的x和y坐标指定，总共为 实数，我们想知道是否有两个线段相交。
在标准的线交问题中，给出了在欧几里得平面上相交的线段的列表。简单的算法检查每一对片段。然而，如果要检查大量可能相交的线段，则效率会变得越来越低，因为在典型的输入序列中，大多数线段对彼此并不接近。最常见,更有效的方法来解决这个问题大量的片段是使用一个扫描行算法,我们想象有一条直线滑线段和我们跟踪它线段相交在每个时间点上使用一个动态的基于二叉搜索树的数据结构。
线扫描算法
简化接近相关问题(如计算Voronoi图)的常见方法是使用扫描线。算法首先对端点进行排序 轴从左到右，然后通过一条垂直线从左到右通过所有点，并检查交叉点。
的状态扫描线的集合是与扫描线相交的线段。当扫描线向下移动时，状态会发生变化，但不是连续的。只有在特定的点上才需要更新状态。我们称这些点为事件点平面扫描算法。扫描留置点到达终点的时刻是算法实际运行的唯一时刻:它更新扫描直线的状态，并进行相交测试。特别是，如果排气点是一个线段的上端点，那么一个新的线段开始与扫描线相交，必须添加到状态中。此段与已经与扫描线相交的段进行相交测试，必须从状态中删除。此段与已经与扫描线相交的部分进行相交测试。如果偶数点是较低的端点，则段停止与扫描线相交，必须从状态中删除。这样，我们只测试有一条水平线与两个线段相交的线段对。不幸的是，这是不够的:仍然有情况，我们测试的对的二次数量，因为只有少量的交点。一个简单的例子是一组与x轴相交的垂直线段。所以算法对输出不敏感。 The problem is that two segments that intersect the sweep line can still be far apart from each other.
考虑到以上所有问题，有一种方法可以将这些想法转化为一种高效的算法:
下面是详细的步骤。
1)顺其自然 给定的线。必须有 端点来表示 行。根据x坐标对所有点排序。在排序时，维护一个标志来指示此点是该线的左点还是右点。
2)从最左边开始。每一点都要遵循吗
.....a)如果当前点是其线段的左点，检查其线段与上下两段的交点。并将其线添加到活动线段中(可以看到左端点，但还看不到右端点的线段)。注意，我们只考虑那些仍然活跃的邻居。
b)如果当前点是右点，将其线段从活动列表中移除，并检查其两个活动邻居(上面和下面的点)是否相交。