在计算几何中（见计算几何算法），线段求交是指，给定n个不同的线段s₁,s₂,...,s_n(以端点的坐标表示线段)，想要解决以下两个问题:

①判断是否存在线段对(s_i,s_j),i≠j使得s_i,s_j相交。

②输出所有相交的线段对。

最简单的算法是检查每一对线段，时间复杂度是O(n²)。但是线段交的个数p在通常的情况下要比线段个数的平方n²要少，所以，希望得到一个时间复杂度与输出的线段对个数p相关的算法。

在计算几何中，更加有效的算法解决上面两个问题是用扫描线法。在1976年，Shamos和Hoey提出了Shamos-Hoey算法，使问题①在O(n log n)的时间内解决。1979年Bentley和Ottmann基于Shamos-Hoey算法提出了Bentley-Ottmann算法，使得问题②在O((n+p)log n)时间内解决。上述的算法要求假设输入是在一般的位置，即:

①对于每一条线段的两个端点的x轴坐标不同。 

②对于每一条线段的端点不在另外的线段上。

③不存在三条线段交于一点的情况。 

扫描线法的主要想法如下。假设一条垂直于x轴的直线L从平面的最左端移动到最右端，在移动的过程中会与输入的线段相交，并且这些与L相交的线段只有在有限的情况下会改变其与L的相交顺序或者组成，记这些有限情况为事件点。所以直线L从最左端移动到最右端的这个连续的过程就可以看作是由这些离散的事件点组成的。

下面介绍用扫描线法解决问题②，这些事件点分成两类。第一类情况是直线L经过了一条线段s的端点，这种情况下与L相交线段的集合会增加或者减少，所以相应的组成就会改变，对于这类事件点是很好处理的，因为线段的端点是已知的。第二类事件是L经过两条线段的交点，这种情况下L相交的线段的顺序就会得到改变。

扫描线法并不需要一个数据结构来描述扫描线L，用与L相交的线段的集合和事件点并用其他的数据结构来记录L的位置。

①二叉搜索树，用二叉搜索树记录与L相交线段的集合，并且用y轴的坐标作为顺序以构建二叉搜索树。当直线L经过一条线段s的左端端点p时，二叉搜索树就会添加s，而s在树中的位置则可以用二分搜索，所以添加s的时 间复杂度是O(log n)。类似地，当L经过一条线段s的右端点p时，二叉搜索树会删除s。

②优先队列，用优先队列来记录未来的可能的事件点，每一个事件点对应平面上的一个点和所对应的事件。事件点的优先顺序可以用x轴坐标决定。可以用二叉堆来实现优先队列。

①初始设定优先队列Q，记录其未来的时间点，并且优先顺序由x轴坐标决定。初始化Q中的元素是所有线段的端点。

②初始设定二叉搜索树T，记录与L相交的线段的集合，并且用y轴坐标为其顺序。初始化T中的元素为空集。

③当Q不为空时，找到并且删除Q中优先级最高的点p，即x轴坐标最小的点。用下述方法决定其所属的类型并且相应T的操作。如果p是一个线段s的左端端点，在T中插入s，并且搜索s的上一个和下一个线段r与t，检查s是否与r和t有交点，如果有交点，则将其交点插入优先队列Q; 如果p是一个线段s的右端端点，从T中删除s，并且搜索删除s前s的上一个和下一个线段，检查r与t是否相交，如果相交则将交点插入优先队列Q;如果p是两条线段s和t的交点(s在t的下面)，交换s和t在二叉搜索树的顺序，交换顺序后，找到t的下一个线段r与s的上一个线段u，从优先队列Q中删除rs与tu的交点，如果r和t有交点或者s和u有交点，则在优先队列Q中插入这些点。

Bentley-Ottmann算法中步骤③检查2n+p个事件点，其中p是相交点的个数。而对于每一种事件点，对应操作的时间复杂度是O(log n)，所以总共的时间复杂度是O((n+p)log n)。而对于Shamos-Hoey算法只需要将上面算法适当改进可以得到O(n log n)时间复杂度。如果算法中的找出相交的点不需要额外的储存，那么算法的空间复杂度则是O(n)。

Bentley-Ottmann算法与Shamos-Hoey算法是基于一般位置的假设。但是在实际应用中这些假设是不合理的，为此Bentley和Ottmann提出了对输入线段进行扰动以避免上述不合理的假设，但是却没有给出详细的说明如何扰动。de Berg给出了以下处理特殊位置的输入的处理方式：

①对于两个端点x轴相同的线段，可以设y轴坐标较小的端点为左端端点，类似的，如果Q中有很多x坐标相同的事件点，则可以用y轴坐标决定优先级。

②对于存在一条线段的端点在另外的线段上的情况，可以假设线段是一个闭集合，即包含其端点。这样对于两条线段共享一个端点和一条线段的端点在另 外的线段上的情况，端点都属于相交的点。

③对于有多条线段交于一点的情况，对于此交点创建并且处理一个单独的事件点。由此事件点所对应的二叉搜索树T的操作包括删除以此事件点为右端点的线段，插入以此事件点为左端点的线段，并且倒序剩下相交于这个点的线段。

O(n log n)部分是必不可少的，因为这符合了在决策树计算模型中线段交问题的下限。然而，有关p，相交点的个数的部分是可以提升的。1988年，Clarkson和Mulmuley分别提出了随机算法，期望的时间复杂度是O(n log n + p)，空间复杂度是O(n+p)。之后，Balaban提出了时间复杂度为O(n log n + p) 和空间复杂度为O(n)的算法。

如果输入的线段与其端点可以形成一个连通图，O(n log n)也可以提高。Clarkson,Cole和Tarjan给出了一个时间复杂度为O(n log^∗n + p)的算法， 其中log^∗n是多重log运算。之后，2009年，Eppstein、Goodrich和Strash提出了时间复杂度为O(n + k log⁽ⁱ⁾n)的随机性算法，其中log⁽ⁱ⁾是指迭代i次log的函数。

在通常情况下，用高精度来计算，并用有理数表示线段端点和交点的坐标。 但是，可以用浮点计算迎来加速计算与比较这些坐标，有关线段相交的精确度问题，详情可以参见文献。